Antes de empezar
- Mutex, bloqueo y despertar (lección Sincronización: mutex y semáforos).
- La cola de listos y el estado bloqueado (lección Procesos y sus estados).
Teoría
En esta lección cada recurso tiene una sola instancia: un cerrojo, un archivo, una impresora, un tenedor. Un hilo lo toma (o se bloquea hasta que su dueño lo suelte), lo usa y lo suelta. Si al soltarlo hay alguien esperando, el primero de la cola se lo queda.
El grafo de asignación de recursos dibuja quién tiene qué y quién espera qué:
| Flecha | Significa |
|---|---|
| Continua, de R a T | T tiene R. |
| Discontinua, de T a R | T espera R. |
Un interbloqueo es un conjunto de hilos en el que cada uno espera un recurso que tiene otro del conjunto. Ninguno puede seguir, así que ninguno soltará nunca lo que tiene. Con recursos de una sola instancia, hay interbloqueo si y solo si hay un ciclo en el grafo.
Los filósofos comensales: n filósofos alrededor de una mesa y un tenedor entre cada par. Para comer, un filósofo necesita los dos tenedores que tiene al lado. Cada uno toma el tenedor de su izquierda, después el de su derecha, come y deja los dos. En el simulador, el tenedor izquierdo del filósofo Ti es Ri y el derecho es Ri+1 (R1 para el último).
Hay una CPU, cada turno ejecuta una operación y los turnos van en círculo.
Ejemplo: T1 tiene R1 y espera R2; T2 tiene R2. Eso es una cadena, T1 → R2 → T2, no un ciclo: cuando T2 suelte R2, T1 seguirá.
Predecir
El tablero empieza con Filósofos: cinco filósofos se sientan a la vez. Cada uno toma el tenedor izquierdo, después el derecho, come una vez y deja los dos.
Responde en el panel Tu predicción antes de ejecutar: ¿termina en interbloqueo? y ¿cuántos filósofos llegan a comer (a hacer work)?
Ejecutar
Escenario
Con orden global, cada hilo pide sus recursos de menor a mayor número (R1 antes que R2), sin cambiar en qué momento los pide.
Retraso antes de empezar
Turnos que el hilo pasa haciendo otra cosa antes de su programa.
Tu predicción
El tablero antes de empezar
Una CPU, una operación por turno y turnos en círculo. Cada recurso tiene un solo dueño.
| Hilo | Estado | Tiene | Espera | Programa |
|---|---|---|---|---|
| Listo | nada | – |
| |
| Listo | nada | – |
| |
| Listo | nada | – |
| |
| Listo | nada | – |
| |
| Listo | nada | – |
|
Qué pasó en este turno
Pulsa Ejecutar o avanza turno a turno. Aquí verás qué pide cada hilo y quién lo tiene.
Mientras avanza, fíjate en tres momentos:
- En el paso 5, ¿queda algún tenedor libre?
- Entre los pasos 6 y 9 aparece una flecha discontinua por turno. ¿Es ya un ciclo?
- En el paso 10, ¿adónde lleva la última flecha?
La tabla de debajo del grafo dice qué tiene cada hilo, qué espera y en qué operación de su programa está.
Explicar
Esta etapa se abre cuando ejecutas la simulación hasta el final.
Ir a la simulaciónLo correcto era: sí hay interbloqueo, y ningún filósofo come.
Un interbloqueo no se arregla esperando. En los cinco primeros turnos cada filósofo toma su tenedor izquierdo. En los cinco siguientes cada uno pide el derecho, que es el izquierdo de su vecino. En el paso 10 la última petición cierra el ciclo T5 → R1 → T1 → R2 → T2 → R3 → T3 → R4 → T4 → R5 → T5. Para avanzar, alguien tendría que soltar un tenedor, y nadie suelta nada mientras espera.
Las cuatro condiciones de Coffman. Un interbloqueo necesita las cuatro a la vez:
| Condición | En la mesa |
|---|---|
| Exclusión mutua | Un tenedor tiene un solo dueño. |
| Retener y esperar | Cada uno guarda su tenedor izquierdo mientras pide el derecho. |
| Sin expropiación | Nadie le quita un tenedor a otro. |
| Espera circular | El ciclo del grafo. |
Basta romper una para que el interbloqueo sea imposible.
Prevención con un orden global. Numera los recursos y pídelos siempre de menor a mayor. Un ciclo necesitaría que alguien tuviera un recurso alto mientras espera uno más bajo, y el orden lo impide: se rompe la espera circular. En la mesa solo cambia un filósofo, T5, que pasa a tomar R1 antes que R5. Los demás ya tomaban primero el tenedor de número menor.
Esperar no es estar interbloqueado. Con el orden global, tras el paso 8 hay cuatro filósofos bloqueados a la vez, pero sus flechas forman una cadena que termina en T4, que tiene R4 y encuentra R5 libre: lo toma en su siguiente turno, come, suelta, y la cadena se deshace de uno en uno.
El resto del sistema sigue. En Dos cerrojos, T1 y T2 se interbloquean en el paso 8, pero T3, que solo usa R3, termina con normalidad. El sistema no se congela: los hilos del ciclo simplemente no vuelven nunca.
Ajustar los tiempos no es una solución. Si T2 empieza 2 turnos tarde, T1 toma los dos cerrojos antes y Dos cerrojos termina. Con 1 turno de retraso, el ciclo se forma igual. Un disco más lento o otra carga devuelven el mal momento.
Cuatro estrategias:
- Prevenir: romper una condición de Coffman por diseño. Orden global de cerrojos, pedir todo de una vez, o intentar tomar el cerrojo y, si está ocupado, soltar lo que se tiene y reintentar.
- Evitar: conceder una petición solo si el sistema queda en un estado seguro (el algoritmo del banquero de Dijkstra). Exige conocer de antemano lo máximo que pedirá cada uno; es raro en sistemas de propósito general.
- Detectar y recuperar: buscar ciclos en el grafo de espera y abortar a una víctima. Las bases de datos lo hacen: PostgreSQL revisa si hay interbloqueo cuando una espera supera
deadlock_timeout(1 segundo por omisión) y aborta una transacción con un error. - Ignorar el problema: los sistemas operativos de propósito general no detectan interbloqueos entre cerrojos de las aplicaciones. El programa se queda colgado y alguien lo mata.
Herramientas. En el núcleo de Linux, lockdep anota en qué orden se toman los cerrojos y avisa la primera vez que dos se toman en órdenes opuestos, antes de que el interbloqueo llegue a ocurrir.
Varias instancias. Si un tipo de recurso tiene varias instancias, un ciclo indica que el interbloqueo es posible, pero no seguro. Para decidirlo hace falta un algoritmo como la comprobación de seguridad del banquero.
Experimentar
Esta etapa se abre cuando ejecutas la simulación hasta el final.
Ir a la simulaciónUsa el tablero para resolver estos retos. Cada uno tiene una solución posible al desplegarlo.
1. Haz que los cinco filósofos coman cambiando solo el orden en que piden los tenedores.
Activa el Orden global. Solo cambia T5 (toma R1 antes que R5) y la espera circular se vuelve imposible. Comen en este orden: T4, T3, T2, T1, T5.
2. Encuentra un momento en que cuatro hilos esperan a la vez sin interbloqueo.
Con el orden global, tras el paso 8. Las flechas discontinuas forman una cadena que termina en T4, que tiene R4 y todavía puede tomar R5, que está libre.
3. Haz que Dos cerrojos termine sin cambiar el orden de los cerrojos.
Pon el retraso de T2 en 2 (o más). T1 toma R2 antes de que T2 lo pida. Con retraso 1 el ciclo se forma igual, en el paso 10: depender del momento es frágil.
4. Provoca un interbloqueo con el menor número de hilos posible.
Filósofos con 2 a la mesa: el ciclo se cierra en el paso 4. Dos hilos y dos cerrojos tomados en órdenes opuestos bastan.
Comprobar
Esta etapa se abre cuando ejecutas la simulación hasta el final.
Ir a la simulaciónProfundizar
- El algoritmo del banquero, paso a paso: estados seguros e inseguros, y por qué un estado inseguro no siempre termina en interbloqueo.
- Livelock. Filósofos que sueltan su tenedor y reintentan todos a la vez: nadie está bloqueado, pero nadie avanza.
- Intentar y retroceder. Tomar un cerrojo con
trylocky, si falla, soltar todo y esperar un tiempo aleatorio rompe el interbloqueo a cambio de un posible livelock. - Interbloqueos en bases de datos. Grafos de espera entre transacciones y cómo se elige a la víctima.
Para leer más:
- Coffman, Elphick y Shoshani, «System Deadlocks», ACM Computing Surveys 3(2), 1971.
- Arpaci-Dusseau y Arpaci-Dusseau, Operating Systems: Three Easy Pieces, cap. 32, sección 32.3, y cap. 31, sección 31.6. Gratis en línea.
- Silberschatz, Galvin y Gagne, Operating System Concepts, 10.ª ed., cap. 8.
- Documentación del núcleo Linux, Runtime locking correctness validator: docs.kernel.org.
- Documentación de PostgreSQL,
deadlock_timeout: postgresql.org.