Pr-1st-1.1-m05-Slajd29

Algorytm Chandy, Misra, Hass dla modelu AND (4)

Monitor $Q_i$ akceptuje wiadomość typu PROBE odebraną od $Q_j$ i przesyła ją dalej do $Q_k$ w wypadku, gdy spełnione są jednocześnie następujące warunki:

1. $P_i$ jest pasywny,

2. $P_i$ wysłał żądanie REQUEST i oczekuje na potwierdzenie GRANT od $P_k$, $(P_k\in {{𝒟}}_i)$

3. $P_i$ nie wysłał potwierdzenia GRANT na ostatnie żądanie REQUEST od $P_j$,

4. otrzymana wiadomość PROBE jest pierwszą wiadomością tego typu od danego inicjatora $Q_{\alpha }$, od momentu, gdy $P_i$ zmienił swój stan na pasywny.

Jeżeli $Q_{\alpha }$ zaakceptuje wiadomość PROBE przez siebie zainicjowaną, to proces $P_{\alpha }$ jest zakleszczony.

Autorzy tego algorytmu wykazali, że po zainicjowaniu detekcji przez monitor $Q_{\alpha }$ procesu zakleszczonego, monitor ten stwierdzi w skończonym czasie, że $P_{\alpha }$ należy do cyklu w WFG.

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