Deadlock em um grafo de espera
A missão
Problema
Um banco de dados acompanha n transações numeradas de 0 a n - 1. Cada par [a, b] em waits significa que a transação a está esperando um lock que a transação b detém. Existe um deadlock quando algum grupo de transações espera umas pelas outras em círculo. Retorne True se o grafo de espera (wait-for graph) contiver um deadlock e False caso contrário.
Exemplos
Input: n = 4, waits = [[0, 1], [1, 2], [2, 0], [3, 0]]
Output: True
Por quê: 0 espera por 1, 1 por 2 e 2 por 0, então nenhuma delas consegue prosseguir
Input: n = 4, waits = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: False
Por quê: duas cadeias se encontram em 3, mas se encontrar não é um círculo, e 3 não espera por ninguém
Input: n = 2, waits = []
Output: False
Por quê: edge case: ninguém espera, então ninguém fica travado
Dicas
0 / 3
Um conjunto de visitados simples não basta em um grafo direcionado. No segundo exemplo, 3 é alcançado duas vezes sem nenhum círculo. Que fato extra distingue um círculo de dois caminhos que se encontram?
Um círculo significa que a busca volta para uma transação que ainda está no caminho atual. Acompanhe três estados: não visitada, no caminho atual e concluída.
Rode uma busca em profundidade a partir de cada transação não visitada. Marque a transação de cinza ao entrar nela e de preto quando todas as suas esperas tiverem sido exploradas. Chegar a uma transação cinza significa deadlock, enquanto chegar a uma preta é seguro.
- Tempo-alvo
- O(n + m)
- Espaço-alvo
- O(n + m)
Restrições
- transactions are numbered 0 to n - 1
Solução
A busca em profundidade (DFS) com três cores separa os dois casos que um conjunto de visitados não distingue. As transações brancas não foram exploradas, as cinza estão no caminho percorrido no momento, e as pretas foram totalmente exploradas e comprovadamente não levam a nenhum círculo. Uma aresta para uma transação cinza fecha um ciclo pelo caminho atual, o que é um deadlock, enquanto uma aresta para uma transação preta só se junta a um ramo já liberado. Um grafo sem deadlock é exatamente um grafo que tem ordem topológica, então essa verificação também diz se as transações poderiam ser agendadas uma depois da outra. Cada transação e cada espera são visitadas uma vez, então o tempo é O(n + m) para m esperas, e o espaço é 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, [])) # -> FalseTravou na ideia, e não no código? Ciclos em um grafo direcionado explica isso.