Los semáforos se inventaron para resolver problemas de sincronización sin espera activa. Sin embargo, son primitivas de bajo nivel, no están estructuradas. Son propensas a provocar errores de programación y la responsabilidad recae completamente en los programadores. La omisión accidental de un signal o un unlock provoca fallos críticos.
Los monitores son una primitiva estructurada de programación concurrente que concentra la responsabilidad en los módulos de los programas. Son una generalización del núcleo de los primeros sistemas operativos. Con el tiempo, los monitores se convirtieron en un mecanismo de sincronización muy importante ya que son una generalización natural de la programación orientada a objetos ([Ben-Ari]).
Los monitores evolucionaron a partir de ideas y discusiones entre Edsger Dijkstra, Per Brinch-Hansen, Ole-Johan Dahl y C.A.R. Hoare ([Brinch]). Buscaban una forma de estructurar a los sistemas operativos usando lenguajes de alto nivel[2]. En 1973 fueron formalizados por Hoare en su notación más conocida ([Hoare1]).
La idea era que el sistema operativo es un conjunto de módulos, schedulers, que asignan recursos compartidos para diversos procesos. Llamaron monitor al conjunto de procedimientos y datos que debía gestionar cada scheduler. Para evitar los problemas derivados de los accesos concurrentes cada monitor debía asegurar la exclusión mutua de la ejecución de sus procedimientos. Las variables del monitor solo podían ser accedidas desde estos procedimientos.
Brinch Hansen diseñó el primer lenguaje concurrente, Concurrent Pascal, basado en Pascal y con ideas de Modula67. Concurrent Pascal sirvió para el desarrollo de varios sistemas operativos experimentales y otros lenguajes como Concurrent C, Mesa, ADA y Java. Este último incluye monitores como construcción sintáctica: la combinación de métodos y bloques synchronized con las funciones de sincronización wait, notify y notifyAll.
En la propuesta original un monitor se declaraba de una forma similar a la siguiente[3]:
monitor Counter
integer counter = 0
procedure add
counter = counter + 1
El monitor Counter tiene una variable counter y el procedimiento add. La variable es accesible solo desde este procedimiento.
Ningún procedimiento de un monitor se ejecutará si otro se está ejecutando, es decir, se asegura exclusión mutua en la ejecución de sus métodos. Como las variables solo son accesibles desde sus procedimientos, el problema de la sección crítica está resuelto.
La estructura de monitores que encapsula variables y procedimientos es similar al concepto de programación orientada a objetos. Esta es una de las razones por la que Java implementa monitores como construcción sintáctica del lenguaje. Aunque no tiene una construcción específica para definir monitores, cada objeto en Java tiene asociado un mutex implícito.
Dicho mutex se puede usar para forzar la exclusión mutua de un bloque de código indicando que está synchronized con el objeto. Como en el siguiente ejemplo (código completo):
Object lock = new Object();
...
for (int i =0; i < max; i++) {
synchronized (lock) {
counter += 1;
}
}Java agrega automáticamente las operaciones lock y unlock sobre el mutex del objeto al inicio y salidas del bloque de código. La alternativa equivalente y más simple es declarar synchronized a los métodos que acceden a recursos compartidos, como el siguiente ejemplo (código completo):
...
synchronized void add() {
counter++;
}
...
for (int i =0; i < max; i++) {
add();
}En este caso el mutex está asociado a la propia instancia, el objeto this. El prefijo synchronized especifica que el hilo debe obtener el lock para ejecutar el método. Las llamadas a otros métodos retienen el acceso exclusivo hasta que se haya salido del método synchronized.
|
Note
|
Una clase cuyos métodos públicos están todos declarados como synchronized se denomina monitor Java. Aunque es solo una convención, no hay obligación sintáctica de hacerlo así. |
Un error habitual de programadores no experimentados es suponer que el mutex de cada instancia es un mutex global que resguarda a los métodos sincronizados de todas las instancias de una clase. Un método de instancia synchronized solo asegura la exclusión mutua de ese método sobre la misma instancia. Cada instancia ejecuta sus métodos independientemente de las demás. Esto significa, por ejemplo, que no hay exclusión mutua si varias instancias modifican concurrentemente una variable estática desde un método de instancia synchronized. Para estos casos hay que definir explícitamente un objeto estático compartido por las diferentes instancias, o hacerlo desde un método de clase synchronized.
La exclusión mutua entre procedimientos no es suficiente para la sincronización general entre procesos, por ello se añadieron dos operaciones: wait y signal (opcionalmente broadcast, similar a wait pero despierta a todos los hilos en la cola). Estas permiten bloquear y desbloquear procesos cuando se cumple alguna condición. Por ejemplo, para bloquear a los productores si el buffer está lleno y desbloquearlos cuando hay nuevamente espacio.
Las operaciones wait y signal se implementan de distintas formas:
- Variables de condición explícitas
-
Se declaran explícitamente las variables de condición que se usarán en el programa. No son variables normales, no permiten almacenar o leer valores, solo pueden usarse como receptoras de wait y signal. Las variables de condición tienen asociada una cola de los procesos bloqueados en ellas. Es responsabilidad del programa la verificación de condiciones lógicas y la llamada a wait y signal sobre las variables de condición adecuadas.
El signal sobre una variable desbloquea a un proceso en esa variable, si no hay ninguno no tiene ningún efecto. Esta fue la implementación original en Concurrent Pascal, los lenguajes que tienen construcciones[4] de variables condicionales permiten mecanismos y algoritmos equivalentes.
- Variables de condición implícitas
-
Las operaciones wait y signal no están ligadas a ninguna variable explícita, hay una única variable implícita con una única cola. Como no es posible señalizar a variables diferentes se requieren variables de estado adicionales. Un proceso que se desbloquea debe verificar esas variables de estado para decidir si le corresponde continuar (en general implica cambiar un if por un while).
Como en la forma anterior, si no hay ningún proceso bloqueado la operación signal no tiene efecto. Esta es la implementación de monitores en Java, la operación wait es el método homónimo, signal es notify y broadcast es notifyAll.
- Objetos protegidos
-
El bloqueo y desbloqueo es automático y depende de expresiones lógicas, o guards. El compilador o la máquina virtual tienen la responsabilidad de bloquear al proceso si la condición es falsa y despertarlos si se hace verdadera.
Este tipo de mecanismo se denomina tipo u objetos protegidos. En ADA[5], por ejemplo, para que el método Insert solo se ejecute cuando la variable Empty es verdadera:
protected body Protected_Buffer_Type is entry Insert (An_Item : in Item) when Empty is (1) begin ... end
-
La expresión lógica, o guard, de Insert.
-
Un monitor se suele representar gráficamente de la siguiente forma:
Por la exclusión mutua solo un proceso puede estar dentro del monitor. Los procesos dentro del monitor pueden bloquearse en variables de condición, por lo que tienen que liberar temporalmente el lock para que otros puedan entrar. Para diferenciarlos de procesos que todavía no han entrado al monitor, a los bloqueados en variables de condición se los representan en salas internas.
Cuando un proceso que está dentro del monitor señaliza (S) a una variable de condición, si hay procesos esperando en variables de condición (W) y otros esperando para entrar al monitor (E), ¿se bloquea al proceso que señaliza? ¿A qué proceso se desbloquea primero?
Los monitores deben especificar la prioridad que dan a los diferentes tipos de procesos. Como comprobaremos enseguida, esa especificación es fundamental para el diseño de los algoritmos.
Hay tres alternativas habituales:
-
El proceso que estaba bloqueado en la variable de condición señalizada se debe reanudar inmediatamente. A esta condición se le llama requerimiento de reanudación inmediata (o IRR, Immediate Resumption Requirement). Es característica de los monitores tradicionales, su especificación de prioridades es
E < S < W.
Los procesos bloqueados en las variables de condición (W) son los de mayor prioridad, el proceso que señaliza (S) se bloquea inmediatamente y cede el monitor. Los que están esperando en la entrada (E) son los de menor prioridad.
-
El proceso que señaliza sale del monitor, luego se ejecutan los que estaban bloqueados en la variable de condición señalizada y finalmente los que esperan entrar al monitor. Esta especificación es
E < W < S.
-
Los procesos que están esperando para entrar tienen la misma prioridad que los bloqueados en variables de condición,
E = W < S.
Esta es la especificación de monitores en Java. El proceso que señaliza tiene la mayor prioridad, continúa su ejecución hasta salir del monitor. Los procesos desbloqueados por el notify o notifyAll van a la misma cola que los procesos en espera para entrar al monitor.
Hoare demostró ([Hoare1]) que los monitores son equivalentes a los semáforos ya que cualquiera de ellos se puede implementar con el otro. La simulación de semáforos con monitores es un buen ejemplo. Se necesita una variable entera para el valor del semáforo (value) y una variable de condición (notZero) para bloquear a los procesos en la operación wait si el semáforo es igual a cero.
El siguiente es el algoritmo de simulación de semáforos con monitores tradicionales:
monitor Semaphore
integer value = k
condition notZero
operation wait
if value == 0
waitC(notZero)
value = value - 1
operation signal
value = value + 1
signalC(notZero)
El algoritmo es correcto pero tiene un matiz importante, requiere la reanudación inmediata (es decir E < S < W). Cuando un proceso ejecuta signalC, el proceso desbloqueado debe ejecutarse inmediatamente para evitar que value sea modificado por otro. Por ejemplo: uno que está a punto de ejecutar wait (como puede ocurrir en Java ya que la prioridad de ambos es la misma, E = W), o el mismo proceso que hizo el signal puede hacer otro wait. En ambos casos el valor del semáforo acabaría negativo, un error grave.
Si el monitor no asegura E < S < W, el proceso tiene que volver a verificar si la condición se mantiene al despertarse del wait. En este caso tiene que verificar si value sigue siendo distinto a cero.
En el método wait hay que cambiar el if por while:
operation wait
while value == 0
waitC(notZero)
value = value - 1
|
Note
|
La reanudación inmediata simplifica los algoritmos pero también genera retrasos innecesarios en los procesos que señalizan. Cuando no se cuenta con esta propiedad el patrón de programación correcto para verificar la condición es usar while en lugar de if. |
El algoritmo modificado puede ser directamente traducido a Java. Se necesita la misma variable entera value e implementar el wait y signal como métodos synchronized (en este ejemplo se usa p y v para no confundir con el wait nativo de Java):
class Semaphore {
int value;
public Semaphore(int v) {
value = v;
}
synchronized void p() {
while (value == 0) {
wait();
}
value--;
}
synchronized void v() {
value++;
notify();
}
}CounterSemaphore.java es el código completo de la simulación semáforos. Este ejemplo es similar y equivalente al código con la clase Semaphore de java.util.concurrent que vimos en el capítulo [semaphores].
La implementación de mutex es más sencilla (código completo) que la de semáforos, solo hace falta una variable booleana (lock):
class Mutex {
boolean lock;
synchronized void lock() {
while (lock) {
wait();
}
lock = true;
}
synchronized void unlock() {
lock = false;
notify();
}
}Los monitores no están limitados solo a construcciones sintácticas, también son una forma de estructurar los programas. Se pueden implementar los mismos algoritmos en cualquier lenguaje si se asegura exclusión mutua entre las funciones del monitor y se disponen de variables de condición. Las librerías POSIX Threads proveen ambas, además del mutex también ofrecen variables de condición idénticas a las diseñadas para monitores.
Las variables de condición de POSIX Threads tienen las operaciones estándar: wait (pthread_cond_wait), signal (pthread_cond_signal) y la operación broadcast (pthread_cond_broadcast) para despertar a todos los procesos (similar a notifyAll de Java).
Los monitores, y Java, requieren que wait, notify y broadcast se llamen desde métodos sincronizados. Para asegurar las mismas condiciones de entrada y salida de la sección crítica del monitor, POSIX Threads requiere que la función pthread_cond_wait se llame con un mutex asociado[6] como segundo argumento. Así pues, su funcionalidad es similar a Java: cuando el proceso se bloquea libera el mutex (es una operación atómica) y cuando se desbloquea lo vuelve a adquirir.
Para implementar semáforos con el método de monitores se necesita un mutex, una variable de condición y el valor del semáforo:
pthread_mutex_t mutex;
pthread_cond_t notZero;
int value = 1;Se usa mutex para asegurar la exclusión mutua entre las dos operaciones (p y v), la variable de condición notZero para los procesos bloqueados en el wait y value para el valor del semáforo. Salvo las llamadas explícitas a lock y unlock (al inicio y fin de cada función respectivamente), el resto del código es idéntico a la implementación de semáforos con monitores en Java.
El código simplificado[7] (código completo):
void p() {
mutex_lock(&mutex);
while (value == 0) {
cond_wait(¬Zero, &mutex);
}
value--;
mutex_unlock(&mutex);
}
void v() {
mutex_lock(&mutex);
value++;
cond_signal(¬Zero);
mutex_unlock(&mutex);
}En la llamada a cond_wait, además de la variable de condición, se envía como argumento el mutex del monitor para cumplir con los requisitos de monitores:
-
El mutex es liberado cuando el proceso se bloquea en una variable de condición, así puede entrar otro proceso.
-
El mutex vuelve a adquirirse en cuanto el proceso es despertado por un signal y así asegura la exclusión mutua en el monitor. El proceso despertado no podrá continuar hasta que el que señalizó haya ejecutado el unlock al final de su función.
El proceso que se despierta en la variable de condición compite en la entrada con los demás procesos en la cola de mutex. Así pues, las prioridades de monitores con POSIX Threads son idénticas a las de Java: E = W < S.
La implementación de un semáforo mutex es igual de sencillo que el de Java, el código simplificado (código completo):
void lock() {
mutex_lock(&mutex);
while (locked) {
cond_wait(&unLock, &mutex);
}
locked = 1;
mutex_unlock(&mutex);
}
void unlock() {
mutex_lock(&mutex);
locked = 0;
cond_signal(&unLock);
mutex_unlock(&mutex);
}En el capítulo [semaphores] vimos algunos algoritmos de sincronización, no se pretende resolver todos los problemas con dichos algoritmos, ni que se deban reprogramar cada vez que se necesitan (la mayoría de ellos ya están disponibles como librerías). Los estudiamos porque son modelos simples de los diferentes tipos de problemas de programación concurrente.
La mala noticia es que con monitores haremos lo mismo, estudiaremos los algoritmos para resolver los mismos problemas. La buena noticia es que los problemas (barreras, productor-consumidor, lectores-escritores, etc.) ya nos son conocidos por lo que no habrá que repetir la presentación de cada uno de ellos. La segunda buena noticia es que los algoritmos con monitores son más sencillos que sus equivalentes con semáforos.
El algoritmo de barreras con monitores es significativamente más sencillo con monitores que con semáforos. En Java solo hace falta un contador (arrived) inicialmente en cero. Cuando cada proceso ejecuta barrier se incrementa el contador, si todavía no es el último se bloquea con wait. Si es el último proceso en llegar pone a cero el contador y despierta a todos los procesos con notifyAll (código completo):
synchronized void barrier(int n) {
arrived++;
if (arrived == n) {
arrived = 0;
notifyAll(); (1)
} else {
wait();
}
}-
Despierta a todos los procesos bloqueados.
El proceso que ejecuta notifyAll es siempre el último proceso que faltaba por llegar a la barrera. El método sincronized barrier asegura exclusión mutua en el bloque que cambia el valor de arrived, por lo tanto todos los procesos anteriores ya ejecutaron el wait y están bloqueados. No se pueden perder señales ni dejar procesos sin despertar.
Tampoco se puede adelantar ningún proceso, la asignación de arrived y el notifyAll son atómicas. Cuando el primer proceso de la siguiente fase pueda entrar en barrier el valor de arrived ya será 0, por lo que quedará bloqueado en el wait (por ser menor que n).
Este algoritmo funciona aunque el monitor tenga especificación diferente a E = W < S –por ejemplo E < S < W–, porque el valor de arrived fue asignado antes de ejecutar notifyAll.
Así como existen las variables condicionales en POSIX Threads, otros lenguajes también proveen las mismas funcionalidades[8]. En Python se puede usar un objeto de threading.Condition asociado con el mutex de las funciones del monitor. Además del contador arrived se usa mutex y la variable de condición allArrived sobre la que se señalizará cuando todos los procesos hayan llegado.
mutex = threading.Lock()
allArrived = threading.Condition(mutex)
arrived = 0El código simplificado de la función barrier (código completo):
def barrier(n):
with mutex: (1)
arrived += 1
if arrived == n:
arrived = 0
allArrived.notify_all()
else:
allArrived.wait()-
with mutex asegura exclusión mutua de todo el bloque, en este caso es la función completa.
La función broadcast simplifica el algoritmo, sin ella habría que hacer tantos signals como procesos bloqueados. A diferencia de la barrera con semáforos, en este caso no es un problema, solo hay que agregar un bucle. El mutex de la función impide que procesos desbloqueados se adelanten y ejecuten el wait cuando todavía no se acabó de despertar a los procesos anteriores. Es una ventaja de usar el patrón de monitores.
El algoritmo de productores-consumidores con buffer finito se puede implementar con dos variables de condición (código completo en Python): una para bloquear los productores cuando el buffer está lleno (notFull) y otra para bloquear a los consumidores (notEmpty) cuando no hay elementos en el buffer.
La lógica del productor es sencilla. Mientras el buffer está está lleno se bloquea en notFull. Después de agregar un elemento se hace un signal a notEmpty para que se despierte un consumidor (si hay alguno esperando).
def append(self, data):
with mutex:
while len(buffer) == buffer.maxlen:
notFull.wait()
buffer.append(data)
notEmpty.notify()El consumidor se bloquea si el buffer está vacío y luego de obtener un elemento señaliza notFull por si hay productores bloqueados.
def take(self):
with mutex:
while not buffer:
notEmpty.wait()
data = buffer.popleft() (1)
notFull.notify()
return data-
Extrae el primer elemento de la lista.
El algoritmo es correcto porque asegura que el productor no puede avanzar si no hay espacio en el buffer, ni los consumidores si el buffer está vacío. Mientras se hace la verificación del estado del buffer ningún otro proceso puede agregar o quitar elementos debido a la exclusión mutua entre métodos del monitor.
En los monitores nativos de Java no se pueden usar diferentes variables de condición, pero el algoritmo es casi idéntico (código completo):
synchronized int take() {
while (buffer.isEmpty()) {
wait();
}
data = buffer.remove();
notifyAll();
return data;
}
synchronized void append(Integer data) {
while (buffer.size() == size) {
wait();
}
buffer.add(data);
notifyAll();
}Al no poder disponer de variables independientes los productores y consumidores comparten la misma cola, por lo que no se puede discriminar a qué procesos hay que desbloquear. Ambos llaman a notifyAll para que todos –productores y consumidores– verifiquen si pueden continuar. Como la verificación se hace dento de un while el algoritmo también es correcto, pero potencialmente más ineficiente[9]: cuando un productor o consumidor ejecuta notifyAll se despiertan todos los productores y consumidores bloqueados, aunque solo uno de ellos podrá salir del bucle y añadir o quitar un elemento.
Se usan dos variables de condición: canRead para notificar a los lectores y canWrite para los escritores. También una variable entera readers para contar los lectores en la sección crítica y la booleana writing para indicar si hay un escritor (código completo).
Si hay un escritor en la sección crítica los lectores esperarán en la variable canRead hasta que el escritor señalice y comprueben si pueden entrar. Si es el caso, incrementan el número de lectores y señalizan a canRead para que los lectores bloqueados puedan avanzar.
def reader_lock():
with mutex:
while writing:
canRead.wait() (1)
readers += 1
canRead.notify() (2)-
Espera si hay escritores.
-
Para que puedan entrar otros lectores.
A la salida los lectores verifican si ya no quedan otros lectores, si es así señalizan para que puedan entrar los escritores bloqueados.
def reader_unlock():
with mutex:
readers -= 1
if not readers:
canWrite.notify() (1)-
Si es el último lector desbloquea a los escritores bloqueados.
Los escritores se bloquean en la variable canWrite si hay otros lectores o un escritor. Cuando la condición sea falsa podrán entrar y asignarán True a writing para bloquear a los siguientes lectores y escritores.
def writer_lock():
with mutex:
while writing or readers:
canWrite.wait() (1)
writing = True-
Espera si hay lectores o escritores.
Cuando el escritor sale señaliza a lectores o escritores, cualquiera de ellos podrá entrar a continuación.
def writer_unlock():
with mutex:
writing = False
canRead.notify() (1)
canWrite.notify() (1)-
Señaliza a lectores y escritores.
La última parte –la señalización a canRead y canWrite– puede modificarse para dar prioridad a lectores o escritores. Una forma de hacerlo es verificar la cola de bloqueados en cada variable de condición. Si se quiere dar prioridad a los lectores se verifica canRead y si tiene procesos bloqueados se señaliza solo a ella. Lo mismo puede hacerse con canWrite para dar prioridad a los escritores.
Aunque el escritor que sale dé prioridad a otro escritor, los escritores pueden sufrir inanición si no dejan de llegar nuevos lectores mientras hay otros en la sección crítica. Se puede asegurar la espera limitada de escritores si antes de entrar los lectores verifican si hay algún escritor bloqueado en canWrite:[10]
def reader_lock():
with mutex:
while writing or not empty(canWrite):
canRead.wait()
readers += 1
canRead.notify()En Java no se pueden usar dos variables de condición por lo que hay que recurrir al notifyAll para desbloquear a lectores y escritores (código completo). Se necesitan dos variables, el contador de lectores (readers) y una booleana que indicará si hay un escritor en la sección crítica (writing).
Los lectores solo se bloquean si hay un escritor, cuando entran hacen el notifyAll para que puedan entrar otros lectores que bloqueados en wait (también despertará a los escritores, que volverán a bloquearse inmediatamente).
synchronized void readerLock() {
while (writing) {
wait();
}
readers++;
notifyAll();
}El último lector en salir debe hacer el notifyAll para que puedan entrar los escritores bloqueados.
synchronized void readerUnlock() {
readers--;
if (readers == 0) {
notifyAll();
}
}Los escritores quedan bloqueados si hay otro escritor o lectores en la sección crítica.
synchronized void writerLock() {
while (writing || readers != 0) {
wait();
}
writing = true;
}El escritor que sale señaliza para que puedan entrar los siguientes lectores y escritores.
synchronized void writerUnlock() {
writing = false;
notifyAll();
}No se puede decidir ni conocer a priori si entrarán lectores o un escritor. Depende de cuál se ejecute primero, no está definido por la política de las colas de espera y depende del scheduler. Al igual que el anterior, este algoritmo da prioridad a los lectores. Si se desea que los escritores tengan prioridad se puede agregar un contador de número de escritores esperando y hacer que los lectores se bloqueen en la entrada si este contador es mayor que cero.
Por ejemplo:
synchronized void readerLock() {
while (writing || waiting > 0) {
wait();
}
readers++;
notifyAll();
}Con la solución con semáforos de los filósofos cenando aprendimos los problemas de eficiencia e interbloqueos provocados por un diseño descuidado. Planteado de forma correcta, el algoritmo con monitores es más simple y menos propenso a sufrir los problemas de semáforos. Debido a la exclusión mutua entre métodos, hay más libertad para verificar y modificar las variables compartidas sin la preocupación de provocar condiciones de carrera o interbloqueos. Pero hay que ser meticulosos en verificar si se cumplen las condiciones después de que un hilo fue desbloqueado.
El caso de los filósofos es otro ejemplo notable –como el de barreras– de la simplicidad que aportan los monitores. En los algoritmos con semáforos casi todo el código se ejecutaba dentro de una sección crítica, la excepción eran las operaciones bloqueantes de semáforos (i.e. los wait de sincronización) que deben estar fuera de la sección crítica para evitar interbloqueos. Ese problema ya no existe con las variables de condición, el proceso que se bloquea automáticamente libera el monitor.
Puede diseñarse un clase monitor para toda la mesa: los filósofos deben llamar a sus métodos para tomar y soltar los tenedores (pick y release respectivamente). El algoritmo simplificado en Java es el siguiente (código completo):
class Table {
boolean forks[];
synchronized void pick(int l, int r) {
while (! forks[l] || ! forks[r]) {
wait();
}
forks[l] = false;
forks[r] = false;
}
synchronized void release(int l, int r) {
forks[l] = true;
forks[r] = true;
notifyAll();
}
}El array forks mantiene el estado de cada tenedor, true si está disponible. El método pick es simple: si ambos están disponibles los toma poniendo en false al estado de los dos, caso contrario llama a wait para bloquearse hasta que sus vecinos liberen los tenedores. La liberación de ambos tenedores (release) consiste en marcarlos como libres y señalizar por si hay filósofos esperando por alguno de los tenedores que acaba de liberar.
El algoritmo cumple los requisitos de filósofos, es óptimo y no produce interbloqueos porque no hay retención y espera. La simplicidad de este algoritmo comparado con el de semáforos es también notable.
A pesar de su simplicidad se puede observar otra vez la potencial ineficiencia, la tormenta de procesos desbloqueados provocada por el notifyAll. Cada vez que un filósofo deja sus tenedores despierta a todos, aunque estén bloqueados esperando por tenedores diferentes. Para desbloquear selectivamente se necesitan diferentes variables de condición, pero el monitor nativo de Java no lo permite. Se pueden usar las clases de sincronización de Lock y las variables de condición asociadas que se obtienen con lock.newCondition().
El siguiente es un algoritmo con diferentes variables de condición (código en Java, equivalente en Python). El array forks ahora se usa para indicar cuántos tenedores están disponibles para cada filósofo (inicialmente dos). Cuando un filósofo toma los tenedores decrementa los disponibles de sus vecinos y los incrementa cuando los libera.
CanEat es un array de variables de condición para bloquear a los filósofos que no tienen los dos tenedores disponibles. Las variables left y right representan a los vecinos de un filósofo. El vecino de la izquierda del filósofo0 es filósofo4 y filósofo1 el de la derecha[11].
Cada variable de condición del array canEat corresponde a un filósofo, cuando estos dejan los tenedores señalizan solo a los vecinos que tienen los dos tenedores disponibles. Si los filósofos están bloqueados serán despertados, en caso contrario la señal es ignorada.
def pick():
with mutex:
while forks[i] != 2:
canEat[i].wait()
forks[left] -= 1
forks[right] -= 1
def release():
with mutex:
forks[left] += 1
forks[right] += 1
if forks[left] == 2: (1)
canEat[left].notify()
if forks[right] == 2: (1)
canEat[right].notify()-
Solo señaliza a sus vecinos que tienen los dos tenedores libres.
Los monitores aseguran la ejecución atómica de sus procedimientos –los serializan–. Esta característica dificulta implementaciones eficientes para multiprocesamiento. No hay muchos lenguajes modernos con los que comparar las diferencias entre semáforos y monitores nativos, pero al menos podemos intentarlo con Java. Es uno de los lenguajes más usados, es eficiente gestionando hilos y su modelo de memoria está bien definido.
Para comparar los tiempos se usaron los programas de ejemplos de mutex en C con POSIX Threads y los tres mecanismos de exclusión mutua de Java: la clase Lock, Semaphore y con un método synchronized explicado más arriba. Para obtener datos más fiables se hicieron con cien millones de iteraciones en lugar de los diez millones de los ejemplos anteriores.
El siguiente gráfico muestra los tiempos de reloj en segundos de cada uno de los programas:
Puede sorprender que todos los tiempos de Java sean considerablemente inferiores a la mejor implementación posible en C (POSIX Threads con mutex de las mismas librerías). Esto se debe a las optimizaciones –con técnicas que estudiamos en spinlocks– de los mecanismos de sincronización en la máquina virtual de Java (explicados más adelante)
Los demás tiempos en Java son muy similares, no sorprende, ya que comparten código e infraestructura de la máquina virtual. La clase Lock es la que mejor resultados obtiene porque está optimizada para exclusión mutua. Pero los tres mecanismos son muy similares en eficiencia.
|
Note
|
Implementación de monitor nativo en Java
La eficiencia de la exclusión mutua de los monitores en Java se debe a la implementación sofisticada de la máquina virtual con técnicas que vimos antes: instrucción CAS, spinlocks, spin then block y bloqueo de hilos (usando las librerías de hilos estándares de cada sistema operativo). La entrada a la sección crítica de métodos o bloques synchronized está gestionado por tres colas diferentes, un hilo puede estar solo en una de ellas:
Los hilos bloqueados en el wait del monitor se añaden a la cola WaitSet, el notify o notifyAll simplemente transfieren el o los hilos de esta cola a cxq o EntryList. |
Las barreras son un buen ejemplo para comparar la eficiencia entre semáforos y monitores porque además de exclusión mutua incluyen sincronización. Para hacer las mediciones se ejecutaron los programas con cien mil fases sin demoras entre ellas.
El gráfico muestra dos grupos: a la izquierda los tiempos con programas en C y POSIX Threads, a la derecha implementados con Java. La barra azul en cada grupo (izquierda) representa los tiempos de ejecución con semáforos (vistos en [sync_barrier]), la barra roja con monitores.
En ambos casos la implementación con monitores es la más eficiente. Incluso con POSIX Threads que no cuenta con monitores nativos, sino construidos programáticamente. Además de ser más eficientes, los algoritmos con monitores son más simples que los de semáforos.
La mayor parte de la sincronización se hace dentro de una sección crítica, con semáforos (o mutex) los procesos deben salir de ella antes de bloquearse. Con monitores no hace falta hacerlo explícitamente, las variables de condición están diseñadas o optimizadas para estas situaciones.
Este ejemplo muestra otra vez las ventajas de los monitores. Facilitan el diseño de algoritmos más sencillos y menos propenso a errores y, con el uso apropiado, son más eficientes.
|
Tip
|
En algunos casos merece la pena diseñar e implementar los algoritmos con el patrón de monitores, aún en lenguajes que no tienen construcciones sintácticas o soporte nativo de monitores. |
En el algoritmo de filósofos se planteó el problema de que con la variable implícita nativa del monitor se despertaba a todos los procesos. La solución fue usar variables explícitas para despertar solo al que corresponde. Pero ¿vale la pena complicar el algoritmo por la mejora que se obtiene?
Para poder comparar se eliminaron las esperas en comer y pensar, cada proceso tomará y dejará los tenedores sin demoras. Para que las mediciones sean más fiables se subió el número de operaciones comer a un millón para cada filósofo.
El gráfico siguiente muestra los tiempos de CPU y real de ambas versiones, solo con monitores nativos (native, en azul a la izquierda) y con las variables de condición de la clase Lock (en rojo, a la derecha):
La diferencia es mínima, despreciable, a favor de la implementación con variables de condición. Parece lógico que es así porque son solo cinco procesos. Para comprobarlo hice pruebas con 5, 10, 20, 50 y 100 hilos (o filósofos). Sus tiempos son los siguientes:
Los resultados son contraintuitivos, a medida que aumenta el número de hilos la solución con la variable nativa tiene mejor comportamiento relativo que el algoritmo con varias variables y colas. Las optimizaciones meticulosas de la máquina virtual tienen mucho que ver. En todo caso, es contraproducente optimizar prematuramente basado en suposiciones, sobre todo en programación concurrente.
Los semáforos no proveen una construcción estructurada que encapsule métodos y variables modificadas concurrentemente. Los monitores se diseñaron para solventar esta deficiencia, son una abstracción más estructurada que facilita el diseño de algoritmos de sincronización. No todos los lenguajes implementan la definición original de Hoare, pero prácticamente todos ofrecen los mecanismos para implementarlos metodológicamente: mutex y variables de condición.
En este capítulo hemos visto cómo diseñar algoritmos de sincronización basados tanto en monitores implementados a nivel sintáctico –como en Java– como los construidos por el programador. Puede parecer que la serialización impuesta por los monitores provocan ineficiencias importantes, pero vimos que no siempre es así. En algunos problemas –como las barreras– los monitores no solo permiten algoritmos concurrentes más simples, también más eficientes.
Los monitores, como los semáforos, carecen de una característica deseable en concurrencia: la comunicación entre procesos. Este problema lo resuelven los mensajes o canales, el tema del próximo capítulo.
-Java.png){kind=link}