Pr-1st-1.1-m08-Slajd18

Z Studia Informatyczne
Wersja z dnia 15:59, 7 wrz 2006 autorstwa Szopen (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wyznaczanie obrazu spójnego: Kanały non-FIFO

Wyznaczanie obrazu spójnego: Kanały non-FIFO


W algorytmie Chandy-Lamporta przesyłane znaczniki pełniły podwójną rolę. Po pierwsze, dzięki zachowaniu uporządkowania FIFO pakietów, znaczniki określały pośrednio zbiór wiadomości wysyłanych przez nadawcę do w chwili zapamiętywania stanu lokalnego procesu . Zbiór jest bowiem jednocześnie zbiorem wiadomości odebranych przez do chwili otrzymania znacznika (wiadomości wysłane przed znacznikiem dotrą przez nim do procesu docelowego), czyli . Jeżeli więc stan procesu zostanie zapamiętany w chwili , to stan kanału w chwili jest równy . Dodatkowo znaczniki przesyłane kanałami FIFO gwarantują oczywiście że a tym samym zapewniają spójność obrazu stanu globalnego.

Lai i Yang przedstawili algorytm, który nie wykorzystuje znaczników i nie wymaga by kanały były typu FIFO. W algorytmie zakłada się, że reprezentacje stanów lokalnych obejmują historię komunikacji , a więc odpowiednie zbiory wiadomości dotychczas wysłanych i odebranych. W efekcie, monitor konstruujący obraz spójny może łatwo wyznaczyć stany poszczególnych kanałów po otrzymaniu stanów lokalnych ihistorii komunikacji od wszystkich monitorów, jako różnicę ; gdzie .

Nie ma więc też potrzeby specjalnego odnotowywania wiadomości odebranych z danego kanału po zapamiętaniu stanu lokalnego () a przed otrzymaniem znacznika ().


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