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 $outLo{g}_{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 $outLo{g}_{i,j}({\tau }_i)$ jest bowiem jednocześnie zbiorem $inLo{g}_{i,j}({{\tau }_j}^{\prime })$ wiadomości odebranych przez $P_j$ do chwili otrzymania znacznika (wiadomości wysłane przed znacznikiem dotrą przez nim do procesu docelowego), czyli $outLo{g}_{i,j}({\tau }_i)=inLo{g}_{i,j}({{\tau }_j}^{\prime })$. Jeżeli więc stan procesu $P_j$ zostanie zapamiętany w chwili ${\tau }_i\le {{\tau }_j}^{\prime }$, to stan kanału $C_{i,j}$ w chwili ${\tau }_j$ jest równy $outLo{g}_{i,j}({\tau }_i)\setminus inLo{g}_{i,j}({\tau }_j)$. Dodatkowo znaczniki przesyłane kanałami FIFO gwarantują oczywiście że $outLo{g}_{i,j}({\tau }_j)\subseteq inLo{g}_{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ę $outLo{g}_{i,j}({\tau }_i)\setminus inLo{g}_{i,j}({{\tau }_j}^{\prime })$; gdzie ${\tau }_i\le {{\tau }_j}^{\prime }$.

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}^{\prime }$).

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