Exclusión mutua: locks y pools en Java

Contexto

En el mundo de la programación concurrente surgen problemas cuando múltiples hilos tratan de modificar un recurso compartido. Un ejemplo claro de esto es el ejemplo del ContadorNaive en la práctica anterior, existen errores e inconsistencias en los resultados.

A continuación se definen dos términos para referirnos a este tipo de situaciones en el mundo concurrente:

Condición de carrera (race condition): Ocurre cuando en una ejecución dos o más hilos acceden a un recurso compartido (por ejemplo, una variable) al mismo tiempo, y el resultado depende del orden de ejecución (Oaks y Wong 2004).
Carrera por los datos (data race): Ocurre cuando dos o más hilos realizan una llamada a un método de un objeto compartido al mismo tiempo, y al menos una llamada es una escritura (Michael L. Scott 30 January 2024).

Por ejemplo, en el programa del ContadorNaive existe una race condition porque la variable \(counter\) puede ser accedida por varios hilos al mismo tiempo y el resultado de \(counter\) puede variar en distintas ejecuciones dependiendo del orden en el que se ejecutan los hilos. También existe una data race porque la variable \(counter\) puede ser leída y modificada con un método de escritura por al menos dos hilos al mismo tiempo.

El concepto de sección crítica nos permite evitar data races y race conditions. Una sección crítica es un bloque de código que solo puede ser ejecutado por un hilo a la vez.
Java provee varias implementaciones de secciones críticas, en esta prática abordaremos:

\(\diamond\) la palabra reservada synchronized y

\(\diamond\) la interface Lock.
En la clase teórica vimos que un objeto Candado es un objeto que resuelve el problema de exclusión mutua al permitir que solo un hilo lo obtenga a la vez. La palabra reservada synchronized funciona de forma similar a un candado, la diferencia es que no solo previene que dos o más hilos accedan a un bloque de código, además previene que dos o más hilos accedan a distintos métodos que modifican un mismo objeto al mismo tiempo. Cada objeto en Java tiene asociado un candado, es por eso que synchronized permite crear secciones críticas por objeto (Oaks y Wong 2004).
La clase Lock (java.util.concurrent.locks) nos permite crear secciones críticas de manera más flexible que al utilizar syncrhonized. La razón es que el scope (alcance) de synchronized comprende todos los métodos en los cuales se utilizó synchronized, en cambio, el scope de un objeto Lock solo comprende el bloque de código que se encuentra entre la llamada lock() (adquirir el candado) y unlock() (dejar el candado). La clase incluye otros métodos y existen varios tipos de objetos de tipo Lock: https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/package-summary.html.

La clase Semaphore es básicamente una generalización de un candado que incluye un contador. Es una generalización de un candado porque permite que un número \(n\) (\(n \geq 1\)) de hilos accedan a una sección crítica https://docs.oracle.com/javase%2F8%2Fdocs%2Fapi%2F%2F/java/util/concurrent/Semaphore.html.

Pools de hilos

A partir de Java (J2SE 5.0) se incorporaron las implementaciones de pools de hilos. El objetivo de una pool es crear un grupo de hilos en espera de tareas por ejecutar, una vez que existe una tarea, uno de los hilos la toma, la ejecuta, finaliza y vuelve a esperar por otra. Utilizamos pools para reusar hilos (mejorar el rendimiento) y mejorar el diseño del programa. No conviene utilizar pools si realizamos procesamiento secuencial (en batch) o si no importa la cantidad de hilos que ocupemos en un programa.

Para implementar una pool en Java utilizamos la interfaz Executor https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Executor.html, la cual tiene un método \(execute()\) que recibe como parámetro un objeto Runnable.

[language = Java , frame = trBL , firstnumber = last , escapeinside={(*@}{@*)}]
package java.util.concurrent;
  public interface Executor {
      public void execute(Runnable task);
  }

También provee una subinterface de Executor, llamada ExecutorService que implementa los siguientes métodos:

[language = Java , frame = trBL , firstnumber = last , escapeinside={(*@}{@*)}]
package java.util.concurrent;
  public interface ExecutorService extends Executor {
      void shutdown( );//termina las tareas que se hayan enviado al ejecutor, pero no realiza nuevas
      List shutdownNow( );//trata de terminar todas las tareas, incluso las que se han enviado y regresa una lista de las que no se empezaron
      boolean isShutdown( );
      boolean isTerminated( );//es verdadero si el estado de la pool esta en "terminado"
      boolean awaitTermination(long timeout, TimeUnit unit)
              throws InterruptedException;//Podemos esperar a que termine una determinado intervalo de tiempo
// Si mandamos una tarea via "submit" nos devuelven un objeto Future, nos sirve para checar si la tarea ha terminado
      <T> Future<T> submit(Callable<T> task);
      <T> Future<T> submit(Runnable task, T result);
      Future<?> submit(Runnable task);
      <T> List<Future<T>> invokeAll(Collection<Callable<T>> tasks)
              throws InterruptedException;
      <T> List<Future<T>> invokeAll(Collection<Callable<T>> tasks,
                                    long timeout, TimeUnit unit)
              throws InterruptedException;//Ejecuta todos los metodos en una coleccion
      <T> T invokeAny(Collection<Callable<T>> tasks)
              throws InterruptedException, ExecutionException;//ejecuta alguno y termina
      <T> T invokeAny(Collection<Callable<T>> tasks,  long timeout, TimeUnit unit)
              throws InterruptedException, ExecutionException, TimeoutException;
}

La clase Future se ve de la siguiente forma:

[language = Java , frame = trBL , firstnumber = last , escapeinside={(*@}{@*)}]
public interface Future<V> {
      V get( ) throws InterruptedException, ExecutionException; //Devuelve el resultado del callable, espera de ser necesario
      V get(long timeout, TimeUnit unit)
          throws InterruptedException, ExecutionException, TimeoutException;//Se bloquea hasta que se devuelva el resultado o hasta que expire el timeout
      boolean isDone( );//Devuelve verdadero si la tarea ya se realizo
      boolean cancel(boolean mayInterruptIfRunning);
      boolean isCancelled( );//
}

Si el método cancel() se llama, el objeto Callable, puede nunca empezar, pudo haber terminado y el método ya no tiene efecto o puede ser que se esté ejecutando y el hilo sea interrumpido aunque el objeto no cese por completo.

Java también tiene implementado una clase (ThreadPoolExecutor), la cual implementa la interface ExecutorService. La cual especifica el cómo ejecutar y terminar las tareas, permite especificar las características de la cola para las tareas. Sin embargo, lo abordaremos más adelante.

Ejemplos

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

Programa 1 (SynchronizedExample1): Utilización de synchronized, el método run es una sección critica, cada hilo lo ejecuta, y hasta que no termina de ejecutarlo lo deja.
Programa 2 (SynchronizedExample2): Utilización de synchronized, ejemplo de un problema con el alcance
Programa 3 (LockExample1): Ejemplo de un contador que utiliza un candado predefinido de Java
Programa 4 (ExampleExecutor): Ejemplo de una pool de hilos que ejecuta n tareas (runnables)
Programa 5 (CounterPool): Una pool de hilos que ejecuta un contador
Programa 6 (CounterPoolCallable): Una pool de hilos que ejecuta un contador, utiliza futures y callables
Programa 7 (ColaSecuencial): Implememtación de una cola secuencial, utiliza la clase Nodo
Programa 8 (Scheduler): Programa para completar, utiliza la clase Tarea

Ejercicios

Instrucciones:

Entrega en un PDF las respuestas de los ejercicios que no requieran implementarse, en los ejercicios que requieran implementación añade una breve descripción de los programas que entregas (sus nombres y qué hacen).
Solo un integrante del equipo debe subir la práctica. Los demás integrantes deben marcar la tarea como entregada y escribir, en un comentario privado dentro de la práctica, el nombre completo de la persona que realizó la entrega.
Cada ejercicio debe tener un programa que indique “Implementar” si aplica.
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 21 LTS o si no se entrega la breve descripción de los programas se penalizará.

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

Total de puntos: 100
Nota: En esta práctica no es necesario utilizar otros objetos de la biblioteca Concurrent de java que no hayan sido mencionados en el Contexto 1 de esta práctica, por ejemplo: getAndIncrement, ArrayBlockingQueue, ConcurrentLinkedQueue. Muchos de estos objetos ya predefinidos en java son implementaciones linealizables: con consistencia, y en esta práctica no los necesitamos.

El programa ColaSecuencial es una implementación de una cola secuencial. Implementa una Cola concurrente utilizando una pool de hilos (ExecutorService). No utilices candados ni synchronized.
Ejecuta varias veces tu implementación con diferentes secuencias de llamadas a métodos ¿Tu implementación funciona de acuerdo a lo que se espera de una cola o suceden inconsistencias? Por ejemplo,

1) Se hace \(enq(a)\), \(enq(b)\) y \(deq()\) y al final ambos elementos \(a\) y \(b\) están en la cola.

2) Se realiza un \(enq(a)\) y un \(enq(b)\) y la cola solo contiene al elemento \(a\) o \(b\).

3) Se desencola dos veces el mismo elemento.

Si existe una ejecución así toma una captura pantalla del resultado de tu programa que lo ejemplifique.

Hint: Para analizar si hay inconsistencias, utiliza la interfaz Future, solo ten cuidado con el método \(get()\) ya que fuerza a que el resultado del future sea devuelto en ese momento.

Importante: El orden en el que se suben las tareas con submit y se guardan en los futures, no es el orden en el que se realizan, solo es el orden en el que se les asignan a los hilos. Nuestro sistema es asíncrono, es decir, cada hilo puede tardarse más o menos en ejecutar la tarea que se le asignó.
¿Existen data races o race-conditions? Explica en qué variables y porqué suceden.
Utiliza candados y/o synchronized en tu implementación de forma que los métodos \(enq()\) y \(deq()\) sean una sola sección crítica y contesta: ¿existen inconsistencias?

Importante: El orden en el que se suben las tareas con submit y se guardan en los futures, no es el orden en el que se realizan, solo es el orden en el que se les asignan a los hilos. Nuestro sistema es asíncrono, es decir, cada hilo puede tardarse más o menos en ejecutar la tarea que se le asignó.
En una pool de hilos (ExecutorService), ¿si utilizamos más hilos equivale a un mayor throughput? Argumenta porqué.
Problema. Supón que perteneces a un equipo de trabajo en el cual estás a cargo de dar acceso a un servidor. Seis personas te pueden mandar tareas para que las ejecutes en el servidor. Las tareas del hilo \(0\) y \(2\) tardan \(500ns\), las del hilo \(1\) tardan \(2000ns\) y las de los hilos \(3\), \(4\) y \(5\) tardan \(3000ns\).

Tienes la instrucción de no dar acceso a más de tres al mismo tiempo y de no aceptar al mismo tiempo las tareas del hilo \(0\) y \(2\). Diseña e implementa una solución. Hint: Apóyate del programa Scheduler y Tarea, el semáforo inicializado en 3 representa que solo pueden entrar 3 al mismo tiempo, decide como utilizarlo en el programa Tarea (colocando sus métodos \(adquire\) y \(release\)); además, decide como utilizar un candado, para restringir aceptar las tareas de los hilos \(0\) y \(2\) al mismo tiempo.
- ¿Tu implementación cumple con Justicia?
- Sino es así, describe cómo podrías garantizarla.

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

Oaks, S., y H. Wong. 2004. Java Threads: Understanding and Mastering Concurrent Programming. O’Reilly Media. https://books.google.com.mx/books?id=r8hhO7oGKrEC.

← Volver al índice de prácticas