Pr-1st-1.1-m06-Slajd20

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

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

Dla modelu żądań k spośród r, wierzchołek grafu jest redukowany, gdy odpowiedni monitor otrzyma wiadomości typu ECHO. Po redukcji wierzchołka, monitor wysyła wiadomości typu ECHO do wszystkich monitorów odpowiadających poprzednikom w grafie WFG, podtrzymując tym samym fazę detekcji. Wysłane wiadomości typu ECHO mogą z kolei spowodować redukcję kolejnych wierzchołków itd. Na koniec, monitor inicjujący stwierdza wystąpienie zakleszczenia, jeżeli nie został on zredukowany do chwili zakończenia algorytmu. Zakleszczone procesy reprezentowane są przy tym przez wszystkie nie zredukowane wierzchołki grafu WFG. Jeśli wiadomość typu ECHO nie powoduje redukcji węzła to jej waga jest wysłana wprost do inicjatora w wiadomości SHORT.

W ogólności, redukcja spójnego obrazu grafu WFG może się rozpocząć w wierzchołku nie będącym liściem grafu, przed zapamiętaniem całego grafu. Ma to miejsce, gdy wiadomość typu ECHO dotrze do monitora i zainicjuje redukcję odpowiadającego mu wierzchołka grafu WFG przed nadejściem wiadomości typu FLOOD wszystkimi kanałami wejściowymi reprezentowanymi w grafie, a więc przed zapamiętaniem w całości lokalnej części grafu.

Tak więc dwa działania związane z tworzeniem obrazu spójnego grafu WFG i redukcją tego grafu, realizowane są współbieżnie i żadna dodatkowa synchronizacja nie jest potrzebna.

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