Pr-1st-1.1-m06-Slajd05

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytm detekcji zakleszczenia w środowisku asynchronicznym (3)

Algorytm detekcji zakleszczenia w środowisku asynchronicznym (3)

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

.

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 w tradycyjny graf czarno-biały przez uwzględnienie w tym ostatnim tylko łuków w kolorze Black. Wynikowy graf 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 .

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

,

gdzie oznacza sumaryczną liczbę wyjściowych łuków o kolorze Grey lub White wierzchołka , a - liczność zbioru (liczbę łuków wyjściowych w grafie ).

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 , wykonywaną równolegle z samym algorytmem detekcji.


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