Clase de teoría sem. 11 · Deadlock (lo que añade al libro)

💡 En simple

La clase 11 repite el cap. 6 del libro (las 4 condiciones, prevención, evitación, detección) y le suma ejemplos de código y algoritmos al estilo de Silberschatz: Work, Finish y Need. Esta página solo trae lo nuevo. Lo que ya está en el libro lo encuentras en Stallings cap. 6.

🎯 Al terminar podrás

1. Distinguir starvation, livelock y deadlock con un ejemplo de cada uno.
2. Encontrar el deadlock en código real (productor–consumidor con los P() invertidos, transferencias con dos locks) y corregirlo.
3. Decidir con el grafo de asignación si un ciclo es deadlock según las instancias, y construir el grafo de espera.
4. Ejecutar a mano el banquero (Need, seguridad y peticiones) y el algoritmo de detección.

Antes necesitas: Coffman y los tres enfoques

• Detective escribe tu hipótesis del bug antes de abrir el diagnóstico
• Laboratorio sube la escalera: resuelto → completa → solo → variante
• Examen cronométrate y no abras la solución hasta terminar

Por qué importa para el LC3

Esta clase es posterior al LC2, así que entra. Sus ejemplos de código (productor–consumidor mal ordenado, transferencias con dos locks) tienen justo la forma de una pregunta de análisis o de código.

Starvation, livelock y deadlock

	Qué pasa	Ejemplo de la clase
Starvation	Un hilo espera indefinidamente, aunque el sistema sigue avanzando	hilos de baja prioridad que nunca corren porque siempre hay otros de alta
Livelock	Un caso especial de starvation: los estados de los procesos cambian todo el tiempo, pero ninguno progresa	dos hilos que se ceden el paso eternamente (como el trylock + reintentar del lab 11)
Deadlock	Espera circular por recursos: nadie se mueve	el hilo A tiene Res 1 y espera Res 2; el hilo B tiene Res 2 y espera Res 1

Relación clave: todo deadlock es starvation, pero no al revés. En un deadlock los procesos involucrados esperan para siempre, pero puede haber starvation sin ningún ciclo.

Modelo del sistema: tipos de recurso

• Los recursos son de tipos R1 … Rm, y cada tipo Ri tiene Wi instancias.
• Cada proceso usa un recurso en tres pasos: 1) pedir (request), 2) usar (use), 3) liberar (release).

Clasificación	Qué significa	Ejemplos
Expropiable (preemptible)	el SO puede quitarlo sin problema	CPU
No expropiable	no se le puede quitar al hilo	espacio en disco, impresora, derecho a entrar a una sección crítica
Compartible vs exclusivo	¿varios lo pueden usar a la vez?	archivo de solo lectura (compartible) vs impresora (exclusivo)
Reutilizable vs consumible	como en el libro	memoria y semáforos vs mensajes y señales

Expropiar (preemption) es interrumpir temporalmente lo que hace una tarea, con la intención de reanudarla después.

Ejemplo 1 · Productor–consumidor con los P() invertidos

La versión correcta pide primero el semáforo de conteo y después el mutex:

Producer(item) {               Consumer() {
    emptySlots.P();                fullSlots.P();
    mutex.P();                     mutex.P();
    Enqueue(item);                 item = Dequeue();
    mutex.V();                     mutex.V();
    fullSlots.V();                 emptySlots.V();
}                                  return item; }

La clase cambia el orden solo en el productor: primero mutex.P() y después emptySlots.P().

🔍 Detective · productor–consumidor con los P() invertidos

Síntoma: Con el buffer lleno, el programa se cuelga: ni el productor ni el consumidor avanzan, y la CPU queda en 0 %.

Escribe tu hipótesis (qué variable o qué orden lo causa) antes de abrir.

Pista

¿Qué tiene tomado el productor en el momento en que se bloquea? ¿Qué necesita el consumidor para liberar un espacio?

Diagnóstico: causa raíz, cuándo se dispara, corrección y cómo verificarla

Supongamos que el buffer está lleno: mutex = 1, emptySlots = 0, fullSlots = N.

Paso	Quién	Acción	Estado
1	Productor	mutex.P() ✔	mutex = 0
2	Productor	emptySlots.P() → se bloquea (vale 0) con el mutex tomado
3	Consumidor	fullSlots.P() ✔	fullSlots = N − 1
4	Consumidor	mutex.P() → se bloquea (vale 0)

• El productor espera a que el consumidor libere un espacio, pero el consumidor espera el mutex que tiene el productor. Es una espera circular: deadlock.
• La regla: nunca hay que bloquearse esperando una condición mientras se tiene el mutex. Primero el semáforo de conteo, después el mutex.
• Verificación: recorrí todos los estados con un buffer de tamaño 1. La versión correcta tiene 8 estados y ningún deadlock. La invertida tiene 11 estados y un deadlock, justo el de la traza: productor con mutex esperando emptySlots, consumidor esperando mutex, buffer lleno.

Ejemplo 2 · Deadlock por orden de locks

Dos hilos que toman dos mutex en orden opuesto (recurso reutilizable):

void *do_work_one(void *param) {           void *do_work_two(void *param) {
    pthread_mutex_lock(&first_mutex);          pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&second_mutex);         pthread_mutex_lock(&first_mutex);
    ...                                        ...
}                                          }

Si el hilo 1 toma first_mutex y el hilo 2 toma second_mutex, cada uno espera el del otro.

Transferencias bancarias (lock ordering deadlock): aquí el orden lo deciden los argumentos.

void transaction(Account from, Account to, double amount) {
    lock1 = get_lock(from);
    lock2 = get_lock(to);
    acquire(lock1);
    acquire(lock2);
    withdraw(from, amount);
    deposit(to, amount);
    release(lock2);
    release(lock1);
}

La transacción 1 hace A → B ($25) y la 2 hace B → A ($50), las dos al mismo tiempo.

🔍 Detective · transferencias cruzadas

Síntoma: El sistema del banco funciona semanas sin problemas, hasta que dos clientes se transfieren dinero mutuamente en el mismo instante. Las dos transacciones quedan colgadas.

Escribe tu hipótesis (qué variable o qué orden lo causa) antes de abrir.

Pista

Escribe el orden en que cada transacción pide los locks cuando from = A, to = B, y cuando from = B, to = A. ¿Qué condición de Coffman se cumple?

Diagnóstico: causa raíz, cuándo se dispara, corrección y cómo verificarla

Causa raíz: la 1 toma el lock de A y la 2 el de B, y luego cada una espera el lock de la otra. Ninguna función está «mal escrita»: el orden de adquisición lo deciden los datos (from, to). Por eso dos transacciones opuestas piden los mismos dos locks en orden contrario: espera circular. Cuándo se dispara: solo si las dos se intercalan justo entre el primer y el segundo acquire; por eso tarda semanas en aparecer. Corrección: un orden global.

Se rompe la espera circular tomando siempre los locks en un orden global fijo, por ejemplo por número de cuenta, sin importar cuál es el origen y cuál el destino:

void transaction(Account from, Account to, double amount) {
    Account first  = from.id < to.id ? from : to;
    Account second = from.id < to.id ? to : from;
    acquire(get_lock(first));
    acquire(get_lock(second));
    withdraw(from, amount);
    deposit(to, amount);
    release(get_lock(second));
    release(get_lock(first));
}

Ahora A → B y B → A toman primero el lock de A, así que no se puede formar el ciclo. Es la prevención de la espera circular del libro (§6.2) llevada al código. La solución propia es la misma idea que el filósofo asimétrico del lab 11.

Prevención: los detalles de la clase

• Exclusión mutua: no hace falta para recursos compartibles (archivos de solo lectura); sí para los no compartibles.
• Hold and wait, dos opciones:
  1. pedir y recibir todos los recursos antes de empezar;
  2. pedir recursos solo cuando no se tiene ninguno.
  • Desventajas: baja utilización de los recursos y posible starvation.
• No expropiación: si un proceso que tiene recursos pide uno que no se le puede dar ya, libera todo lo que tiene. Lo liberado pasa a su lista de espera y el proceso se reinicia solo cuando puede recuperar lo viejo y lo nuevo.
• Espera circular: un orden total de los tipos de recurso, pidiéndolos en orden creciente.

Grafo de asignación y cuándo un ciclo es deadlock

• Arista de petición: Pi → Rj.
• Arista de asignación: Rj → Pi.
• Arista de reclamo (claim): Pi ⇢ Rj, punteada. Indica que Pi podría pedir Rj en el futuro; se usa en la evitación.

El grafo…	Conclusión
No tiene ciclos	no hay deadlock
Tiene un ciclo y una instancia por tipo	hay deadlock
Tiene un ciclo y varias instancias por tipo	posibilidad de deadlock: hay que analizar

El ejercicio de la clase («¿este grafo representa un deadlock?»): no lo hay si se puede ir liberando.

1. T3 termina y libera R4 y R2.
2. Con eso, T2 termina y libera R1, R2 y R3.
3. Luego T1 termina.

Si existe un orden así, no hay deadlock aunque haya un ciclo. En los dos grafos siguientes de la clase, uno sí tiene deadlock (nadie puede terminar) y el otro no, porque un hilo fuera del ciclo (T2 o T4) libera una instancia.

🔮 Predice antes de seguir

Un grafo tiene un ciclo P1 → R1 → P2 → R2 → P1. R1 tiene 2 instancias: una la tiene P2 y la otra P3, que no espera nada. ¿Hay deadlock?

Ya tengo mi respuesta: comparar

No. P3 no está en el ciclo y no espera nada, así que termina y libera su instancia de R1. Esa instancia se le asigna a P1, P1 termina y libera R2, y luego P2 termina. Con varias instancias, el ciclo es necesario pero no suficiente: hay que intentar ir liberando, como en el ejercicio de la clase.

Algoritmos según el número de instancias

Instancias	Evitación	Detección
Una por tipo	analizar el grafo de asignación	grafo de espera (wait-for): los nodos son solo procesos, con Pi → Pj si Pi espera a Pj. Hay deadlock si y solo si hay un ciclo. Buscarlo cuesta O(n²)
Varias por tipo	banquero	algoritmo con Available, Allocation y Request, de costo O(m × n²)

El grafo de espera se obtiene del grafo de asignación eliminando los nodos de recurso y uniendo directamente al que espera con el que tiene el recurso.

El banquero en notación Silberschatz (como en la clase)

• Need = Max − Allocation.
• Petición de Pi:
  1. si Request ≤ Need, ir al paso 2; si no, error (superó su máximo);
  2. si Request ≤ Available, ir al paso 3; si no, esperar;
  3. simular: Available −= Request, Allocation += Request, Need −= Request. Si el estado es seguro se asigna; si no, se restaura y Pi espera.
• Seguridad:
  1. Work = Available y Finish = false;
  2. buscar un i con Finish[i] = false y Need_i ≤ Work, hacer Work += Allocation_i y Finish[i] = true, y repetir;
  3. si todos tienen Finish = true, el estado es seguro.
• Estado seguro (definición de la clase): existe una secuencia ⟨P1 … Pn⟩ con todos los procesos en la que lo que Pi aún puede pedir se cubre con lo disponible más lo que tienen todos los Pj con j < i.
• Seguro ⇒ no hay deadlock. Inseguro ⇒ posibilidad de deadlock. La evitación garantiza no entrar nunca en un estado inseguro.

Ejemplo clásico de Silberschatz: 5 procesos y recursos A = 10, B = 5, C = 7.

	Allocation (A B C)	Max (A B C)	Need = Max − Alloc
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Available = (10, 5, 7) − la suma de Allocation = (3, 3, 2).

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

Resuelto: ¿el estado es seguro?

Paso	¿Quién?	Need ≤ Work	Work después (+ Allocation)
0	—	—	3 3 2
1	P1	1 2 2 ≤ 3 3 2 ✓	5 3 2
2	P3	0 1 1 ≤ 5 3 2 ✓	7 4 3
3	P0	7 4 3 ≤ 7 4 3 ✓	7 5 3
4	P2	6 0 0 ≤ 7 5 3 ✓	10 5 5
5	P4	4 3 1 ≤ 10 5 5 ✓	10 5 7

Todos terminan: el estado es seguro, con la secuencia ⟨P1, P3, P0, P2, P4⟩. Hay otras válidas, como ⟨P1, P3, P4, P2, P0⟩, la del libro de Silberschatz. Al terminar, Work debe volver al total (10, 5, 7): es una buena forma de comprobar las sumas.

Peldaño 2 · Complétalofaltan pasos clave: llénalos tú

Complétalo: P1 pide (1, 0, 2)

Los pasos 1 y 2 de la petición ya están: Request (1 0 2) ≤ Need de P1 (1 2 2) ✓, y Request ≤ Available (3 3 2) ✓. Completa el paso 3: simula la asignación (nuevo Available, nuevo Allocation y nuevo Need de P1) y corre el algoritmo de seguridad. ¿Se concede?

Comparar (verificado con un script)

• Available = 3 3 2 − 1 0 2 = 2 3 0. Allocation de P1 = 3 0 2. Need de P1 = 0 2 0.
• Seguridad: P1 (0 2 0 ≤ 2 3 0) → Work 5 3 2 → P3 → 7 4 3 → P0 → 7 5 3 → P2 → 10 5 5 → P4 → 10 5 7.
• Es seguro: se concede.

Peldaño 3 · Solosin ayuda; luego compara

Solo: después de conceder lo anterior, llegan dos peticiones: P4 pide (3, 3, 0) y P0 pide (0, 2, 0)

Comparar (verificado con un script)

• P4 (3 3 0): es ≤ su Need (4 3 1), pero no es ≤ Available (2 3 0), porque falta A. P4 espera, sin simular nada.
• P0 (0 2 0): es ≤ su Need (7 4 3) y ≤ Available. Se simula: Available queda en 2 1 0. Ahora nadie cumple Need ≤ Work: P1 necesita 2 de B, P3 necesita 1 de C y los demás necesitan más A. El estado es inseguro, así que se deniega, se restaura el estado y P0 espera.

Peldaño 4 · Variantecambia una condición: ¿sigue valiendo lo anterior?

Variante: la misma petición de P0 (0, 2, 0), pero en el estado original (antes de conceder lo de P1)

Comparar

Ahora sí se concede. Available queda en 3 1 2 y existe la secuencia segura ⟨P3, P1, P0, P2, P4⟩ (verificada con un script). Lección: el banquero no juzga la petición en sí, sino el estado al que lleva. La misma petición puede ser segura o insegura según lo que ya se haya asignado. Que se deniegue no significa que habría habido deadlock: el banquero es conservador.

Ejemplo de detección con 5 procesos

Hay 5 procesos y 3 recursos: A = 7, B = 2 y C = 6. Available = (0, 0, 0).

	Allocation (A B C)	Request (A B C)
P0	0 1 0	0 0 0
P1	2 0 0	2 0 2
P2	3 0 3	0 0 0
P3	2 1 1	1 0 0
P4	0 0 2	0 0 2

¿Hay deadlock? ¿Y si P2 pide una C más?

Estado inicial: no hay deadlock. La clase da la secuencia ⟨P0, P2, P3, P1, P4⟩, con Finish = true para todos. Por ejemplo, P0 no pide nada y libera (0, 1, 0); P2 tampoco pide y libera (3, 0, 3), y así sucesivamente. El script encontró otra secuencia válida, ⟨P0, P2, P1, P3, P4⟩: puede haber varias.

P2 pide una C más (su fila de Request pasa a 0 0 1):

• Solo P0 puede terminar (no pide nada), y entonces Work = (0, 1, 0).
• Con eso nadie más puede: P1 pide 2 A, P2 pide 1 C, P3 pide 1 A y P4 pide 2 C.
• Hay deadlock entre P1, P2, P3 y P4.

Las dos respuestas están verificadas con un script del algoritmo de detección.

Ojo con el paso 1: a los procesos con Allocation = 0 se les pone Finish = true desde el inicio (en Stallings: «marcar los que tienen la fila en ceros»).

¿Cada cuánto correrlo? Si se invoca de forma arbitraria puede haber muchos ciclos en el grafo, y no se sabría cuál proceso «causó» el deadlock.

Recuperación (la lista de la clase)

Terminando procesos: abortar todos los que están en deadlock, o uno a la vez hasta romper el ciclo. Para elegir a quién:

1. la prioridad del proceso;
2. cuánto ha computado y cuánto le falta;
3. los recursos que ya usó;
4. los recursos que necesita para terminar;
5. cuántos procesos habrá que terminar;
6. si es interactivo o batch.

Expropiando recursos:

• Elegir víctima minimizando el costo.
• Rollback: volver a un estado seguro y reiniciar desde ahí.
• Starvation: puede salir siempre la misma víctima. La solución es incluir el número de rollbacks en el costo.

«Ignorar el problema» y lockdep

• No hay una estrategia que sirva para todo tipo de deadlock.
• Otra solución es ignorarlo (la «del avestruz»). La usan la mayoría de los SO, como UNIX y Linux, excepto en las funciones del kernel.
• Dentro del kernel, Linux usa lockdep (Lock Dependency Validator, en kernel/locking/lockdep.c):
  • detecta de forma dinámica y proactiva los deadlocks de spinlocks y mutex;
  • verifica que los locks se tomen siempre en un orden consistente en todo el código del kernel (es la prevención de la espera circular, comprobada en ejecución);
  • Linux propone además un mecanismo nuevo: DEPT (Dependency Tracker).

⚠️ Errores que cuestan puntos

• Decir que el livelock es «un deadlock lento».En el livelock los procesos cambian de estado todo el tiempo (sueltan y reintentan), pero no progresan. En el deadlock están bloqueados.
• En una petición, simular aunque Request > Available.Si no hay disponible, el proceso espera directamente. Solo se simula si cabe.
• Olvidar marcar desde el inicio a los procesos con Allocation = 0 en la detección.Esos procesos no retienen nada, así que no pueden estar en deadlock: Finish = true desde el inicio.
• Confundir la matriz Request de la detección con Need.Detección usa lo que se pide ahora (Request). El banquero usa lo que podría pedir (Need).

Autoevaluación

Clase de teoría sem. 11

0/12 correctas · 0 respondidas Reiniciar

1. ¿Cuál afirmación es correcta?

a) Toda starvation es un deadlockb) Todo deadlock es una forma de starvation, pero puede haber starvation sin deadlockc) El livelock no cambia de estadod) Deadlock y livelock son lo mismo

2. En el productor–consumidor, el productor hace mutex.P() antes que emptySlots.P(). Con el buffer lleno…

a) funciona igualb) deadlock: el productor duerme en emptySlots con el mutex tomado y el consumidor no puede entrarc) starvation del consumidord) se pierde un item

3. Transferencias A→B y B→A con dos locks pueden tener deadlock. La solución estándar es…

a) un sleep entre los dos acquireb) tomar los locks en un orden global (por id de cuenta)c) usar más hilosd) liberar en orden inverso

4. El derecho a entrar a una sección crítica es un recurso…

a) expropiableb) no expropiablec) consumibled) compartible

5. Un grafo de asignación con un ciclo y una instancia por tipo…

a) puede no tener deadlockb) tiene deadlockc) es un estado segurod) necesita el banquero

6. El grafo de espera (wait-for) se usa cuando…

a) hay varias instancias por tipob) hay una instancia por tipo; buscar un ciclo cuesta O(n²)c) se quiere evitar el deadlockd) hay recursos consumibles

7. Costo del algoritmo de detección con varias instancias:

a) O(n)b) O(n²)c) O(m × n²)d) O(m + n)

8. En el ejemplo de 5 procesos, P2 pide una C más. Resultado:

a) sigue sin deadlockb) deadlock de P1, P2, P3 y P4 (solo P0 puede terminar)c) deadlock solo de P2d) deadlock de todos

9. Al expropiar recursos para recuperarse, ¿cómo se evita que siempre caiga la misma víctima?

a) Eligiéndola al azarb) Incluyendo en el costo el número de rollbacks que ya sufrióc) Abortando todosd) Con el banquero

10. ¿Qué hace lockdep en Linux?

a) Ejecuta el banquero en cada lockb) Verifica en ejecución que los locks del kernel se tomen siempre en un orden consistentec) Mata procesos en deadlockd) Evita la starvation de los lectores

11. La mayoría de los SO (UNIX, Linux) ante el deadlock de procesos de usuario…

a) usan el banquerob) lo ignoran (salvo en el kernel)c) usan detección cada segundod) previenen hold and wait

12. Prevenir hold and wait pidiendo todo antes de empezar tiene como desventajas…

a) más deadlocksb) baja utilización de recursos y posible starvationc) livelockd) necesita orden total

🗣️ Explícalo tú (Feynman)

Explica la diferencia entre el algoritmo del banquero y el de detección, si los dos «buscan una secuencia en que todos terminan».

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…

• El banquero es evitación: se corre antes de conceder y usa Need (el peor caso futuro).
• La detección se corre después, cada cierto tiempo, y usa Request (lo que se pide ahora).
• El banquero exige conocer los máximos. La detección no, pero luego hay que recuperarse (abortar o hacer rollback).
• Si la detección deja procesos sin marcar, esos están en deadlock. Si el banquero no encuentra secuencia, el estado es inseguro (no necesariamente deadlock).

📈 ¿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 ·sem_11/Sem11_11-OST-Deadlock.pdf (clase de teoría 11) · Stallings 9e, cap. 6 · Ejemplos verificados con scripts propios: recorrido de todos los estados del productor–consumidor y algoritmo de detección · La corrección de la transferencia es una solución propia