Deadlock: condiciones, prevención, evitación y detección

🎯 Al terminar podrás

1. Enunciar las 4 condiciones de Coffman y decir cuáles son de política y cuál convierte la posibilidad en deadlock.
2. Para una solución dada (orden de locks, portero, trylock…), decir qué condición rompe.
3. Aplicar el banquero: calcular Need = C − A, encontrar una secuencia segura y decidir si se concede una petición.
4. Distinguir prevención, evitación y detección, y elegir una según el escenario.

Antes necesitas: Semáforos y productor–consumidor

• Visual mira el diagrama o la tabla y explica qué cambia en cada paso
• Simulador predice el estado antes de pulsar el paso siguiente
• Debate elige una alternativa para el escenario y defiéndela

Deadlock: bloqueo permanente de un conjunto de procesos que compiten por recursos o se comunican. Cada uno espera un evento que solo puede producir otro proceso bloqueado del mismo conjunto. No hay una solución eficiente en el caso general.

Ejemplo del tráfico (fig. 6.1): cuatro autos llegan a un cruce de cuatro altos y cada uno necesita dos cuadrantes (a-b, b-c, c-d, d-a).

• Si todos respetan la regla «cede al de tu derecha», nadie avanza. Es un deadlock potencial: si uno decide pasar, se resuelve.
• Si todos entran a la vez, cada uno ocupa un cuadrante y espera el siguiente. Es un deadlock real.

Región fatal (diagrama de progreso conjunto, fig. 6.2)

P hace get A … get B … release A … release B y Q hace get B … get A … release B … release A. Si el camino de ejecución entra a la región fatal (P tiene A y Q tiene B), el deadlock es inevitable. Si P liberara A antes de pedir B (fig. 6.3), no existiría región fatal, sin importar el orden de ejecución. El deadlock depende de la lógica y de la dinámica.

Tipos de recursos

Reutilizables	Consumibles
los usa un proceso a la vez y no se agotan	se crean y se destruyen al consumirse
CPU, canales de E/S, memoria, dispositivos, archivos, bases de datos, semáforos	interrupciones, señales, mensajes, datos en buffers de E/S
Ejemplo: P pide el disco D y luego la cinta T; Q pide T y luego D. Con el orden p0 p1 q0 q1 p2 q2 hay deadlock. Otro: hay 200 KB, P1 pide 80 y luego 60, P2 pide 70 y luego 80	Ejemplo: P1 hace Receive(P2); Send(P2) y P2 hace Receive(P1); Send(P1) con receive bloqueante. Puede estar años sin manifestarse

Grafo de asignación de recursos (Holt): una arista proceso → recurso es una petición pendiente; una arista recurso → proceso es una asignación. Cada punto dentro de un recurso es una instancia. Un ciclo con recursos de una sola instancia implica deadlock. Con varias instancias, un ciclo no garantiza deadlock (fig. 6.5d).

Las 4 condiciones

#	Condición	Significado
1	Exclusión mutua	un recurso solo lo usa un proceso a la vez
2	Hold and wait	se retienen recursos mientras se esperan otros
3	No preemption	no se le puede quitar un recurso a quien lo tiene
4	Espera circular	hay una cadena cerrada en que cada proceso espera un recurso del siguiente

Las condiciones 1–3 son de política: necesarias pero no suficientes (hacen posible el deadlock). Con la 4, que es una consecuencia de la dinámica, las cuatro juntas son suficientes: el deadlock existe, porque se entró a la región fatal. Las condiciones 1–3 suelen ser deseables: la exclusión mutua da consistencia, y la preemption de datos exige rollback.

🔮 Predice antes de seguir

Para cada técnica, di qué condición de Coffman rompe: (a) pedir los locks siempre en orden creciente de id; (b) trylock y, si falla, soltar lo que tienes; (c) pedir todos los recursos al empezar; (d) el portero room = 4 de los filósofos.

Ya tengo mi respuesta: comparar

• (a) Espera circular: con un orden total no se puede cerrar un ciclo.
• (b) Hold and wait: al fallar, el proceso no retiene nada mientras espera. Ojo: puede producir livelock.
• (c) Hold and wait: nunca se espera teniendo algo.
• (d) Espera circular: con solo 4 filósofos sentados no se puede formar el ciclo de 5. Siempre queda uno que consigue sus dos tenedores.

Tres enfoques

1) Prevención: eliminar una condición

Condición	Cómo se previene	Costo
Exclusión mutua	en general no se puede (hay recursos intrínsecamente exclusivos)	—
Hold and wait	pedir todos los recursos de una vez, y bloquear hasta obtenerlos todos	esperas largas, recursos ociosos, hay que saber de antemano qué se necesita (difícil con módulos o hilos)
No preemption	si se deniega una petición, soltar todo y volver a pedir; o que el SO expropie al otro (si las prioridades son distintas)	solo sirve para recursos cuyo estado se guarda fácil, como la CPU
Espera circular	orden lineal de los tipos de recurso: solo se pide Rj si j > i para todo Ri que ya se tiene	ineficiente; imposible tener Ri → Rj → Ri

El caso más simple, de clase (deadlokck_single_core.c): un solo hilo hace pthread_mutex_lock(&mtx) dos veces seguidas sobre un mutex por defecto (NORMAL) y se bloquea contra sí mismo: es un auto-deadlock, que no necesita un segundo hilo. Con un mutex RECURSIVE no pasaría; con uno ERRORCHECK, el segundo lock devolvería EDEADLK.

pthread_mutex_trylock rompe el hold and wait («si no consigo el segundo, suelto el primero»), así que evita el deadlock, pero puede producir livelock o starvation (E1 2024-II).

2) Evitación: decidir dinámicamente, con información del futuro

Permite las condiciones 1–3, pero nunca entra a un estado del que no pueda garantizar la salida. Da más concurrencia que la prevención, pero exige conocer los máximos de antemano.

Notación: los vectores Resource R y Available V, y las matrices Claim C (máximos declarados) y Allocation A.

• $R_j = V_j + \sum_i A_{ij}$ (cada recurso está disponible o asignado);

• $C_{ij} \le R_j$ (nadie reclama más de lo que existe);

• $A_{ij} \le C_{ij}$ (nadie tiene más de lo que reclamó).

• Denegar el inicio de un proceso: iniciar $P_{n+1}$ solo si $R_j \ge C_{(n+1)j} + \sum_{i=1}^{n} C_{ij}$ para todo j. Es muy conservador: supone que todos pedirán su máximo a la vez.

• Denegar asignaciones (algoritmo del banquero, Dijkstra 1965): se simula la asignación y se concede solo si el nuevo estado es seguro. Un estado seguro es uno desde el que existe al menos una secuencia en que todos terminan; en cada paso se busca un $P_k$ con $C_k - A_k \le$ disponible, se simula que termina y se suman sus $A_k$.

Algoritmo del banquero (prueba de seguridad)

Las matrices son editables. Avanza paso a paso: en verde los procesos que pueden terminar (se marcan) y en ámbar el elegido en cada paso.

Fig. 6.7a · estado seguroFig. 6.8a · decidir una peticiónFig. 6.10 · detección

Resource R(9,3,6)

Available V = R − ΣA(0,1,1)

currentavail (paso 0)(0,1,1)

Claim C (máximo declarado)

	R1	R2	R3
P1
P2
P3
P4

Allocation A

	R1	R2	R3
P1
P2
P3
P4

Need = C − A

P1: (2,2,2)P2: (0,0,1)P3: (1,0,3)P4: (4,2,0)

Siguiente pasoVer resultadoReiniciar

currentavail = Available = (0,1,1)

V = (0,1,1). Solo P2 puede terminar (le falta (0,0,1)); al liberar, todos los demás pueden. Secuencia segura: P2, P1, P3, P4.

Peldaño 1 · Resueltolee cada paso y su porqué

Resuelto: la fig. 6.7a en el simulador

Elige el preset «Fig. 6.7a» y avanza paso a paso. Antes de cada paso, di qué proceso puede terminar y con qué disponible queda. Resultado (verificado con un script): V = (0, 1, 1); Need de P2 = (0, 0, 1) ≤ V, así que P2 termina y V = (6, 2, 3). Luego P1 (V = 7 2 3), P3 (9 3 4) y P4 (9 3 6). El estado es seguro. La escalera completa del banquero, con la notación de la clase, está en la clase de teoría sem. 11.

Inseguro ≠ deadlock

Un estado inseguro solo tiene potencial de deadlock: si P1 libera antes de pedir más, el sistema vuelve a un estado seguro. La evitación no predice el deadlock; garantiza que no haya posibilidad de que ocurra.

Restricciones del banquero:

• los máximos se declaran por adelantado;
• los procesos deben ser independientes, sin restricciones de sincronización entre ellos;
• el número de recursos es fijo;
• nadie termina mientras tenga recursos.

3) Detección y recuperación

Se conceden los recursos siempre que se pueda y periódicamente se busca el ciclo. Revisar en cada petición detecta temprano y el algoritmo es incremental, pero consume CPU.

Algoritmo (Coffman 1971), con Allocation, Available y la matriz de peticiones Q:

1. Marcar a los procesos con una fila de Allocation en ceros.
2. W = Available.
3. Buscar un proceso no marcado con $Q_i \le W$. Si no hay, terminar.
4. Marcarlo, hacer W += A_i y volver al paso 3.

Hay deadlock si y solo si quedan procesos sin marcar, y esos son exactamente los que están en deadlock. El simulador de arriba incluye el ejemplo de la fig. 6.10.

Recuperación, de menor a mayor sofisticación:

1. Abortar a todos los procesos en deadlock. Es lo más común.
2. Volver cada uno a un checkpoint y reiniciar. El deadlock podría repetirse, pero el no determinismo suele evitarlo.
3. Abortar uno por uno hasta que se rompa el ciclo, volviendo a correr la detección tras cada aborto.
4. Expropiar recursos uno por uno, haciendo rollback del proceso afectado.

Para 3 y 4 se elige primero al proceso con menos CPU consumida, menos salida producida, más tiempo restante estimado, menos recursos o menor prioridad.

🔮 Debate: ¿prevención, evitación o detección?

Elige un enfoque para cada sistema y defiéndelo: (1) un sistema de reservas de vuelos con miles de transacciones que bloquean filas de una base de datos; (2) un controlador de un robot industrial con 3 tareas fijas que conocen de antemano qué recursos usan; (3) un SO de escritorio como Linux.

Ya tengo mi respuesta: comparar

• (1) Detección y recuperación. Los recursos que tocará cada transacción no se conocen de antemano y los deadlocks son raros. Se detectan ciclos en el grafo de espera y se aborta una transacción con rollback, que las bases de datos ya saben hacer.
• (2) Evitación (banquero) o prevención por orden. Hay pocas tareas, los máximos se conocen y un deadlock es inaceptable. El banquero aprovecha mejor los recursos; el orden lineal es más simple.
• (3) Ignorarlo en espacio de usuario (la estrategia del avestruz) y prevenir por orden dentro del kernel, verificado con lockdep. Detectar en todo momento costaría demasiado y los máximos no se conocen.

El criterio: ¿conozco los máximos?, ¿cuánto cuesta un deadlock?, ¿puedo deshacer trabajo (rollback)?

Estrategia integrada (Howard 1973)

Agrupar los recursos en clases ordenadas: espacio de swap, luego recursos de proceso, luego memoria principal, luego recursos internos. Se usa un orden lineal entre clases, y dentro de cada clase la estrategia que mejor le sirve:

Clase	Estrategia
Espacio de swap	prevención: pedir todo de una vez (los máximos suelen conocerse) o evitación
Recursos de proceso (cintas, archivos)	evitación (se declaran de antemano) u orden dentro de la clase
Memoria principal	prevención por expropiación: swap out del proceso
Recursos internos (canales de E/S)	orden lineal

Filósofos comensales (Dijkstra 1971)

Cinco filósofos, cinco tenedores y hacen falta dos para comer. Se busca exclusión mutua sobre cada tenedor, sin deadlock y sin starvation (en este caso, literal).

Simulador de semáforos

Haz clic en un proceso para ejecutar su siguiente instrucción. Semántica de Stallings: el valor puede ser negativo (|valor| = procesos en cola) y la cola es FIFO.

Filósofos ingenuos (fig. 6.12)Filósofos con room = 4 (fig. 6.13)

fork[0]1

fork[1]1

fork[2]1

fork[3]1

fork[4]1

F0listo

▶ wait(fork[0]);

F1listo

▶ wait(fork[1]);

F2listo

▶ wait(fork[2]);

F3listo

▶ wait(fork[3]);

F4listo

▶ wait(fork[4]);

Paso aleatorioDeshacerReiniciar

Registro vacío.

Haz que cada filósofo tome su tenedor izquierdo (un clic en F0…F4): los 5 quedan bloqueados esperando el derecho. Es DEADLOCK por espera circular.

Solución	¿Deadlock?	Idea
Cada uno toma el izquierdo y luego el derecho (fig. 6.12)	Sí	los 5 toman el izquierdo a la vez: espera circular
Portero room = 4 (fig. 6.13)	No	con 4 sentados y 5 tenedores, alguno tiene los dos
Monitor con ForkReady[5] (fig. 6.14)	No	toma izquierdo y derecho dentro del monitor: nadie se cuela entre medio
Asimetría: el último toma primero el derecho	No	rompe el orden circular (es prevención por orden lineal de tenedores)
Tomar ambos o ninguno (verificar los dos con el lock)	No	rompe el hold and wait

Mecanismos de UNIX (§6.7)

Mecanismo	Para qué	Detalle
Pipes	datos productor–consumidor	buffer circular FIFO. Sin nombre (entre parientes) o con nombre (FIFO). El SO hace la exclusión mutua; si el pipe está lleno, el escritor se bloquea
Mensajes	datos	colas de mensajes (msgsnd, msgrcv) con un tipo; se puede recibir FIFO o por tipo
Memoria compartida	datos (lo más rápido)	los procesos se sincronizan por su cuenta
Semáforos	disparar acciones	vienen en conjuntos. semop aplica una lista de operaciones: sem_op > 0 suma; == 0 espera a que valga 0; < 0 resta o espera
Señales	disparar acciones	sin prioridades y no se encolan (un bit por tipo); se procesan al despertar o al volver de una syscall. Las señales RT de Linux sí se encolan, tienen prioridad y llevan un valor

⚠️ Errores que cuestan puntos

• Decir que un estado inseguro es un deadlock.Inseguro es solo la posibilidad. Si un proceso libera antes de pedir más, no pasa nada.
• Decir que un ciclo en el grafo siempre es deadlock.Eso vale solo con una instancia por recurso. Con varias, hay que intentar ir liberando.
• Calcular el banquero comparando el máximo C con lo disponible.Se compara Need = C − A (lo que le falta) con el disponible.
• Decir que trylock «resuelve» el problema.Evita el deadlock (rompe hold and wait), pero puede causar livelock y starvation.
• Decir que la evitación «predice» el deadlock.No lo predice: garantiza que nunca se entre en un estado desde el que no se pueda salir.

Autoevaluación

0/9 correctas · 0 respondidas Reiniciar

1. ¿Qué condición de Coffman es la que convierte la POSIBILIDAD de deadlock en EXISTENCIA?

a) Exclusión mutuab) Hold and waitc) No preemptiond) Espera circular

2. Pedir todos los recursos de una vez previene…

a) la exclusión mutuab) el hold and waitc) el no preemptiond) la espera circular

3. Ordenar los tipos de recurso y pedirlos siempre en orden creciente previene…

a) el hold and waitb) la espera circularc) la exclusión mutuad) la starvation

4. Un estado inseguro…

a) es un deadlockb) podría llevar a deadlock; el banquero lo evitac) es imposibled) es el estado inicial

5. Los mensajes y las señales son recursos…

a) reutilizablesb) consumiblesc) de exclusión mutuad) expropiables

6. Con varias instancias por recurso, un ciclo en el grafo de asignación…

a) siempre es deadlockb) no garantiza deadlockc) es imposibled) implica starvation

7. La recuperación más común en los SO reales es…

a) el rollbackb) abortar a todos los procesos en deadlockc) expropiar recursosd) reiniciar la máquina

8. Filósofos con room = 4: ¿por qué no hay deadlock?

a) Porque hay más tenedoresb) Con 4 sentados y 5 tenedores, al menos uno tiene sus dos tenedoresc) Porque comen por turnosd) Porque usan trylock

9. Exigencia del banquero:

a) Que los procesos compartan memoriab) Declarar los máximos por adelantadoc) Tener un solo recursod) Usar semáforos fuertes

🗣️ Explícalo tú (Feynman)

Explica por qué basta romper una de las 4 condiciones para que no haya deadlock, y por qué casi nunca se rompe la exclusión mutua.

Dilo en voz alta o escríbelo en 4–5 líneas, sin mirar la página. Después revisa qué te faltó.

Tu explicación debería mencionar…

• Las 4 juntas son suficientes y cada una es necesaria: si falta una, el deadlock no puede existir.
• La exclusión mutua es intrínseca a muchos recursos (una impresora, un lock), así que no se puede quitar.
• Por eso se ataca hold and wait (pedir todo o soltar al fallar), no preemption (expropiar) o espera circular (orden total).
• Un ejemplo de código: dos locks tomados en orden distinto y cómo el orden por id lo arregla.

Error típico al explicarlo: confundir «necesaria» con «suficiente». Las condiciones 1 a 3 solas hacen el deadlock posible, pero no lo provocan.

📈 ¿Qué tan bien lo dominas?

Elige pensando en lo que hiciste, no en lo que leíste. Para marcar 3 tienes que haber resuelto un ejercicio nuevo sin pistas y haberlo justificado. Si solo lo leíste y sientes que «ya entendí», todavía es un 1.

0No lo reconozco o lo confundo con otro tema1Lo entiendo leyendo, pero no lo aplico solo2Resuelvo ejercicios parecidos a los vistos, con alguna pista3Resuelvo uno nuevo sin ayuda y justifico cada paso4Lo transfiero: comparo alternativas y veo casos límite

Fuente ·Stallings 9e cap. 6 (§6.1–6.7, figs. 6.1–6.14, tabla 6.1) · for_partial/E1_OS_2024_II__Solucionario_.pdf (P4: condiciones y trylock) · for_partial/E1_OS_2024_I__Respuestas_.pdf (P5) · código del curso so/deadlokck_single_core.c