Pr-1st-1.1-m05-Slajd26: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Szopen (dyskusja | edycje)
1922 edycje
Nie podano opisu zmian
 
Szopen (dyskusja | edycje)
1922 edycje
Nie podano opisu zmian
 
Linia 1: Linia 1:
==Alg. Chandy, Misra, Hass dla modelu AND (1)==
==Algorytm Chandy, Misra, Hass dla modelu AND (1)==


[[Image:pr-1st-1.1-m05-Slajd26.png|Alg. Chandy, Misra, Hass dla modelu AND (1)]]
[[Image:Pr-1st-1.1-m05-Slajd26.png|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'').  
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'').  
Linia 9: Linia 9:
* <math>probeOut</math> – pakiet kontrolny
* <math>probeOut</math> – pakiet kontrolny
* <math>granted_i</math> – tablica wartości logicznych, wartość <math>True</math> j-tego elementu tej tablicy  oznacza że proces <math>P_i</math> po odebraniu ostatniej wiadomości REQUEST od procesu <math>P_j</math> wysłał do  <math>P_j</math> potwierdzenie GRANT.
* <math>granted_i</math> – tablica wartości logicznych, wartość <math>True</math> j-tego elementu tej tablicy  oznacza że proces <math>P_i</math> po odebraniu ostatniej wiadomości REQUEST od procesu <math>P_j</math> wysłał do  <math>P_j</math> potwierdzenie GRANT.
*<math>\mathcal{D}_i<\math> – zbiór warunkujący procesu <math>P_i</math>  
*<math>\mathcal{D}_i</math> – zbiór warunkujący procesu <math>P_i</math>  
<math>recvProbe_i</math> – tablica wartości logicznych, wartość <math>True</math> j-tego elementu tej tablicy oznacza że monitor <math>Q_i</math> odebrał od <math>Q_j</math> wiadomość typu PROBE zainicjowaną przez <math>Q_k</math> i spełnione są warunki konieczne zakleszczenia procesu  <math>P_i</math> oraz <math>P_j</math>.
<math>recvProbe_i</math> – tablica wartości logicznych, wartość <math>True</math> j-tego elementu tej tablicy oznacza że monitor <math>Q_i</math> odebrał od <math>Q_j</math> wiadomość typu PROBE zainicjowaną przez <math>Q_k</math> i spełnione są warunki konieczne zakleszczenia procesu  <math>P_i</math> oraz <math>P_j</math>.
*<math>\alpha _i</math> – indeks monitora, który zainicjował detekcję zakleszczenia  
*<math>\alpha _i</math> – indeks monitora, który zainicjował detekcję zakleszczenia  
<math>deadlockDetected_i</math> – wartość <math>True</math> tej zmiennej oznacza że wykryte zostało zakleszczenie
<math>deadlockDetected_i</math> – wartość <math>True</math> tej zmiennej oznacza że wykryte zostało zakleszczenie
Linia 17: Linia 17:




[[pr-1st-1.1-m05-Slajd25 | << Poprzedni slajd]] | [[pr-1st-1.1-m05-toc|Spis treści ]] | [[pr-1st-1.1-m05-Slajd27 | Następny slajd >>]]
[[Pr-1st-1.1-m05-Slajd25 | << Poprzedni slajd]] | [[Pr-1st-1.1-m05-toc|Spis treści ]] | [[Pr-1st-1.1-m05-Slajd27 | Następny slajd >>]]

Aktualna wersja na dzień 15:54, 7 wrz 2006

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

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

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

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

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

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


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

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Pr-1st-1.1-m05-Slajd26&oldid=44687”