Pr-1st-1.1-m05-Slajd26

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

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 , określające indeks inicjatora. Podstawowe zmienne wykorzystywane przez algorytm są następujące:

  • – pakiet kontrolny
  • – tablica wartości logicznych, wartość j-tego elementu tej tablicy oznacza że proces po odebraniu ostatniej wiadomości REQUEST od procesu wysłał do potwierdzenie GRANT.
  • – zbiór warunkujący procesu

– tablica wartości logicznych, wartość j-tego elementu tej tablicy oznacza że monitor odebrał od wiadomość typu PROBE zainicjowaną przez i spełnione są warunki konieczne zakleszczenia procesu oraz .

  • – indeks monitora, który zainicjował detekcję zakleszczenia

– wartość tej zmiennej oznacza że wykryte zostało zakleszczenie

Dla uproszczenia, pominięto w specyfikacji tego algorytmu oczywiste akcje monitora , związane ze zmianą wartości .


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