El concepto de semáforos fue el primero en solucionar problemas de sincronización sin espera activa. Lo inventó Edsger W. Dijkstra a finales de la década de 1960 ([Dijkstra74]), aunque las primeras ideas aparecieron a principios de la misma década ([Dijkstra35]). Está inspirado en las señales visuales ferroviarias[3] que indican si un tren está habilitado para entrar en una vía. Es una construcción sencilla y eficiente que permite solucionar problemas genéricos de sincronización entre procesos.
Los mecanismos de sincronización vistos hasta ahora no requieren la colaboración del sistema operativo, funcionan directamente sobre el hardware desnudo. En cambio, los semáforos se implementan habitualmente como servicios del núcleo de los sistemas operativos. Estos tienen la capacidad de bloquear y planificar para ejecución de los procesos e hilos. Bloquear a un proceso hasta que pueda continuar su ejecución no necesita de funcionalidades adicionales sofisticadas, los sistemas operativos hacen lo mismo para todas las operaciones de entrada-salida. En el caso de semáforos, los procesos se bloquean o ejecutan condicionados únicamente por el valor que tiene una variable entera. Una abstracción tan simple como potente.
Un semáforo es una construcción definida por una variable entera, el valor del semáforo, que puede tomar valores no negativos; y una cola de procesos bloqueados en el semáforo. La estructura es similar a la siguiente:
struct Semaphore {
unsigned value;
Queue q;
}Un semáforo puede ser inicializado con un valor no negativo, el siguiente pseudocódigo indica que el valor del semáforo (la variable value) es inicializada a 1:
Semaphore s = 1
Además de la estructura de datos, los semáforos se componen de dos primitivas fundamentales: P (de la contracción prolaag del holandés proberen te verlagen, que significa intentar decrementar) y V (del holandés verhoog o verhogen, que significa incrementar).
| P |
Si el contador es mayor que cero lo decrementa, caso contrario bloquea al proceso que la llamó. Actualmente es más conocida como wait, acquire, o lock. |
| V |
Si hay algún proceso bloqueado en el semáforo, lo desbloquea. En caso contrario, incrementa el valor de la variable. Esta operación es más conocida como signal, release, o post. |
El algoritmo de ambas[4]:
def wait(s):
if s.value > 0:
s.value -= 1 (1)
else:
add(process, s.queue)
block(process) (2)-
Si es mayor que cero, se decrementa el valor del semáforo.
-
Si es cero, se bloquea al proceso que llamó a wait.
def signal(s):
if empty(s.queue):
s.value += 1 (1)
else:
process = get(s.queue)
sched(process) (2)-
Si no hay procesos bloqueados en la cola del semáforo, se incrementa su valor.
-
Caso contrario, se desbloquea a un proceso.
Las implementaciones de semáforos suelen incluir otras operaciones:
-
Asignar un valor inicial al semáforo.
-
Obtener el valor del semáforo.
-
Intentar wait solo si no produce bloqueo del proceso (usualmente llamada try_lock).
La implementación de exclusión mutua con semáforos es trivial. Se inicia el semáforo con 1, el preprotocolo es la llamada a wait, el posprotocolo a signal:
Semaphore s = 1 ... s.wait() critical_section() s.signal() ...
Cuando el primer proceso entre a la sección crítica decrementará su valor y continuará. Si otro proceso desea entrar, el valor de value será cero, por lo que se bloqueará hasta que el primero ejecute el signal.
Los programas de ejemplo incluyen la solución del contador en C con semáforos POSIX, Python y Java usando semáforos.
El valor del semáforo puede interpretarse como un indicador del número de recursos disponibles –también denominado permisos (permits)–, indica el número de llamadas que se pueden hacer a wait sin provocar el bloqueo del proceso. En exclusión mutua interesa que solo haya un proceso en la sección crítica, así pues, el valor inicial debe ser 1.
Se pueden programar mecanismos más complejos de sincronización usando valores iniciales diferentes. Supongamos un sistema con N procesadores, para evitar cambios de contextos innecesarios se limita a un máximo de N procesos dentro de una sección del programa: solo hay que inicializar el valor del semáforo con N. Este tipo de uso de semáforos, donde se permiten más de uno y hasta N procesos en secciones críticas, se denominan multiplexes.
La definición anterior de semáforos permite valores cero y positivos, son denominados semáforos generales o contadores. Si solo permiten valores 0 y 1, se denominan semáforos binarios. Los binarios son equivalentes a los generales, permiten resolver los mismos problemas (con algunas líneas más de código).
Con el algoritmo de Barz se pueden simular semáforos generales ([Barz]). Este algoritmo requiere dos semáforos binarios (mutex y gate) y una variable entera (value).
Las funciones generalWait y generalSignal son las emulaciones genéricas de wait y signal respectivamente; k es el valor inicial del semáforo. El semáforo mutex asegura exclusión mutua para el acceso a value. El semáforo gate se usa para controlar qué procesos deben bloquearse o desbloquearse según el valor de value.
BinarySemaphore mutex = 1
BinarySemaphore gate = 1
value = k
def generalWait():
gate.wait() (1)
mutex.wait()
value -= 1
if value > 0:
gate.signal() (2)
mutex.signal()
def generalSignal():
mutex.wait()
value += 1
if value == 1:
gate.signal() (3)
mutex.signal()-
Si no es el primer proceso en entrar a la sección crítica, debe esperar a ser autorizado por el proceso anterior.
-
Permite que entre otro proceso si el valor es positivo.
-
Antes estaba en cero, permite que entre otro proceso.
Los semáforos mutex, también llamados locks, son semáforos binarios –o equivalentes– optimizados para ser usados con exclusión mutua[5], con restricciones y propiedades adicionales:
-
Son inicializados a 1.
-
Se añade el concepto de propiedad, solo el proceso que hizo el wait puede hacer luego el signal.
-
Algunos sistemas permiten que el mismo hilo haga varios wait, si ya es el propietario del lock continúa su ejecución. Este tipo de semáforos mutex se denominan reentrantes.
Los mutex son muy comunes y los recomendados para exclusión mutua, hay lenguajes como Go que no tienen funciones nativas de semáforos generales, solo mutex y lock. Como con spinlocks, a la operación wait se la suele llamar lock, y unlock a signal.
Las operaciones y uso son idénticas a la exclusión mutua con semáforos generales. Solo cambian los nombres de las funciones, y que los mutex son inicializados automáticamente:
Mutex mutex ... mutex.lock() critical_section() mutex.unlock() ...
|
Note
|
Mutex de POSIX Threads
En C se pueden usar los mutex de las librerías POSIX Threads. Las primitivas son pthread_mutex_lock y pthread_mutex_unlock (programa en C), no son reentrantes. Go lo ofrece en Mutex y Locker del paquete sync (código fuente). En Java se puede usar la clase ReentrantLock de java.util.concurrent.locks. Python tiene clases similares, threading.Lock y threading.RLock.[6] Además de las llamadas tradicionales a acquire y release se puede usar con la cláusula with: for i in range(MAX_COUNT/THREADS):
with mutex:
counter += 1
|
Cada semáforo tiene asociado una cola de procesos bloqueados y la política de gestión de esta cola es fundamental. Si la cola es FIFO, aseguran espera limitada y equidad; estos semáforos se denominan semáforos fuertes. Por el contrario, se denominan semáforos débiles (weak semaphores) si los procesos se seleccionan aleatoriamente.
|
Note
|
Semáforos en Unix y Linux
|
La sección crítica es una abstracción conveniente y sencilla para resolver la competencia de recursos, otro problema común es la coordinación del orden de ejecución de operaciones ([Ben-Ari]). Supongamos dos procesos P y Q, la instrucción Qj debe ejecutarse solo después de la instrucción Pi, se denota como Pi < Qj. Para que se cumpla esta condición, antes de Qj hay que asegurar:
-
Que continua la ejecución si Pi ya se ejecutó.
-
Que se bloquea a Q si Pi todavía no se ejecutó, y se desbloquea una vez que se haya ejecutado.
Para resolverlo se necesita un semáforo (contador o binario) inicializado a cero. Inmediatamente después de Pi, P ejecuta signal sobre dicho semáforo. Q llama a wait inmediatamente antes de Qi. Los programas serán similares al siguiente ejemplo:
Semaphore sync = 0 P Q ... ... Pi sync.wait() sync.signal() Qj ... ...
Este algoritmo con un único semáforo solo permite sincronizar dos procesos, y solo uno puede esperar por el otro.
A veces es conveniente desarrollar programas concurrentes que se sincronizan por fases. Los procesos deben esperar que todos acaben la fase actual y comenzar la siguiente simultáneamente. Esta coordinación se logra de forma muy parecida al ejemplo anterior: poniendo barreras de sincronización al final e inicio de cada fase.
- Barrera
-
Es un mecanismo de sincronización que obliga a procesos concurrentes (o distribuidos) a esperar a que todos hayan llegado a un punto determinado. Solo podrán continuar cuando todos los procesos hayan llegado a una barrera. El conjunto de los puntos de sincronización se denomina barrera ([Taunbenfeld]).
Una barrera binaria es una extensión del ejemplo anterior, donde solo uno de los procesos debía esperar por el otro. En cambio, una barrera hace que ambos deban esperar a que el otro acabe una fase para avanzar a la siguiente; además, las barreras pueden usarse cíclicamente.
El algoritmo de barreras para dos procesos es trivial, hacen falta dos semáforos binarios inicializados a cero. El valor de cada semáforo indica si su proceso correspondiente llegó a la meta. Cada proceso ejecuta signal en su semáforo para indicar que llegó al final de una fase, y luego wait en el semáforo del otro proceso.
Semaphore arrived_p = 0
Semaphore arrived_q = 0
P Q
... ...
arrived_p.signal() arrived_q.signal()
arrived_q.wait() arrived_p.wait()
... ...
arrived_p.signal() arrived_q.signal()
arrived_q.wait() arrived_p.wait()
... ...
La intención de uso de barreras genéricas para un número indeterminado de procesos es poder implementar sincronizaciones cíclicas como la siguiente:
while True:
do_phase()
barrier(n)Después de do_phase cada proceso esperará a que los demás hayan llegado al mismo punto, solo así podrán continuar con la siguiente. La misma barrera puede ser reusada cíclicamente, también para un número indeterminado de iteraciones.
Estas barreras no pueden implementarse igual que las binarias. Los semáforos son recursos costosos, requieren colas y tiempos relativamente elevados para la inicialización. No tiene sentido tener un array de N semáforos y hacer N operaciones de wait y signal. Hay que solucionarlo con un número limitado de semáforos, y que no requiera que el número de operaciones de cada proceso sea proporcional al número de procesos concurrentes.
El siguiente algoritmo de barreras cíclicas usa dos semáforos binarios, arrivals y departures, y una variable counter incrementada atómicamente[7]. Si no se dispone de este tipo de operaciones atómicas, hay que usar un mutex adicional para asegurar exclusión mutua en las modificaciones a counter (código en Python y en Java):
Semaphore arrival = 1
Semaphore departure = 0
counter = 0
def barrier(n):
arrival.wait()
getAndAdd(counter, 1)
if counter < n:
arrival.signal() (1)
else:
departure.signal() (2)
departure.wait() (3)
getAndAdd(counter, -1)
if counter > 0:
departure.signal() (4)
else:
arrival.signal() (5)-
Si no llegaron todos los procesos, permite la llegada de otro.
-
Si llegaron todos, autoriza la salida de un proceso.
-
Espera la autorización para continuar.
-
Si no salieron todos, autoriza la salida del siguiente.
-
Si llegaron todos, comienza nuevamente el ciclo de llegadas.
|
Note
|
Algunos lenguajes implementan barreras similares en sus librerías de concurrencia. En Java y Ruby la clase CyclicBarrier, en Go el tipo WaitGroup de sync, en Python threading.Event puede adaptarse fácilmente para el mismo propósito. Hay una propuesta de estandarización de la misma construcción para ISO C++ ([Mackintosh]) juntamente con Latches (mecanismo que bloquea a los procesos hasta que su contador se hace cero). |
El problema de los productores-consumidores es un ejemplo clásico de sincronización de orden de ejecución. Está presente en casi todos los mecanismos de comunicación, las tuberías entre procesos y comandos[8], la E/S a dispositivos, comunicaciones por red, etc.
Hay dos tipos de procesos:
- Productores
-
Produce un nuevo elemento que será transmitido a los consumidores.
- Consumidores
-
Recibe y consume los elementos transmitidos desde los productores.
Hay dos tipos de productores-consumidores:
- Síncronos
-
Cuando se produce un elemento, este debe ser consumido para que el productor pueda continuar su ejecución.
- Asíncronos
-
El canal de comunicación tiene capacidad de almacenamiento, un buffer, por lo que no es necesario que los productores esperen a que cada elemento sea consumido. Los productores agregan los elementos a una cola y los consumidores obtienen el primer elemento de esta.
El segundo caso es el más habitual. El uso de un buffer permite que productores y consumidores avancen a su propio ritmo; pero requiere sincronización para hacer que los consumidores esperen si el buffer está vacío, y los productores si el buffer está lleno. Los procesos pueden ser considerados cíclicos, ambos ejecutan un bucle donde añaden o quitan elementos del buffer:
while True:
data = produce()
buffer.add(data)while True:
data = buffer.get()
consume(data)Aunque no existen las memorias infinitas, ni se puede confiar en que las velocidades relativas de los productores evitarán que el buffer supere un tamaño razonable, es un primer paso para la implementación del algoritmo más general.
Como el buffer no está limitado el algoritmo no debe comprobar que haya espacio suficiente. Solo debe bloquear a los consumidores si el buffer está vacío, y desbloquearlos cuando hay elementos disponibles. Además del buffer compartido se requieren dos semáforos: un mutex para asegurar exclusión mutua al insertar o quitar elementos y otro de sincronización (notEmpty) para bloquear a los consumidores si el buffer está vacío.
Queue buffer
Semaphore mutex = 1
Semaphore notEmpty = 0Los siguientes son los algoritmos para los productores y consumidores:
while True:
data = produce()
mutex.wait()
buffer.add(data) (1)
mutex.signal()
notEmpty.signal() (2)-
Agrega un elemento dentro de una sección crítica.
-
Señaliza el semáforo, su valor será el número de elementos en el buffer.
while True:
notEmpty.wait() (1)
mutex.wait()
data = buffer.get() (2)
mutex.signal()
consume(data)-
Se bloquea si el buffer está vacío, si no es así decrementa y obtiene el siguiente elemento. El valor del semáforo contador notEmtpy siempre se corresponde con el número de elementos disponibles en el buffer.
-
Obtiene el siguiente elemento de la cola.
En el código en Python se puede consultar la implementación completa. Hay dos clases –Producer y Consumer– que implementan el algoritmo de productores y consumidores respectivamente. Se crean dos hilos productores (variable PRODUCERS) y dos consumidores (CONSUMERS). Los productores producen 1 000 elementos (TO_PRODUCE) cada uno y acaban. Para el buffer se usa una lista nativa de Python, se agregan elementos con append y se obtiene el primer elemento con pop(0).
El algoritmo anterior puede ser extendido para que funcione con un tamaño de buffer limitado. Así como los consumidores se bloquean si no hay elementos en el buffer, los productores deben hacer lo mismo si no quedan posiciones libres. Se necesita un semáforo contador adicional (notFull) cuyo valor indicará el número de posiciones libres, por lo que se inicializa con el tamaño del buffer (BUFFER_SIZE).
Queue buffer
Semaphore mutex = 1
Semaphore notEmpty = 0
Semaphore notFull = BUFFER_SIZELos siguientes son los algoritmos para cada proceso, solo se requiere una línea adicional en cada uno (el código en Python):
while True:
data = produce()
notFull.wait() (1)
mutex.wait()
buffer.add(data)
mutex.signal()
notEmpty.signal()-
Se bloquea si notFull vale cero, caso contrario lo decrementará y añadirá un nuevo valor.
while True:
notEmpty.wait()
mutex.wait()
data = buffer.get()
mutex.signal()
notFull.signal() (1)
consume(data)-
Incrementa el semáforo para que un productor pueda añadir otro elemento.
|
Note
|
El modelo productor-consumidor es muy común en informática, las tuberías y colas son construcciones muy útiles. La mayoría de lenguajes ofrecen una implementación nativa o por librerías. Por ejemplo, la clase ArrayBlockingQueue en Java, Queue en Python (queue partir de Python 3) y Ruby. Los mensajes nativos de Go son productores-consumidores que pueden ser síncronos o asíncronos (los estudiamos en el capítulo [channels]). |
La técnica de sincronización anterior con dos semáforos se denomina semáforos partidos (split semaphores). Se llaman así cuando se usan dos o más semáforos cuya suma es una constante, en este caso el invariante es:
notEmpty + notFull = BUFFER_SIZE
Si la constante es igual a uno la técnica se denomina semáforos partidos binarios.
En la sección crítica las operaciones wait y signal son ejecutadas por el mismo proceso y en ese orden, no son semáforos partidos. Sin embargo, en el algoritmo de productores-consumidores con buffer limitado se usan dos semáforos y las llamadas a wait y signal se hacen desde diferentes hilos. Los semáforos partidos permiten que los procesos esperen por eventos que se producen en otros.
En [readers_writers] del capítulo [spinlocks] vimos cómo resolver un problema también muy habitual, relajando las condiciones de la exclusión mutua con las siguientes condiciones:
-
Se permite más de un lector en la sección crítica.
-
Mientras haya un lector en la sección crítica no puede entrar ningún escritor.
-
Los lectores no pueden entrar si hay un escritor en la sección crítica.
-
Solo puede haber un escritor en la sección crítica.
El algoritmo clásico de lectores-escritores se puede implementar con semáforos binarios o mutex, siempre que permitan que un proceso que no hizo el wait pueda hacer un signal. En el ejemplo en Python se usa la clase threading.Lock, permite que cualquier hilo llame a release aunque no haya ejecutado el acquire.
readers = 0 (1)
Semaphore writer = 1 (2)
Semaphore mx = 1 (3)-
Contador de lectores en la sección crítica.
-
Asegura la exclusión mutua entre escritores y entre escritor y lectores.
-
Se usa con dos propósitos: 1) asegurar exclusión mutua para verificar y modificar la variable readers; 2) como barrera (el primer lector bloqueará a los siguientes si hay un escritor en la sección crítica).
Las entradas y salidas de escritores son idénticas a las de exclusión mutua:
def writer_lock():
writer.wait()
def writer_unlock():
writer.signal()Si un lector no es el primero, puede entrar a la sección crítica. Si no hay ningún lector, espera en writer a que no haya ningún escritor. Como no hace el signal en el semáforo mx, los demás lectores quedarán bloqueados hasta que el primer lector se desbloquee de writer.
def reader_lock():
mx.wait()
readers += 1
if readers == 1:
writer.wait() (1)
mx.signal()-
Si es el primer lector, espera a que no haya ningún escritor.
def reader_unlock():
mx.wait()
readers -= 1
if readers == 0:
writer.signal() (1)
mx.signal()-
Si es el último lector, libera writer, podrán entrar escritores.
El algoritmo anterior da prioridad a los lectores y no asegura espera limitada a los escritores. Cuando entra un lector los escritores tendrán que esperar hasta que salga el último, pero los lectores podrán seguir entrando sin dejar paso al escritor. Es decir, se pueden generar esperas infinitas. Para evitarlas hay que asegurar que los lectores esperan si un escritor desea entrar.
Se usa un semáforo adicional, entry, que bloquea a los nuevos lectores cuando el primer escritor hace un wait. El siguiente es el algoritmo equitativo, la función reader_unlock es la misma, cambian las otras tres (código fuente completo):
...
Semaphore entry = 1
def reader_lock():
entry.wait()
mx.wait()
readers += 1
if readers == 1:
writer.wait()
mx.signal()
entry.signal()
...
def writer_lock():
entry.wait()
writer.wait()
def writer_unlock():
writer.signal()
entry.signal()La mayor ineficiencia de este algoritmo está en la entrada de lectores, se hacen dos wait sobre dos semáforos, entry y mx. En 2013, Vlad Popov y Oleg Mazonka propusieron un algoritmo más eficiente ([Popov]), los lectores solo hacen wait sobre un semáforo (el código completo en Python).
|
Note
|
POSIX Threads ofrece lectores-escritores con las funciones pthread_rwlock_*, en Java la clase ReentrantReadWriteLock, en Go el tipo RWMutex del paquete sync. |
Es un modelo muy estudiado en el área de la programación concurrente, fue inventado como ejercicio por Dijkstra en 1965 y luego formalizado por Hoare. No es un problema cuya solución tenga un uso práctico directo, pero es lo suficientemente simple y propone desafíos interesantes. Es objeto habitual de estudio y comparación entre las diferentes mecanismos de sincronización concurrentes.
Se trata de cinco filósofos sentados en una mesa en la que también hay cinco tenedores[9], uno a cada lado de los filósofos.
Cada filósofo es un proceso que realiza solo dos actividades: pensar o comer. El algoritmo general de cada uno de ellos:
def philosopher():
while True:
think()
pick() (1)
eat()
release() (2)-
Asegura que puede tomar los dos tenedores, el de la izquierda y el de la derecha
-
Libera ambos tenedores.
Cada filósofo necesita dos tenedores para comer y solo puede tomar los que tiene a su lado. Para que el programa sea correcto se deben cumplir los siguientes requisitos:
-
Un filósofo solo puede comer si tiene los dos tenedores.
-
Exclusión mutua, un tenedor solo puede ser usado por un filósofo a la vez.
-
Se debe asegurar progreso.
-
Se debe asegurar espera limitada.
-
Debe ser eficiente. Si no hay competencia por un tenedor, este debe poder ser usado por uno de sus dos filósofos vecinos.
Identificamos a los filósofos y tenedores con un índice de 0 a 4 (es decir, de 0 a N-1). El tenedor a la izquierda del filósofo0 será el tenedor0, el de su derecha el tenedor1. Así sucesivamente, hasta el último filósofo4, que a su izquierda tendrá el tenedor4 y a su derecha el tenedor0.
Una primera solución es asegurar exclusión mutua a toda la mesa, solo un filósofo puede comer a la vez. Es un problema de exclusión mutua, se requiere un único semáforo mutex (table):
Semaphore table = 1
def philosopher():
while True:
think()
table.wait()
eat()
table.signal()Esta solución es ineficiente: aunque hay tenedores para que puedan comer dos filósofos simultáneamente, solo uno podrá hacerlo. Una mejor solución es asegurar exclusión mutua por cada tenedor, para ello se necesita un array de cinco semáforos mutex, uno por tenedor. El índice i identifica a cada filósofo, cada proceso intentará tomar primero el tenedor de su izquierda (también es i) y luego el de su derecha (corresponde a (i + 1) % 5).
Las funciones pick y release tomarán y soltarán los tenedores respectivamente, por conveniencia se define la función right que retorna el índice del tenedor de la derecha (el tenedor de la izquierda del filósofoi es simplemente tenedori):
Semaphore forks[5] = [1, 1, 1, 1, 1]
def philosopher(i):
while True:
think()
pick(i)
eat()
release(i)
def right(i):
return (i+1) % 5
def pick(i):
forks[i].wait()
forks[right(i)].wait()
def release(i):
forks[i].signal()
forks[right(i)].signal()Antes de comer cada filósofo hace wait sobre los dos tenedores que le corresponden, primero al de la izquierda y luego al de la derecha. Si alguno de ellos está ya tomado, quedará bloqueado hasta que el filósofo que lo tiene lo libere y ejecute el signal correspondiente. Sin embargo, tiene un problema importante[10]: si todos intentan comer simultáneamente cada uno tomará su tenedor de la izquierda, cuando lo intenten con el de la derecha quedarán bloqueados porque ya habrá sido tomado por su vecino.
Una secuencia de instrucciones que lleva a este estado podría ser la siguiente: cada filósofo toma el tenedor de su izquierda, la ejecución se intercala o se ejecuta en paralelo (recordad que el problema es equivalente):
fork[0].wait()
fork[1].wait()
fork[2].wait()
fork[3].wait()
fork[4].wait()
Ahora cada uno de ellos intenta tomar el tenedor de su derecha:
fork[1].wait()
fork[2].wait()
fork[3].wait()
fork[4].wait()
fork[0].wait() (1)
-
El filósofo4 es el único que hace el wait en orden decreciente.
Todos quedarán bloqueados porque los semáforos mutex están tomados, es un interbloqueo, como vimos en el capítulo [algorithms].
Los interbloqueos se pueden producir cuando hay competencia por recursos de cualquier tipo. Dos procesos P y Q necesitan los recursos a y b y los solicitan en orden diferente, como en el siguiente ejemplo:
P Q get(a) get(b) ... ... get(b) get(a)
Ambos procesos quedarán esperando a que el otro libere uno de los recursos, pero el otro no lo hará porque tampoco puede avanzar. No hay progreso, se produce un bucle en el grafo de asignación de recursos. Es lo mismo que puede pasar con el algoritmo anterior de los filósofos, se dice que hay una espera circular.
|
Important
|
Condiciones necesarias para interbloqueo
Para que se puedan producir interbloqueos deben cumplirse las siguientes condiciones necesarias:
|
Para prevenir interbloqueos es suficiente que el algoritmo evite que se presente alguna de las condiciones.
-
La exclusión mutua no se puede evitar, un tenedor solo puede ser usado por un filósofo a la vez.
-
La retención y espera se podría evitar, pero requiere algoritmos de sincronización más complejos que el de exclusión mutua (lo haremos en la solución óptima, más adelante).
-
Se podría hacer que sea apropiativo, si se detecta interbloqueo se quita el tenedor a uno de los filósofos involucrados en la cadena, también requiere un algoritmo más sofisticado.
-
La condición de espera circular es la más sencilla de evitar que se produzca, basta forzar a que todos los procesos soliciten los recursos en el mismo orden, ascendente o descendente.
El culpable de que no se soliciten los tenedores en el mismo orden es el filósofo con el último índice. Al contrario de los demás, que solicitan los tenedores en orden ascendente, el filósofo4 los toma en orden descendente: primero el tenedor4 y luego el tenedor0. Para forzar el mismo orden se puede cambiar la función pick, de forma que el primer wait se haga siempre sobre el tenedor con el índice menor (código en Python):
def pick(i):
if i < right(i):
forks[i].wait()
forks[right(i)].wait()
else:
forks[right(i)].wait()
forks[i].wait()Este algoritmo suele denominarse LR porque hay dos tipos de filósofos, los que toman primero el tenedor de la izquierda (L) y los que lo hacen con el de la derecha (R). No se pueden producir interbloqueos al no cumplirse la condición de espera circular.
Pero el algoritmo no es óptimo, hay situaciones donde podrían estar comiendo dos filósofos pero solo lo hace uno. Si, como vimos antes, todos los filósofos desean comer más o menos simultáneamente puede darse la siguiente secuencia:
fork[0].wait()
fork[1].wait()
fork[2].wait()
fork[3].wait()
fork[0].wait() (1)
fork[1].wait()
fork[2].wait()
fork[3].wait()
fork[4].wait() (2)
-
El filósofo4 que ahora hace el wait en orden decreciente y se bloquea.
-
El filósofo3, el tenedor4 está libre y puede continuar comiendo, todos los demás esperarán, cuando filósofo3 podrá comer el filósofo2, luego filósofo1, etc.
Con cinco filósofos pueden comer hasta dos. Sin embargo, con la secuencia anterior hemos demostrado que hay casos donde el algoritmo no cumple con el mínimo.
Para obtener la solución óptima hay que cambiar el enfoque, en vez de un problema de exclusión mutua hay que tratarlo como una sincronización de orden de instrucciones. Cuando un filósofo desea comer verifica el estado de sus dos vecinos; podrá comer si ninguno de los dos está comiendo. En caso contrario, tendrá que esperar que los vecinos le notifiquen cuando liberen los tenedores.
Se usa el array status para indicar el estado de cada filósofo: pensando (THINKING), que pretende comer (con hambre, HUNGRY) y comiendo (EATING). El array sync de semáforos para sincronizar entre los filósofos, y el semáforo mutex para asegurar exclusión mutua cuando se verifica y manipula el array status.
status[5] = [THINKING,... ,THINKING]
Semaphore sync[5] = [0, 0, 0, 0, 0]
Semaphore mutex = 1La función pick asigna HUNGRY al estado del filósofo y llama a la función canEat, que verifica si ninguno de los vecinos está comiendo. Si no es así, señaliza en su semáforo sync correspondiente, por lo que no se bloqueará en el acquire sobre sync[i] (en la última línea de pick). Pero si alguno de los vecinos está comiendo no se hará el release y el filósofo se bloqueará.
def pick(i):
mutex.acquire()
status[i] = HUNGRY
canEat(i)
mutex.release()
sync[i].acquire()Si ninguno de los vecinos está comiendo canEat asigna EATING al estado de filósofoi y señaliza en su semáforo. A diferencia del algoritmo anterior, las funciones left y right retornan el índice del filósofo vecino (no del tenedor): right es la misma, pero left retorna el índice del vecino –no el tenedor– de la izquierda ((i - 1) % 5, el vecino de la izquierda de filósofo0 es el filósofo4).
def canEat(i):
if status[i] == HUNGRY
and status[left(i)] != EATING
and status[right(i)] != EATING:
status[i] = EATING
sync[i].release()Cuando un filósofo deja de comer debe verificar si sus vecinos están esperando por los tenedores que retenía. Antes de señalizarles también tiene que verificar que el otro vecino de su vecino no está comiendo. Para ello se puede usar la función canEat que precisamente hace eso, lo que cambiará será el valor del argumento i.
def release(i):
mutex.acquire()
status[i] = THINKING
canEat(left(i)) (1)
canEat(right(i)) (1)
mutex.release()-
Se reusa la función canEat para verificar el estado de los vecinos del vecino. Si el filósofo que deja los tenedores es el 1, entonces se llamará con el argumento 0 (el filósofo de la izquierda) y luego con el 2 (el filósofo de la derecha).
Hay que tener en cuenta que las llamadas a canEat se hacen siempre desde dentro de la sección crítica del semáforo mutex, es decir, no se producen condiciones de carrera ni conflictos en las verificaciones y cambios de estado del array status.
Este algoritmo es óptimo (código fuente completo), asegura que si hay tenedores para que coman dos filósofos estos podrán hacerlo sin demora. No hay retención y espera, los filósofos que no pueden comer no retienen ningún tenedor. Sin retención y espera tampoco se puede producir espera circular.
Dado que no se cumplen dos de las condiciones necesarias, no pueden producirse interbloqueos. Cumple con todas los requisitos que impusimos al principio.
|
Note
|
Un bug marciano
El día 4 de julio de 1997 el Mars Pathfinder aterrizó en Marte, se desplegó la nave que sirvió para el viaje y aterrizaje –el SpaceCraft– y a las pocas horas empezó a enviar datos y fotos en alta calidad. Unos días después se detectaron reinicios continuos del ordenador al intentar enviar a la tierra datos meteorológicos y científicos. Los reinicios eran ordenados por la tarea bc_sched, responsable de verificar que las demás tareas se ejecutan correctamente. El procesador era un Power1/RS6000 de IBM, conectado a un bus VME con interfaces para la cámara, la radio y un bus 1553. El bus 1553 tenía dos partes, una usada para navegación espacial (aceleradores, válvulas, sensor solar y escáner de estrellas) y otra para el aterrizaje (acelerómetro y radar de altitud) y los instrumentos científicos: el ASI/MET. El bus 1553, heredado de la sonda Cassini, tenía un modo de funcionamiento síncrono simple: el software controlador y toma de datos se planificaban exactamente cada 0.125 segundos (8 Hz). El sistema operativo era un Unix de tiempo real desarrollado por Wind River, VxWorks, adaptado específicamente al procesador RS600. La arquitectura de software era la siguiente[11]:
Una vez detectados los reinicios se analizaron los datos de debug generados y enviados por bc_sched. El problema era siempre el mismo: bc_dist no completaba su ejecución en el tiempo previsto. Después de 18 horas de simulaciones descubrieron la causa: por la cantidad inesperada de datos que se recogía el sistema estaba más cargado que el mejor caso probado por la NASA. La tarea de baja prioridad ASI/NET accedía a una sección crítica con un wait a un mutex dentro de las funciones del pipe, pero no alcanzaba a salir porque el núcleo asignaba el procesador a las tareas de prioridad intermedia. La tarea bc_dist, de mayor prioridad, también hacía un wait al mismo mutex pero permanecía bloqueada porque ASI/NET no salía de su sección crítica. Así, bc_dist llegaba al final de su período sin acabar, el problema era la inversión de prioridades. |
La inversión de prioridades es un problema que se puede presentar en todos los mecanismos de exclusión mutua en sistemas de multiprogramación con prioridades. Supongamos tres procesos con diferentes prioridades, H de mayor prioridad, I de prioridad intermedia y L de menor prioridad.
L entra en la sección crítica haciendo wait en un semáforo, al poco tiempo H hace wait sobre el mismo semáforo. Antes de que L pueda hacer el signal es quitado del procesador (preempted) por el proceso I de mayor prioridad. H no podrá ejecutarse hasta que I y todos los demás procesos con prioridad intermedia hayan liberado el procesador y permitan que L haga el signal.
Este interbloqueo causado por el scheduler se denomina inversión de prioridades. Aunque H tiene la mayor prioridad, no se puede ejecutar porque comparte recursos con L; que a su vez no se ejecuta porque tiene menor prioridad que I.
El problema era conocido desde hace tiempo en la comunidad científica, pero no hubo formalizaciones ni soluciones hasta 1980 ([Lampson]). Hay varias soluciones:
- Herencia de prioridades (priority inheritance)
-
Antes de bloquear un proceso se verifica la prioridad del que está en la sección crítica, si es menor que la del proceso a punto de bloquearse se le asignará la mayor. Es decir, hereda la mayor prioridad de los procesos bloqueados en el semáforo.
- Maximización de prioridad (priority ceiling)
-
Se define una prioridad suficientemente alta por cada semáforo y se asigna esta prioridad a todos los procesos que operan con él.
- Incremento aleatorio (random boosting)
-
El scheduler sube aleatoriamente la prioridad de los procesos que están en la cola de listos. Si en una vuelta no alcanzó a ejecutar, en la siguiente ronda vuelve a tener la oportunidad. Windows usa este mecanismo ([Microsoft]).
Aunque la más utilizada es herencia de prioridades, no hay un consenso sobre cuál es la mejor solución.
Friends don’t let friends use priority inheritance.
Linus Torvalds se negaba a introducirla en Linux, consideraba que el problema es de programas erróneos, no una cuestión que deba resolver el núcleo. En 2006 Ingo Molnar consiguió introducir soporte para herencia de prioridades en la interfaz FUTEX[12] ([Molnar]), usada para implementar los semáforos POSIX y los mecanismos de sincronización de POSIX Threads, las GLibc fueron adaptadas rápidamente[13].
|
Note
|
El parche
VxWorks permitía configurar en una variable global si se habilitaba o no la herencia de prioridades en los semáforos. Los ingenieros de la NASA habían preferido no arriesgar y la dejaron deshabilitada. Después de estudiar y hacer simulaciones en la Tierra para asegurarse de que los efectos colaterales no eran negativos, se preparó el parche y se envió a la nave en Marte. El problema se resolvió y la misión fue un éxito ([Reeves]). |
Los abstracción de semáforos fue el primer mecanismo formal y útil de sincronización de procesos sin esperas activas. Sigue siendo fundamental y el pilar sobre el que se construyen otros mecanismos. Hemos visto desde su uso trivial para exclusión mutua a algoritmos de sincronización más complejos: barreras, productor-consumidor y lectores-escritores. Estos cuatro modelos a su vez son esenciales para la programación concurrente. Su aprendizaje no solo aporta el conocimiento necesario para reconocer los problemas de concurrencia y las herramientas más adecuadas, saber cómo se construyen esas soluciones permite diseñar soluciones correctas y eficientes para muchos problemas de programación concurrente.
Al haber sido el primer –y más usado– método de sincronización, también sirvió para estudiar los desafíos de la concurrencia, el problema de los filósofos es un clásico. Fue útil para estudiar las diferentes formas de solucionar la sincronización entre procesos y para reconocer las reglas básicas para eludir los interbloqueos.
Finalmente analizamos el fenómeno que se presenta por la compleja interacción de procesos en los sistemas operativos modernos, especialmente en los de tiempo real: la inversión de prioridades.
Los conocimientos adquiridos permitirán enfrentar con bastante facilidad los dos mecanismos más usados en los lenguajes de programación modernos, los monitores y mensajes. Pero antes veremos un tema que raramente se estudia: una interfaz genérica del núcleo del sistema operativo que permite la implementación eficiente de semáforos y otros mecanismos de sincronización.
Linux tiene una interfaz de este tipo, la Fast Userspace Mutex (FUTEX). Aunque está pensada para ser usada por los programadores de librerías, como la GLibc, es muy pedagógico aprender cómo se programan a bajo nivel los mecanismos de sincronización. De esto tratará el siguiente capítulo.
objeto.método() para que sean similares a la mayoría de los ejemplos en Python, programados con las clases de sincronización de threading.
| entre dos comandos en el shell.