Pr-1st-1.1-m08-Slajd07

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ilustracja działania algorytmu Chandy-Lamporta

Ilustracja działania algorytmu Chandy-Lamporta


Dla zilustrowania działania tego algorytmu przeanalizujemy przykład przedstawiony na slajdzie. Przyjęto na nim, że linia czerwona oznacza przesłanie wiadomości aplikacyjnej (na przykład ) natomiast liniami zielonymi oznaczono przesłanie znacznika między monitorami. Założono ponadto, że topologia przetwarzania reprezentuje graf w pełni połączony. Inicjatorem detekcji jest monitor . Na górnej części rysunku w wyniku zdarzenia zachodzącego w w zmiennej zapamiętany zostaje stan lokalny procesu , zmiennej nadawana jest wartość początkowa , a znaczniki zostają wysłane do monitorów oraz . Odebranie pierwszego znacznika przez w wyniku zdarzenia powoduje zapamiętanie stanu lokalnego i uznanie kanału wejściowego za pusty (podstawienie ).

Z kolei wiadomość , odebrana przez po zapamiętaniu stanu lokalnego, zostaje uwzględniona w stanie kanału . Zajście zdarzenia powoduje, że ostatecznie stan kanału będzie zawierał wiadomość . Ostatecznie więc zostaje wyznaczony następujący stan spójny:

Dla porównania stan wyznaczony w procesie detekcji na dolnej części rysunku wygląda następująco:


Jak widać, mimo, że proces detekcji w obu przypadkach rozpoczęty został w tej samej chwili przez ten sam monitor, otrzymane konfiguracje spójne oraz są różne. Łatwo też zauważyć, że reprezentuje stan , podczas gdy reprezentuje stan, który nie wystąpił w rozpatrywanej realizacji (w żadnej chwili nie ma jednocześnie w kanałach i wiadomości). Ta różnica nie powinna zaskakiwać z uwagi na asynchronizm komunikacji i wynikający z tego niedeterminizm przetwarzania.


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