Wait-for graph'ta deadlock
Görev tanımı
Problem
Bir veritabanı 0'dan n - 1'e kadar numaralanmış n transaction'ı takip ediyor. waits'teki her [a, b] çifti, a transaction'ının b transaction'ının tuttuğu bir kilidi (lock) beklediği anlamına geliyor. Bir grup transaction bir çember halinde birbirini bekliyorsa deadlock vardır. Wait-for graph bir deadlock içeriyorsa True, değilse False döndür.
Örnekler
Input: n = 4, waits = [[0, 1], [1, 2], [2, 0], [3, 0]]
Output: True
Neden: 0, 1'i; 1, 2'yi; 2 de 0'ı bekliyor, bu yüzden hiçbiri asla ilerleyemez
Input: n = 4, waits = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: False
Neden: iki zincir 3'te buluşuyor ama buluşmak bir çember değil, 3 de kimseyi beklemiyor
Input: n = 2, waits = []
Output: False
Neden: edge case: kimse beklemiyor, kimse takılı değil
İpuçları
0 / 3
Yönlü bir grafta düz bir ziyaret kümesi yetmez. İkinci örnekte 3'e hiçbir çember olmadan iki kez ulaşılıyor. Bir çemberi buluşan iki yoldan hangi ek bilgi ayırır?
Çember, aramanın mevcut yolda hâlâ duran bir transaction'a geri dönmesi demektir. Üç durum takip et: ziyaret edilmemiş, mevcut yolda ve bitmiş.
Ziyaret edilmemiş her transaction'dan bir derinlik öncelikli arama çalıştır. Bir transaction'a girdiğinde onu gri, bütün beklemeleri keşfedilince siyah işaretle. Gri bir transaction'a ulaşmak deadlock demektir, siyah birine ulaşmak ise güvenlidir.
- Hedef zaman
- O(n + m)
- Hedef alan
- O(n + m)
Kısıtlar
- transactions are numbered 0 to n - 1
Çözüm
Üç renkli derinlik öncelikli arama (DFS), bir ziyaret kümesinin (set) ayıramadığı iki durumu ayırır. Beyaz transaction'lar keşfedilmemiştir, gri olanlar şu an dolaşılan yoldadır, siyah olanlar da tamamen keşfedilmiş ve döngüsel hiçbir yere götürmediği kanıtlanmıştır. Gri bir transaction'a giden kenar mevcut yol üzerinden bir döngüyü kapatır, bu da deadlock'tur; siyah bir transaction'a giden kenar ise yalnız zaten temizlenmiş bir dala katılır. Deadlock'suz bir graf tam olarak topolojik bir sırası olan graftır; bu kontrol transaction'ların art arda zamanlanıp zamanlanamayacağını da söyler. Her transaction ve bekleme bir kez ziyaret edilir; m bekleme için zaman O(n + m), alan 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, [])) # -> FalseKodda değil de fikirde mi takıldın? Yönlü grafta döngüler bunu anlatıyor.