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 $WF{G}^C$. Zauważmy, że w tym wypadku, w przeciwieństwie do środowiska synchronicznego rozważanego poprzednio, nie jest prawdziwa relacja:

$P_i\in {{𝒪}{𝒰}{𝒯}}_j⟺P_j\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 $WF{G}^C$ w tradycyjny graf czarno-biały $WF{G}^{BW}$ przez uwzględnienie w tym ostatnim tylko łuków w kolorze Black. Wynikowy graf $WF{G}^{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 $WF{G}^C$.

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

$expectN{o}_i-outGreyWhiteN{o}_i\le 0$,

gdzie $outGreyWhiteN{o}_i$ oznacza sumaryczną liczbę wyjściowych łuków o kolorze Grey lub White wierzchołka $P_i$, a $expectN{o}_i$ - liczność zbioru ${{𝒟}}_i={{𝒪}{𝒰}{𝒯}}_i$ (liczbę łuków wyjściowych w grafie $WF{G}^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 $WF{G}^C$, wykonywaną równolegle z samym algorytmem detekcji.

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