Módulo 4: Sincronización: mutex y semáforos

Sincronización: mutex y semáforos

Un productor llena un búfer pequeño y un consumidor lo vacía. Tres semáforos los coordinan sin que nadie gire en vano, y basta invertir dos líneas para que todo se detenga.

35 min

Antes de empezar

  • Condiciones de carrera, sección crítica y exclusión mutua (lección Hilos y condiciones de carrera).
  • Los estados listo y bloqueado, y la cola de listos (lección Procesos y sus estados).

Teoría

Un semáforo es un contador que nunca baja de 0, más una cola de hilos bloqueados. Tiene dos operaciones, y cada una es indivisible:

  • wait(s): si s > 0, le resta 1 y el hilo sigue. Si s = 0, el hilo se bloquea en la cola de s y suelta la CPU.
  • signal(s): si hay un hilo bloqueado en s, despierta al primero: su wait se completa y pasa a la cola de listos; el contador no cambia. Si no hay nadie, le suma 1.

Piensa en el contador como una cantidad de permisos. wait toma uno o espera a que haya; signal devuelve uno y, si alguien espera, se lo entrega directamente.

Un semáforo que empieza en 1 y se usa siempre como wait … signal alrededor de una sección crítica da exclusión mutua: es un mutex.

El búfer acotado tiene N casillas que se usan en círculo. Los productores escriben en la casilla in y los consumidores leen en la casilla out; los dos índices avanzan de uno en uno y vuelven a 0 al final. Escribir una casilla y avanzar in es una sección crítica, igual que counter++. La solución usa tres semáforos:

Semáforo Cuenta Empieza en
empty casillas libres N
full casillas ocupadas 0
mutex permiso para tocar los índices 1 
productor:             consumidor:
  wait(empty)            wait(full)
  wait(mutex)            wait(mutex)
  dejar elemento         sacar elemento
  signal(mutex)          signal(mutex)
  signal(full)           signal(empty)

Ejemplo: s = 1. El hilo A hace wait(s): s pasa a 0 y A sigue. El hilo B hace wait(s): B se bloquea. A hace signal(s): B despierta con el permiso y s se queda en 0.

Predecir

El tablero empieza con Productor rápido: un productor, P1, que fabrica 3 elementos; un consumidor, C1; un búfer de 2 casillas; el código correcto y sin cuanto, así que un hilo conserva la CPU hasta que se bloquea o termina. P1 corre primero.

Responde las dos preguntas del panel Tu predicción antes de ejecutar:

  1. ¿Qué hilo se bloquea primero, y en qué semáforo?
  2. ¿Cuánto vale empty justo después del primer signal(empty) de C1?

Ejecutar

Hilos y búfer

Productores
Consumidores
Elementos por productor
Casillas del búfer
Código del productor

El consumidor siempre hace wait(full) antes de wait(mutex).

Escenarios

Planificación

Sin cuanto, un hilo conserva la CPU hasta que se bloquea o termina. Con cuanto, el temporizador también se la quita.

Tu predicción

¿Cuánto vale empty justo después del primer signal(empty)?

El tablero antes de empezar

Una CPU, una operación por paso. Cada semáforo es un contador con su propia cola.

Búfer

  1. libre in out
  2. libre
  • empty 2
    casillas libres
    Cola Vacía
  • full 0
    casillas ocupadas
    Cola Vacía
  • mutex 1
    permiso para tocar el búfer
    Cola Vacía

Cola de listos

CPU

Libre

  • productor

    Listo

    Elemento 1 de 3

    1. wait(mutex)
    2. dejar elemento
    3. signal(mutex)
    4. signal(full)
  • consumidor

    Listo

    Elemento 1 de 3

    1. wait(mutex)
    2. sacar elemento
    3. signal(mutex)
    4. signal(empty)

Qué pasó en este turno

Pulsa Ejecutar o avanza paso a paso. Aquí verás cada wait y cada signal, y quién se bloquea.

Elementos consumidos

Todavía nadie consumió nada.

Bloqueos

Todavía nadie se bloqueó.

Mientras avanza, fíjate en tres momentos:

  • En el paso 11, P1 intenta dejar un tercer elemento. ¿Sigue usando la CPU?
  • En el paso 16, C1 hace signal(empty). ¿Cambia el contador?
  • En el paso 22, C1 hace wait(full). ¿Quién recibe la CPU?

Debajo del tablero aparecen los elementos consumidos, en orden, y cada bloqueo con su paso y su semáforo.

Explicar

Esta etapa se abre cuando ejecutas la simulación hasta el final.

Ir a la simulación

Lo correcto era: P1 se bloquea primero, en empty, y empty vale 0 después del primer signal(empty).

Bloquearse no es esperar dando vueltas. P1 llena las dos casillas y en el paso 11 su wait(empty) encuentra 0. No sobrescribe nada ni se queda comprobando en un bucle: pasa a la cola de empty y suelta la CPU. Un hilo bloqueado no consume nada hasta que alguien lo despierta. Si pensaste que C1 se bloquearía primero porque el búfer empieza vacío, fíjate en que C1 ni siquiera recibe la CPU hasta que P1 se bloquea.

signal no siempre suma. En el paso 16, C1 libera una casilla con signal(empty), pero P1 está esperando en empty. El permiso pasa directamente a P1, que despierta, y el contador se queda en 0. En el paso 21, en cambio, nadie espera en empty (P1 ya está listo) y el contador sube a 1.

Dos clases de espera. empty y full hacen esperar a los hilos por una condición: que haya sitio o que haya datos. mutex los hace esperar por acceso exclusivo. Un mutex por sí solo protege los índices, pero no sirve para esperar a que haya sitio: el productor tendría que soltar el cerrojo, volver a mirar una y otra vez, y gastar CPU.

El orden de los wait importa. Si el productor hace wait(mutex) antes que wait(empty) y encuentra el búfer lleno, se bloquea con el mutex tomado. El consumidor, que es el único que podría liberar una casilla, necesita primero el mutex y también se bloquea. Nadie podrá hacer nunca un signal: es un interbloqueo. La regla: primero espera la condición, después toma el mutex, y suéltalo lo antes posible.

Un error que depende del intercalado. La versión invertida termina sin problemas con cuanto 1, porque el consumidor libera una casilla antes de que el productor tome el mutex con el búfer lleno. Como una condición de carrera, un interbloqueo que depende del momento puede esconderse durante miles de ejecuciones.

POSIX hace lo mismo con otro orden. Aquí signal entrega el permiso directamente a quien espera. En POSIX, sem_post suma 1 y despierta a un hilo, que al correr resta 1. Una vez que el hilo despertado avanza, el contador vale lo mismo en los dos casos.

Mutex y semáforo no son lo mismo. Un mutex tiene dueño: solo lo puede liberar el hilo que lo tomó, y eso permite detectar errores y aplicar herencia de prioridad. Un semáforo no tiene dueño: cualquier hilo puede hacer signal, y justamente por eso full y empty sirven de aviso entre productor y consumidor.

En sistemas reales. POSIX ofrece sem_wait y sem_post, y pthread_mutex_lock y pthread_mutex_unlock; Java tiene java.util.concurrent.Semaphore; Python tiene threading.Semaphore y queue.Queue, un búfer acotado listo para usar. En Linux, mutex y semáforos se construyen sobre la llamada al sistema futex: si nadie compite por el cerrojo, tomarlo y soltarlo no entra al núcleo.

Experimentar

Esta etapa se abre cuando ejecutas la simulación hasta el final.

Ir a la simulación

Usa el tablero para resolver estos retos. Cada uno tiene una solución posible al desplegarlo.

1. Consigue que el programa se quede detenido para siempre.

Carga Orden invertido. En el paso 12, P1 se bloquea en empty con el mutex tomado; en el paso 14, C1 se bloquea en mutex. Ninguno puede despertar al otro.

2. Haz que la versión invertida termine sin cambiar su código.

En Orden invertido, elige Con cuanto y pon el cuanto en 1. Los turnos de una operación dejan que C1 libere una casilla antes de que P1 tome el mutex con el búfer lleno. Termina en 30 pasos, pero el error sigue ahí.

3. Haz que el productor de Productor rápido nunca se bloquee.

Sube el búfer a 3 casillas. empty empieza en 3, un permiso por elemento. C1 tampoco se bloquea: cuando recibe la CPU, full ya vale 3.

4. Haz que un productor se bloquee en mutex.

Carga Dos productores. En el paso 5, P2 intenta tomar el mutex mientras P1 lo tiene para dejar su elemento.

Comprobar

Esta etapa se abre cuando ejecutas la simulación hasta el final.

Ir a la simulación
1. Un semáforo vale 0 y un hilo hace wait sobre él. ¿Qué pasa?
2. ¿Con qué valores empiezan empty, full y mutex en un búfer de 5 casillas?
3. El productor hace wait(mutex) y después wait(empty), y el búfer está lleno. ¿Qué puede pasar?
4. Un hilo hace signal(empty) mientras otro está bloqueado en empty. ¿Qué pasa con el contador?
5. La versión invertida se ejecutó 100 veces sin detenerse. ¿Es correcta?
6. ¿Qué permite un semáforo que un mutex no permite?

Profundizar

  • Variables de condición y monitores. pthread_cond_wait y, en Java, synchronized con wait y notify, son otra forma de esperar una condición sin girar.
  • Lectores y escritores, y los filósofos comensales. Más problemas clásicos de sincronización; el de los filósofos abre el siguiente módulo, el interbloqueo.
  • Inversión de prioridad. Un hilo urgente espera un mutex que tiene uno poco urgente, al que a su vez desplaza uno intermedio. Le pasó a la sonda Mars Pathfinder en 1997; la herencia de prioridad lo resuelve.
  • Futex. Cómo Linux deja fuera del núcleo los cerrojos que nadie disputa.

Para leer más:

  • Arpaci-Dusseau y Arpaci-Dusseau, Operating Systems: Three Easy Pieces, cap. 31, sección 31.4. Gratis en línea.
  • Silberschatz, Galvin y Gagne, Operating System Concepts, 10.ª ed., secciones 6.5, 6.6 y 7.1.1.
  • Dijkstra, Cooperating sequential processes (EWD 123), 1965: cs.utexas.edu.
  • Manuales sem_overview(7) y futex(7): man7.org.