Pr-1st-1.1-m06-Slajd22

Przykład działania dwufazowego algorytmu detekcji zakleszczenia rozproszonego

Przeanalizujmy działanie tego algorytmu na konkretnym przykładzie przedstawionym w prezentacji. Przyjmiemy ponownie dla uproszczenia, że warunkiem uaktywnienia procesu jest otrzymanie potwierdzenia GRANT od wszystkich procesów tworzących zbiór warunkujący. Niech $Q_1$ będzie inicjatorem procesu detekcji zakleszczenia rozproszonego, a $P_4$ - jedynym aktywnym procesem. Najpierw, inicjator $Q_{\alpha }=Q_1$ przekazuje do monitorów procesów tworzących jego zbiór warunkujący wiadomości typu FLOOD, każdą z wagą 1/3. Ponieważ proces $P_4$ jest aktywny, monitor $Q_4$ może od razu wysłać w odpowiedzi wiadomość typu ECHO, z wagą 1/3 równą wadze otrzymanej wiadomości typu FLOOD. Z kolei monitor $Q_3$ przekazuje wiadomość FLOOD do następnika, a $Q_2$ przekazuje wiadomość typu FLOOD do $Q_3$ i $Q_4$. Monitor $Q_2$ dzieli oczywiście wagę otrzymanej wiadomości FLOOD na pół, a więc wysyła wiadomości z wagami 1/6. W następnym kroku, monitor $Q_4$ jako skojarzony z procesem aktywnym, odpowiada wiadomościami typu ECHO do $Q_3$ i $Q_2$, z wagami równymi odpowiednio 1/3 i 1/6. Monitor $Q_3$ wysyła natomiast wiadomość typu SHORT bezpośrednio do inicjatora w odpowiedzi na odebranie kolejnej wiadomości typu FLOOD od $Q_2$. Następnie, po otrzymaniu wiadomości typu ECHO z wagą 1/3, $Q_3$ przekazuje tę wiadomość do swoich poprzedników $Q_1$ i $Q_2$ , dzieląc na pół otrzymaną wagę. Ponieważ pojedyncza wiadomość aplikacyjna typu GRANT symulowana tu przez wiadomość typu ECHO od $Q_4$ nie byłaby wystarczająca do uaktywnienia $P_2$, $Q_2$ wysyła wiadomość typu SHORT z wagą 1/6 do inicjatora $Q_1$. W ostatnim kroku, po otrzymaniu wiadomości ECHO od $Q_3$, monitor $Q_2$ przekaże dalej wiadomość typu ECHO do $Q_1$. Algorytm kończy się, gdy inicjator $Q_1$ otrzyma z powrotem wiadomości z sumaryczną wagą równą 1.

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