Pr-1st-1.1-m06-Slajd05

Algorytm detekcji zakleszczenia w środowisku asynchronicznym (3)

Załóżmy teraz, że każdy monitor $Q_{i}$ zna odpowiadające mu zbiory oraz oraz kolory wszystkich krawędzi incydentnych grafu $WFG^{C}$. Zauważmy, że w tym wypadku, w przeciwieństwie do środowiska synchronicznego rozważanego poprzednio, nie jest prawdziwa relacja:

$P_{i}\in {\mathcal {OUT}}_{j}\iff P_{j}\in {\mathcal {IN}}_{i}$.

Jak łatwo zauważyć, łuk Grey w skończonym czasie zmieni swój kolor na Black albo Translucent w wyniku odebrania wiadomości typu REQUEST przez adresata lub wysłania przez nadawcę wiadomości typu CANCEL. Kolor Grey występuje zatem tylko przejściowo. Uwzględniając ten fakt, można dokonać odwzorowania kolorowanego grafu $WFG^{C}$ w tradycyjny graf czarno-biały $WFG^{BW}$ przez uwzględnienie w tym ostatnim tylko łuków w kolorze Black. Wynikowy graf $WFG^{BW}$ jest wystarczający do detekcji zakleszczenia, choć wykrycie tego stanu staje się możliwe dopiero, gdy żądania zostaną uwzględnione w grafie, a więc gdy łuki Grey zmienią kolor na Black. To opóźnienie detekcji nie podważa jednak poprawności rozwiązania. Powyższa transformacja oznacza przyjęcie wstępnej hipotezy, że żądania odpowiadające łukom Grey i White są już potwierdzone. Oczywiście, jeżeli przy takim założeniu zostanie wykryte zakleszczenie, to zakleszczenie występuje tym bardziej w stanie opisanym przez graf kolorowany $WFG^{C}$.

Przedstawioną powyżej koncepcję implementuje algorytm zaprezentowany na kolejnych slajdach. Przyjęto w nim, że warunkiem uaktywnienia procesu jest spełnienie relacji:

$expectNo_{i}-outGreyWhiteNo_{i}\leq 0$,

gdzie $outGreyWhiteNo_{i}$ oznacza sumaryczną liczbę wyjściowych łuków o kolorze Grey lub White wierzchołka $P_{i}$, a $expectNo_{i}$ - liczność zbioru ${\mathcal {D}}_{i}={\mathcal {OUT}}_{i}$ (liczbę łuków wyjściowych w grafie $WFG^{C}$).

Problem wyznaczania kolorów można rozwiązać przez zastosowanie odpowiednich liczników wiadomości wysłanych i odebranych. Dalej algorytm ten może być uzupełniony i rozwinięty o fazę wyznaczania grafu kolorowanego $WFG^{C}$, wykonywaną równolegle z samym algorytmem detekcji.

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