Pr-1st-1.1-m05-Slajd26

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

Znany jest algorytm detekcji zakleszczenia dla modelu żądań AND i środowiska z kanałami FIFO, w którym monitor pasywnego procesu inicjuje spontanicznie przetwarzanie detekcyjne (ang. probe computation).

W procesie detekcji monitory przesyłają wiadomości kontrolne typu PROBE. Wysłanie wiadomości kontrolnej może być realizowane jednocześnie przez wiele procesów i dlatego wiadomości te zawierają pole $initIndex$, określające indeks inicjatora. Podstawowe zmienne wykorzystywane przez algorytm są następujące:

• $probeOut$ – pakiet kontrolny
• $grante{d}_i$ – tablica wartości logicznych, wartość $True$ j-tego elementu tej tablicy oznacza że proces $P_i$ po odebraniu ostatniej wiadomości REQUEST od procesu $P_j$ wysłał do $P_j$ potwierdzenie GRANT.
• ${{𝒟}}_i$ – zbiór warunkujący procesu $P_i$

$recvProb{e}_i$ – tablica wartości logicznych, wartość $True$ j-tego elementu tej tablicy oznacza że monitor $Q_i$ odebrał od $Q_j$ wiadomość typu PROBE zainicjowaną przez $Q_k$ i spełnione są warunki konieczne zakleszczenia procesu $P_i$ oraz $P_j$.

• ${\alpha }_i$ – indeks monitora, który zainicjował detekcję zakleszczenia

$deadlockDetecte{d}_i$ – wartość $True$ tej zmiennej oznacza że wykryte zostało zakleszczenie

Dla uproszczenia, pominięto w specyfikacji tego algorytmu oczywiste akcje monitora $Q_i$, związane ze zmianą wartości $grante{d}_i$.

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