Pr-1st-1.1-m05-Slajd41

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ń $WFG=⟨{𝒫},{𝒜}⟩$, w którym wierzchołki odpowiadają procesom $P_i$ a łuki $⟨P_i,P_j⟩$, oznaczone przez $A_{i,j}$ reprezentują fakt, że proces $P_i$ wysłał już żądanie REQUEST do $P_j$, lecz nie otrzymał jeszcze potwierdzenia GRANT, ani też nie wysłał unieważnienia CANCEL. W tym kontekście, zbiór ${{𝒪}{𝒰}{𝒯}}_i=\{P_j:⟨P_i,P_j⟩\in {𝒜}\}$ jest więc zbiorem warunkującym ${{𝒟}}_i$ procesu $P_i$.

Niech ponadto ${{ℐ}{𝒩}}_i$ będzie zbiorem procesów $P_j$, od których $P_i$ odebrał wiadomość REQUEST, lecz ani nie wysłał jeszcze w odpowiedzi potwierdzenia GRANT, ani też nie otrzymał od $P_j$ 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 ${{ℐ}{𝒩}}_i=\{P_j:⟨P_i,P_j⟩\in {𝒜}\}$, a ponadto $P_i\in {{𝒪}{𝒰}{𝒯}}_j$ wtedy i tylko wtedy, gdy $P_j\in {{ℐ}{𝒩}}_i$.

Przedstawimy teraz algorytm detekcji zakleszczenia dla danego grafu oczekiwanych potwierdzeń $WFG=⟨{𝒫},{𝒜}⟩$. Algorytm rozpoczyna inicjator $Q_{\alpha }$, 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 >>