Candados clásicos y el modelo de memoria de Java

Contexto

Para que un programador pueda diseñar y razonar de manera concurrente sobre un sistema necesita conocer el modelo de memoria. Existen modelos de memoria a nivel de hardware (por ejemplo, el TSO de la máquina SPARC) y también a nivel de software (por ejemplo, el de Java, el de C++).

Informalmente, un modelo de memoria especifica como las acciones en memoria (por ejemplo, las lecturas y escrituras) en un programa parecen ejecutarse desde el punto de vista del programador, por ejemplo, el valor que debe regresar la lectura de una determinada ubicación en memoria.

En un programa de un solo hilo, el modelo de memoria es trivial, ya que se debe leer lo último escrito. Sin embargo, en un programa multihilo el modelo de memoria es más complejo, ya que una lectura de un hilo puede ver o no escrituras de otros (Michael L. Scott 30 January 2024).

Para un lenguaje de programación de alto nivel como Java, el modelo de memoria determina las transformaciones que el compilador puede aplicar a un programa al producir el bytecode (por ejemplo: https://gee.cs.oswego.edu/dl/jmm/cookbook.html), las transformaciones que la máquina virtual puede aplicar al producir el código nativo, y finalmente, las optimizaciones que el hardware puede realizar en el código nativo (Manson, Pugh, y Adve 2005).

Es por esto que como programadores necesitamos conocer el modelo de memoria, ya que las transformaciones que se realizan en el código, pueden impactar el resultado de nuestros programas. Sin un modelo de memoria bien especificado o si no lo conocemos, es imposible conocer los resultados de un programa.
El modelo de memoria de Java se ha estudiado ampliamente desde los 90’s (Manson, Pugh, y Adve 2005), de forma breve podemos resaltar dos puntos importantes sobre el modelo que nos afectan como programadores de Java: el Reordenamiento y la Visibilidad.

Reordenamiento. El compilador, con el objetivo de optimizar, puede intercambiar el orden de dos líneas de código de un programa concurrente, por ejemplo, en el candado Peterson nos representa un problema si el compilador considera cambiar el orden de \(flag[i] = true;\) y \(victim = i;\).

Visibilidad. Como cada hilo tiene copias de los objetos compartidos en la Heap, puede ser que la escritura del objeto no se refleje de forma enseguida en la lectura de ese mismo objeto por otro hilo.

Para mitigar este par de problemas se utilizan los campos volatile y final, e incluso los objetos atómicos. Los campos volatile y final garantizan que la actualización de una variable se refleje enseguida en todas sus copias, y que se respete el orden de las instrucciones en los programas.

Ejemplos

En el siguiente link: https://github.com/surindt/FC_CConcurrente/tree/main/Programas_P3

Programa 1 (VolatileExample1): Programa que ejemplifica el problema de Visibilidad en el JMM.
Programa 2 (VolatileExample2): Programa que ejemplifica el problema de Reordenamiento en el JMM.
Programa 3 (LockPeterson): Programa que ejecuta la clase Peterson, todas las variables utilizan volatile
Programa 4 (ExecuteBakery): Programa que ejecuta la clase Bakery, implementa Bakery de forma no acotada (sin overflow). Utiliza objetos atómicos.

Ejercicios

Entrega en un pdf las respuestas de los ejercicios que no requieran implementarse y añade una breve descripción de los programas que entregas (sus nombres y qué hacen).
Debes realizar un programa en cada ejercicio que indique “Implementar”.
El formato y el medio de entrega los indicará tu ayudante de laboratorio.
Recuerda que debes utilizar Java 21 LTS.
Si no compila utilizando Java 21LTS o si no se entrega la breve descripción de los programas se penalizará.

Tiempo de elaboración:\(\approx\) 2hr

Total de puntos: 100
Importante: No utilicen en su contador la paquetería Atomic, en general no la utilicen. Cuando utilizan compareAndSet(), get(), getAndIncrement(), etc, están haciendo que todo lo que está adentro de estos métodos se haga de forma atómica. Por ejemplo, si utilizan getAndIncrement() en su contador, este se vuelve linealizable, es decir, con consistencia, siempre contará bien, entonces no tendría caso utilizar candados y ese es el objetivo de esta práctica.

También tengan cuidado con otros objetos de la biblioteca Concurrent de java, muchas de estas implementaciones ya son linealizables, y en esta práctica no las necesitamos.

Solo ocupan volatile.

El algoritmo de candado Peterson solo funciona para 2 hilos, utiliza el algoritmo de candado Peterson para implementar un algoritmo de candado que funcione para 4 hilos. Hint: Apóyate del programa Peterson
1. Para probar que tu candado funciona, crea una implementación en donde utilices un ExecutorService para ejecutar 400 tareas, cada tarea debe aumentar en uno un objeto Contador. Utiliza tu candado para 4 hilos para tener consistencia en tu Contador.
2. De alguna forma obtén el número de veces que los hilos aumentan el contador. ¿Cada uno realiza exactamente 100 tareas o hay algunos que realizan más?
3. ¿Consideras que la implementación cumple con Justicia? Justifica tu respuesta.
Adventencia: Puedes considerar el pseudocódigo de la Tarea 3 (\(DoublePeterson\)). Solo ten cuidado con los id’s, ya que si utilizas modulo 2 para Peterson y modulo 4 para DoublePeterson, puede pasar que dos hilos ejecuten un candado Peterson con el mismo id. Si dos hilos en Peterson tienen el mismo id entonces no se cumple exclusión mutua, y el candado DoublePeterson no cumplirá su función, no contará las 400 tareas.
En base a la implementación de Bakery vista en la clase teoría, implementa Bakery para 4 hilos. Hint: Crea los arreglos \(flag\) y \(label\) de tamaño 4, si consideras necesario utiliza campos volatile
1. Con ayuda de un ExecutorService ejecuta 400 tareas, cada tarea debe aumentar en uno un objeto Contador. Utiliza tu candado para 4 hilos para tener consistencia en tu Contador.
2. De alguna forma obtén el número de veces que los hilos aumentan el contador. ¿Cada uno realiza exactamente 100 tareas o hay algunos que realizan más?
3. ¿Consideras que la implementación cumple con Justicia? Justifica tu respuesta.
Revisa el programa de Bakery que se les compartió como ejemplo, ejecútalo varias veces, revisa el código y contesta:
1. Revisa para que sirve el campo AtomicReference, y qué hacen los métodos compareAndSet() y get().
2. Describe como funciona en a lo más 6 líneas de computadora.
3. ¿Si next no es un AtomicReference sigue funcionando? Hint: Recuerda la Cola concurrente sin candados que implementaste en la Práctica 2
4. ¿Consideras que mantiene la lógica de la implementación vista en clase/tu implementación del ejercicio anterior? Justifica porqué.

Manson, Jeremy, William Pugh, y Sarita V. Adve. 2005. «The Java memory model». En Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 378-91. POPL ’05. New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/1040305.1040336.

Michael L. Scott, Trevor Brown. 30 January 2024. Shared-Memory Synchronization. Springer Cham.

← Volver al índice de prácticas