Pr-1st-1.1-m08-Slajd18

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 $outLog_{i,j}(\tau _{i})$ wiadomości wysyłanych przez nadawcę $P_{i}$ do $P_{j}$ w chwili $\tau _{i}$ zapamiętywania stanu lokalnego procesu $P_{i}$. Zbiór $outLog_{i,j}(\tau _{i})$ jest bowiem jednocześnie zbiorem $inLog_{i,j}(\tau _{j}')$ wiadomości odebranych przez $P_{j}$ do chwili otrzymania znacznika (wiadomości wysłane przed znacznikiem dotrą przez nim do procesu docelowego), czyli $outLog_{i,j}(\tau _{i})=inLog_{i,j}(\tau _{j}')$. Jeżeli więc stan procesu $P_{j}$ zostanie zapamiętany w chwili $\tau _{i}\leq \tau _{j}'$, to stan kanału $C_{i,j}$ w chwili $\tau _{j}$ jest równy $outLog_{i,j}(\tau _{i})\setminus inLog_{i,j}(\tau _{j})$. Dodatkowo znaczniki przesyłane kanałami FIFO gwarantują oczywiście że $outLog_{i,j}(\tau _{j})\subseteq inLog_{i,j}(\tau _{i})$ 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 $Q_{\beta }$ 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ę $outLog_{i,j}(\tau _{i})\setminus inLog_{i,j}(\tau _{j}')$; gdzie $\tau _{i}\leq \tau _{j}'$.

Nie ma więc też potrzeby specjalnego odnotowywania wiadomości odebranych z danego kanału po zapamiętaniu stanu lokalnego ($\tau _{i}$) a przed otrzymaniem znacznika ($\tau _{j}'$).

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