Pr-1st-1.1-m05-Slajd48

Przykład działania algorytmu (1)

Dla ilustracji działania algorytmu rozważmy przykładowy stan globalny reprezentowany przez graf oczekiwanych potwierdzeń przedstawiony na slajdzie. Procesy $P_1$, $P_2$, $P_3$ i $P_4$ należące do zbioru ${𝒫}$ są pasywne i oczekują na wiadomości od innych procesów ze zbioru ${𝒫}$, zgodnie z grafem WFG. Dla prostoty prezentacji skojarzymy z każdym wierzchołkiem grafu WFG (procesem) dwa wektory reprezentujące stan algorytmu w danym wierzchołku. Pierwszy wektor, oznaczony przez $p{S}_i$ (ang. process state), jest zmienną reprezentowaną przez tablicę [1..2] liczb naturalnych. Wartość $p{S}_i[1]$ zależy od wartości zmiennej $notifie{d}_i$, i od liczby odebranych wiadomości typu DONE. Początkowo wartość $p{S}_i[1]$ jest równa 0. Po nadaniu zmiennej $notifie{d}_i$ wartości True przez monitor $Q_i$, $p{S}_i[1]$ przyjmuje wartość 1. Następnie, gdy zakończy się zainicjowana ewentualnie faza potwierdzania i odebrana zostanie ostatnia wiadomość typu DONE, wartość $p{S}_i[1]$ jest zmieniana na 2. Podobnie wartość $p{S}_i[2]$ zależy od zmiennej $confirme{d}_i$, oraz od liczby odebranych wiadomości typu ACK. Początkowo $p{S}_i[2]$ równa się 0. Po nadaniu zmiennej $confirme{d}_i$ wartości True przez monitor $Q_i$, $p{S}_i[2]$ przyjmuje wartość 1. Następnie, po odebraniu ostatniej wiadomości typu ACK, wartość elementu $p{S}_i[2]$ jest zmieniana na 2. Drugi wektor skojarzony z każdym monitorem $Q_i$, oznaczony przez $c{S}_i$ (ang. communication state), jest zmienną reprezentowaną przez tablicę [1..3], której elementy odpowiadają licznikom odebranych wiadomości typu CONFIRM, ACK i DONE. Początkowo, wszystkie te liczniki mają wartość 0. Są one stosownie zwiększane w wyniku odebrania wiadomości typu CONFIRM, ACK i DONE. Na rysunku wektor $p{S}_i$ jest umieszczony wewnątrz wierzchołka, a wektor $c{S}_i$ obok wierzchołka.

W rozważanym przykładzie przyjęto, że $Q_1=Q_{\alpha }$ jest jedynym inicjatorem procesu detekcji zakleszczenia. Monitor $Q_1$ wywołuje procedurę NotifyProc i w konsekwencji jego stan zmienia się, wiadomości typu NOTIFY zostają wysłane (co zaznaczono białym kółkiem i strzałką) do monitorów wszystkich procesów tworzących zbiór warunkujący ${{𝒪}{𝒰}{𝒯}}_1$, a monitor oczekuje na wiadomości typu DONE potwierdzające wszystkie wiadomości typu NOTIFY. Następnie, monitory $Q_2$, $Q_3$ i $Q_4$ odbierają współbieżnie wiadomości typu NOTIFY i w konsekwencji wywołują procedurę NotifyProc, zmieniając tym samym odpowiednio $p{S}_i[1]$ i wysyłając wiadomości typu NOTIFY do monitorów wszystkich procesów tworzących ich zbiory warunkujące. W następnym kroku, wiadomości typu NOTIFY docierają do monitorów, których flagi $notifie{d}_i$ są już zapalone (True). Dlatego, monitory te wysyłają w odpowiedzi wiadomości typu DONE (zaznaczone czarnym kółkiem). W rezultacie, wektory stanów monitorów $Q_2$, $Q_3$ i $Q_4$ przyjmują wartość [2,0]. Umożliwia to dalej wysłanie wiadomości typu DONE do inicjatora $Q_1$. Gdy inicjator otrzyma wszystkie oczekiwane wiadomości typu DONE, algorytm kończy się stwierdzając zakleszczenie procesu $P_1$.

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