Pr-1st-1.1-m05-Slajd41: Różnice pomiędzy wersjami
m Zastępowanie tekstu – „ </math>” na „</math>” |
m Zastępowanie tekstu – „<math> ” na „<math>” |
||
| Linia 4: | Linia 4: | ||
Bracha i Toueg przedstawili algorytm detekcji zakleszczenia rozproszonego dla modelu żądań ''k spośród r'' przyjmując na początek, że komunikacja jest natychmiastowa. Dla tego przypadku w każdym obrazie spójnym przetwarzania rozproszonego wszystkie kanały są puste. Obraz spójny wyrażono następnie w formie grafu oczekiwanych potwierdzeń | Bracha i Toueg przedstawili algorytm detekcji zakleszczenia rozproszonego dla modelu żądań ''k spośród r'' przyjmując na początek, że komunikacja jest natychmiastowa. Dla tego przypadku w każdym obrazie spójnym przetwarzania rozproszonego wszystkie kanały są puste. Obraz spójny wyrażono następnie w formie grafu oczekiwanych potwierdzeń | ||
<math> WFG = \left \langle \mathcal{P}, \mathcal{A} \right \rangle</math>, w którym wierzchołki odpowiadają procesom | <math>WFG = \left \langle \mathcal{P}, \mathcal{A} \right \rangle</math>, w którym wierzchołki odpowiadają procesom | ||
<math>P_i</math> a łuki <math> \left \langle P_i, P_j \right \rangle</math>, oznaczone przez <math>A_{i,j}</math> reprezentują fakt, że proces | <math>P_i</math> a łuki <math>\left \langle P_i, P_j \right \rangle</math>, oznaczone przez <math>A_{i,j}</math> reprezentują fakt, że proces | ||
<math>P_i</math> wysłał już żądanie REQUEST do <math>P_j</math>, lecz nie otrzymał jeszcze potwierdzenia GRANT, ani też nie wysłał unieważnienia CANCEL. | <math>P_i</math> wysłał już żądanie REQUEST do <math>P_j</math>, lecz nie otrzymał jeszcze potwierdzenia GRANT, ani też nie wysłał unieważnienia CANCEL. | ||
W tym kontekście, zbiór | W tym kontekście, zbiór | ||
| Linia 18: | Linia 18: | ||
<math>P_j \in \mathcal{IN}_i</math>. | <math>P_j \in \mathcal{IN}_i</math>. | ||
Przedstawimy teraz algorytm detekcji zakleszczenia dla danego grafu oczekiwanych potwierdzeń <math> WFG = \left \langle \mathcal{P}, \mathcal{A} \right \rangle</math>. Algorytm rozpoczyna inicjator | Przedstawimy teraz algorytm detekcji zakleszczenia dla danego grafu oczekiwanych potwierdzeń <math>WFG = \left \langle \mathcal{P}, \mathcal{A} \right \rangle</math>. Algorytm rozpoczyna inicjator | ||
<math>Q_{\alpha}</math>, którego proces aplikacyjny jest pasywny, a więc potencjalnie zakleszczony. Dla uproszczenia prezentacji założymy, że w danym czasie wykonywany jest co najwyżej jeden proces detekcji i taki właśnie pojedynczy proces będziemy dalej rozważać. Algorytm detekcji składa się z dwóch faz: powiadamiania i potwierdzania. W fazie '''powiadamiania''' (ang. ''notify'') wszystkie monitory są informowane o rozpoczęciu detekcji, natomiast w fazie '''potwierdzania''' (ang. ''confirm'') monitor każdego procesu aktywnego, lub potencjalnie aktywnego, symuluje wysłanie potwierdzenia typu GRANT. | <math>Q_{\alpha}</math>, którego proces aplikacyjny jest pasywny, a więc potencjalnie zakleszczony. Dla uproszczenia prezentacji założymy, że w danym czasie wykonywany jest co najwyżej jeden proces detekcji i taki właśnie pojedynczy proces będziemy dalej rozważać. Algorytm detekcji składa się z dwóch faz: powiadamiania i potwierdzania. W fazie '''powiadamiania''' (ang. ''notify'') wszystkie monitory są informowane o rozpoczęciu detekcji, natomiast w fazie '''potwierdzania''' (ang. ''confirm'') monitor każdego procesu aktywnego, lub potencjalnie aktywnego, symuluje wysłanie potwierdzenia typu GRANT. | ||
Aktualna wersja na dzień 22:15, 11 wrz 2023
Algorytm Bracha, Toueg’a (1)
Bracha i Toueg przedstawili algorytm detekcji zakleszczenia rozproszonego dla modelu żądań k spośród r przyjmując na początek, że komunikacja jest natychmiastowa. Dla tego przypadku w każdym obrazie spójnym przetwarzania rozproszonego wszystkie kanały są puste. Obraz spójny wyrażono następnie w formie grafu oczekiwanych potwierdzeń , w którym wierzchołki odpowiadają procesom a łuki , oznaczone przez reprezentują fakt, że proces wysłał już żądanie REQUEST do , lecz nie otrzymał jeszcze potwierdzenia GRANT, ani też nie wysłał unieważnienia CANCEL. W tym kontekście, zbiór jest więc zbiorem warunkującym procesu .
Niech ponadto będzie zbiorem procesów , od których odebrał wiadomość REQUEST, lecz ani nie wysłał jeszcze w odpowiedzi potwierdzenia GRANT, ani też nie otrzymał od unieważnienia CANCEL. Zauważmy teraz, że w środowisku z komunikacją natychmiastową, każda wiadomość REQUEST, GRANT czy CANCEL jest od razu odebrana, a więc , a ponadto wtedy i tylko wtedy, gdy .
Przedstawimy teraz algorytm detekcji zakleszczenia dla danego grafu oczekiwanych potwierdzeń . Algorytm rozpoczyna inicjator , którego proces aplikacyjny jest pasywny, a więc potencjalnie zakleszczony. Dla uproszczenia prezentacji założymy, że w danym czasie wykonywany jest co najwyżej jeden proces detekcji i taki właśnie pojedynczy proces będziemy dalej rozważać. Algorytm detekcji składa się z dwóch faz: powiadamiania i potwierdzania. W fazie powiadamiania (ang. notify) wszystkie monitory są informowane o rozpoczęciu detekcji, natomiast w fazie potwierdzania (ang. confirm) monitor każdego procesu aktywnego, lub potencjalnie aktywnego, symuluje wysłanie potwierdzenia typu GRANT.
Przyjęto przy tym, że faza potwierdzania jest zagnieżdżona w fazie powiadamiania. W efekcie, faza powiadamiania kończy się dopiero po zakończeniu fazy potwierdzania.
Wykorzystywane są cztery typy komunikatów będących sygnałami. Są to typy: NOTIFY, DONE, CONFIRM i ACK.
