Pr-1st-1.1-m06-Slajd21

Z Studia Informatyczne
Wersja z dnia 15:56, 7 wrz 2006 autorstwa Szopen (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Dwufazowy algorytm detekcji zakleszczenia dla modelu k spośród r (8)

Dwufazowy algorytm detekcji zakleszczenia dla modelu k spośród r (8)

Zauważmy, że w prezentowanym algorytmie pojawia się problem stwierdzenia zakończenia algorytmu detekcji. W celu rozwiązania tego problemu, zastosowano technikę wag, wprowadzając dodatkowo wiadomości typu SHORT. W chwili gdy detekcja jest inicjowana, waga o wartości 1 jest równomiernie dzielona i dołączana do wiadomości typu FLOOD wysyłanych przez inicjatora.

Jeżeli odbierana jest przez monitor pierwsza wiadomość typu FLOOD, waga tej wiadomości jest ponownie równomiernie dzielona i wysyłana wraz z propagowanymi dalej wiadomościami typu FLOOD. Wagi wszystkich kolejnych wiadomości typu FLOOD, są przesyłane od razu wprost do inicjatora, z wykorzystaniem wiadomości typu SHORT. Kiedy wiadomość typu FLOOD dotrze do liścia grafu, jej waga jest zwracana wraz z wiadomością typu ECHO.

W przypadku odebrania wiadomości typu SHORT należy sprawdzić, czy nie jest to wiadomość nieaktualna. Jeśli tak jest w istocie to wiadomość jest ignorowana. W przeciwnym przypadku aktualizowana jest waga procesu inicjatora poprzez dodanie wagi zawartej w odebranym komunikacie.

Algorytm gwarantuje, że niezmienna, równa 1, pozostaje stale suma wag w wiadomościach typu FLOOD, ECHO i SHORT, powiększona o wagę inicjatora, wynikającą z otrzymanych już przez niego wiadomości typu SHORT i ECHO. Algorytm kończy się zatem, gdy waga inicjatora osiągnie wartość 1, co oznacza, że wszystkie działania związane z tworzeniem, zapamiętywaniem oraz redukcją obrazu grafu WFG, zostały zakończone.

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