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 ${\mathcal {P}}$ są pasywne i oczekują na wiadomości od innych procesów ze zbioru ${\mathcal {P}}$, 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 $pS_{i}$ (ang. process state), jest zmienną reprezentowaną przez tablicę [1..2] liczb naturalnych. Wartość $pS_{i}[1]$ zależy od wartości zmiennej $notified_{i}$, i od liczby odebranych wiadomości typu DONE. Początkowo wartość $pS_{i}[1]$ jest równa 0. Po nadaniu zmiennej $notified_{i}$ wartości True przez monitor $Q_{i}$, $pS_{i}[1]$ przyjmuje wartość 1. Następnie, gdy zakończy się zainicjowana ewentualnie faza potwierdzania i odebrana zostanie ostatnia wiadomość typu DONE, wartość $pS_{i}[1]$ jest zmieniana na 2. Podobnie wartość $pS_{i}[2]$ zależy od zmiennej $confirmed_{i}$, oraz od liczby odebranych wiadomości typu ACK. Początkowo $pS_{i}[2]$ równa się 0. Po nadaniu zmiennej $confirmed_{i}$ wartości True przez monitor $Q_{i}$, $pS_{i}[2]$ przyjmuje wartość 1. Następnie, po odebraniu ostatniej wiadomości typu ACK, wartość elementu $pS_{i}[2]$ jest zmieniana na 2. Drugi wektor skojarzony z każdym monitorem $Q_{i}$, oznaczony przez $cS_{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 $pS_{i}$ jest umieszczony wewnątrz wierzchołka, a wektor $cS_{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 ${\mathcal {OUT}}_{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 $pS_{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 $notified_{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 >>