Pr-1st-1.1-m05-Slajd49

Przykład działania algorytmu (2)

Drugi przykład zastosowania algorytmu przedstawia kolejny slajd. Rozważany teraz graf jest podobny do poprzedniego, z tą tylko różnicą, że węzeł $P_{4}$ nie ma krawędzi wychodzącej.

Oznacza to, że proces $P_{4}$ jest aktywny. Załóżmy jeszcze, że każdy proces oczekuje potwierdzeń od wszystkich procesów tworzących jego zbiór warunkujący. Niech ponadto $Q_{1}$ będzie ponownie jedynym inicjatorem. Rozpoczyna on fazę powiadamiania, wysyłając wiadomość typu NOTIFY do monitorów wszystkich procesów tworzących zbiór ${\mathcal {OUT}}_{1}$,. Kiedy wiadomość typu NOTIFY dotrze do $Q_{4}$, którego ${\mathcal {OUT}}_{4}=\emptyset$, monitor $Q_{4}$ wywołuje procedurę NotifyProc. Procedura ta zmienia stan $pS_{4}[1]$ na 1, a następnie wywołuje procedurę ConfirmProc. W efekcie, $pS_{4}[1]=1$ i wiadomość typu CONFIRM zostaje wysłana do monitorów wszystkich procesów tworzących zbiór ${\mathcal {IN}}_{4}$. W kroku tym, monitory $Q_{2}$ i $Q_{3}$ zmieniają swoje zmienne stanu $pS_{2}[1]$ oraz $pS_{3}[1]$ na 1 i wysyłają wiadomości typu NOTIFY do monitorów wszystkich procesów tworzących ich zbiory ${\mathcal {OUT}}_{i}$. Tak więc monitor $Q_{4}$ jest inicjatorem fazy potwierdzania dla $Q_{1}$, $Q_{2}$ i $Q_{3}$. Tym samym $Q_{4}$ wyśle wiadomość typu DONE do inicjatora jego fazy powiadamiania, czyli do $Q_{1}$, dopiero po otrzymaniu wiadomości typu ACK, w odpowiedzi na wszystkie wiadomości typu CONFIRM. W następnym kroku, między innymi monitor $Q_{3}$ otrzymuje wiadomość typu CONFIRM od $Q_{4}$ i przekazuje ją do wszystkich swoich poprzedników w grafie.

Należy zauważyć, że w kroku tym $Q_{2}$ nie przesyła wiadomości typu CONFIRM do $Q_{1}$, gdyż w przyjętym modelu żądań jest to dopuszczalne dopiero po otrzymaniu wiadomości typu CONFIRM od wszystkich następników w grafie. Warunek ten jest spełniony w następnym kroku, kiedy to $Q_{2}$ otrzymał już wiadomość typu CONFIRM od $Q_{3}$. Wówczas, $Q_{2}$ wysyła wiadomość typu CONFIRM do $Q_{1}$. W efekcie, w następnym kroku wiadomości typu ACK przesłane są kolejno do $Q_{2}$, $Q_{3}$ i $Q_{4}$. Gdy wiadomość typu ACK dotrze do $Q_{4}$, monitor ten kończy fazę potwierdzania, co umożliwia mu wysłanie wiadomości typu DONE do monitora będącego dla $Q_{4}$ inicjatorem jego fazy powiadamiania.

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