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 >>