Pr-1st-1.1-m06-Slajd23

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Analiza złożoności czasowej dwufazowego algorytmu detekcji zakleszczenia

Analiza złożoności czasowej dwufazowego algorytmu detekcji zakleszczenia

Przeanalizujmy złożoność czasową algorytmu, przyjmując podobnie jak poprzednio, że graf niezorientowany odpowiadający grafowi WFG, jest scharakteryzowany przez średnicę d i najdłuższą ścieżkę l.

Zauważmy, że przesłanie wiadomości typu ECHO przez wszystkie krawędzie (kanały) musi być poprzedzone przesłaniem wiadomości FLOOD w kierunku przeciwnym. Jak łatwo sprawdzić, przejście wiadomości typu FLOOD przez wszystkie krawędzie wymaga d+1 kroków. Stosując następnie argumentację podobną do tej odnoszącej się poprzednio do wiadomości typu GRANT w algorytmie , stwierdzamy, że w rozważanym wyżej przykładzie dla uaktywnienia procesu wymagane byłoby odebranie obu wiadomości typu GRANT, symulowanych tu przez wiadomości typu ECHO, wysłanych przez i .

W ogólności czas potrzebny na dotarcie wiadomości typu ECHO od monitora procesu aktywnego do , zależy od najdłuższej ścieżki między a . Tak więc, najdłuższa ścieżka w grafie niezorientowanym odpowiadającym grafowi determinuje czas wymagany na propagację wiadomości typu ECHO od monitora procesu aktywnego do inicjatora. Obserwacja ta prowadzi wprost do wniosku, że złożoność czasowa algorytmu wynosi (d + 1) + l.


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