Sr-7-wyk-2.0-Slajd32
Wykrywanie zakleszczeń
W algorytmach wykrywania zakleszczeń , konstruuje się tzw. graf oczekiwania (ang. wait-for graph ), który jest grafem skierowanym. Łuki w takim grafie reprezentują stan przydziału zasobów. Mając graf oczekiwania i wiedząc, czy istnieje w nim cykl możemy stwierdzić, czy mamy do czynienia z zakleszczeniem.
Wraz z pojęciem grafu oczekiwania w systemach rozproszonych, pojawiają się również pojęcia lokalnego i globalnego grafu oczekiwania .
Lokalny graf oczekiwania związany jest z danym stanowiskiem przetwarzania. Węzły w takim grafie odpowiadają procesom lokalnym lub zdalnym, które aktualnie utrzymują lub zamawiają zasoby lokalne na określonym komputerze. Zauważmy, że w ramach poszczególnych stanowisk, procesy mogą się powtarzać.
Globalny graf oczekiwania odnosi się do wszystkich stanowisk i otrzymywany jest w wyniku zsumowania lokalnych grafów oczekiwania.
Fakt, że lokalne grafy nie posiadają cykli nie oznacza, że nie występuje zakleszczenie. Może ono być widoczne dopiero w globalnym grafie. Zatem aby stwierdzić że w systemie rozproszonym występuje zakleszczenie, musimy znać globalny graf oczekiwania.
Na rysunku zilustrowano przykład zakleszczenie trzech procesów P2 , P3 oraz P4 .
