Pr-1st-1.1-m05-Slajd41

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytm Bracha, Toueg’a (1)

Algorytm Bracha, Toueg’a (1)

Bracha i Toueg przedstawili algorytm detekcji zakleszczenia rozproszonego dla modelu żądań k spośród r przyjmując na początek, że komunikacja jest natychmiastowa. Dla tego przypadku w każdym obrazie spójnym przetwarzania rozproszonego wszystkie kanały są puste. Obraz spójny wyrażono następnie w formie grafu oczekiwanych potwierdzeń , w którym wierzchołki odpowiadają procesom a łuki , oznaczone przez reprezentują fakt, że proces wysłał już żądanie REQUEST do , lecz nie otrzymał jeszcze potwierdzenia GRANT, ani też nie wysłał unieważnienia CANCEL. W tym kontekście, zbiór jest więc zbiorem warunkującym procesu .

Niech ponadto będzie zbiorem procesów , od których odebrał wiadomość REQUEST, lecz ani nie wysłał jeszcze w odpowiedzi potwierdzenia GRANT, ani też nie otrzymał od unieważnienia CANCEL. Zauważmy teraz, że w środowisku z komunikacją natychmiastową, każda wiadomość REQUEST, GRANT czy CANCEL jest od razu odebrana, a więc , a ponadto wtedy i tylko wtedy, gdy .

Przedstawimy teraz algorytm detekcji zakleszczenia dla danego grafu oczekiwanych potwierdzeń . Algorytm rozpoczyna inicjator , którego proces aplikacyjny jest pasywny, a więc potencjalnie zakleszczony. Dla uproszczenia prezentacji założymy, że w danym czasie wykonywany jest co najwyżej jeden proces detekcji i taki właśnie pojedynczy proces będziemy dalej rozważać. Algorytm detekcji składa się z dwóch faz: powiadamiania i potwierdzania. W fazie powiadamiania (ang. notify) wszystkie monitory są informowane o rozpoczęciu detekcji, natomiast w fazie potwierdzania (ang. confirm) monitor każdego procesu aktywnego, lub potencjalnie aktywnego, symuluje wysłanie potwierdzenia typu GRANT.

Przyjęto przy tym, że faza potwierdzania jest zagnieżdżona w fazie powiadamiania. W efekcie, faza powiadamiania kończy się dopiero po zakończeniu fazy potwierdzania.

Wykorzystywane są cztery typy komunikatów będących sygnałami. Są to typy: NOTIFY, DONE, CONFIRM i ACK.

<< Poprzedni slajd | Spis treści | Następny slajd >>