Deadlock en un grafo de espera
La misión
Problema
Una base de datos lleva el registro de n transacciones numeradas de 0 a n - 1. Cada par [a, b] en waits significa que la transacción a está esperando un lock (bloqueo) que tiene la transacción b. Hay un deadlock (interbloqueo) cuando algún grupo de transacciones se espera entre sí en círculo. Devuelve True si el grafo de espera contiene un deadlock y False en caso contrario.
Ejemplos
Input: n = 4, waits = [[0, 1], [1, 2], [2, 0], [3, 0]]
Output: True
Por qué: 0 espera a 1, 1 a 2 y 2 a 0, así que ninguna de ellas puede avanzar nunca
Input: n = 4, waits = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: False
Por qué: dos cadenas se juntan en 3, pero juntarse no es un círculo, y 3 no espera a nadie
Input: n = 2, waits = []
Output: False
Por qué: caso límite: nadie espera, así que nadie queda atascado
Pistas
0 / 3
Un simple conjunto de visitados no basta en un grafo dirigido. En el segundo ejemplo, a 3 se llega dos veces sin ningún círculo. ¿Qué dato extra distingue un círculo de dos caminos que se juntan?
Un círculo significa que la búsqueda vuelve a una transacción que todavía está en el camino actual. Lleva tres estados: no visitada, en el camino actual y terminada.
Haz una búsqueda en profundidad desde cada transacción no visitada. Marca una transacción de gris al entrar en ella y de negro cuando hayas explorado todas sus esperas. Llegar a una transacción gris significa un deadlock, mientras que llegar a una negra es seguro.
- Tiempo objetivo
- O(n + m)
- Espacio objetivo
- O(n + m)
Restricciones
- transactions are numbered 0 to n - 1
Solución
La búsqueda en profundidad (DFS) con tres colores separa los dos casos que un conjunto de visitados no puede distinguir. Las transacciones blancas están sin explorar, las grises están en el camino que se recorre en ese momento y las negras están exploradas por completo y se demostró que no llevan a ningún círculo. Una arista hacia una transacción gris cierra un ciclo a través del camino actual, lo que es un deadlock, mientras que una arista hacia una transacción negra solo se une a una rama ya verificada. Un grafo sin deadlock es exactamente uno que tiene un orden topológico, así que esta comprobación también te dice si las transacciones podrían programarse una tras otra. Cada transacción y cada espera se visitan una vez, así que el tiempo es O(n + m) para m esperas, y el espacio es O(n + m).
def has_deadlock(n, waits):
graph = [[] for _ in range(n)]
for a, b in waits:
graph[a].append(b)
WHITE, GREY, BLACK = 0, 1, 2
colour = [WHITE] * n
def visit(u):
colour[u] = GREY # on the current path
for v in graph[u]:
if colour[v] == GREY: # walked back into the path: a circle
return True
if colour[v] == WHITE and visit(v):
return True
colour[u] = BLACK # fully explored, no circle through u
return False
return any(colour[u] == WHITE and visit(u) for u in range(n))
print(has_deadlock(4, [[0, 1], [1, 2], [2, 0], [3, 0]])) # -> True
print(has_deadlock(4, [[0, 1], [0, 2], [1, 3], [2, 3]])) # -> False
print(has_deadlock(2, [])) # -> False¿Lo que te frena es la idea y no el código? Ciclos en un grafo dirigido lo explica.