Pr-1st-1.1-m06-Slajd23

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 $P_2$ wymagane byłoby odebranie obu wiadomości typu GRANT, symulowanych tu przez wiadomości typu ECHO, wysłanych przez $Q_3$ i $Q_4$.

W ogólności czas potrzebny na dotarcie wiadomości typu ECHO od monitora $Q_4$ procesu aktywnego do $Q_2$, zależy od najdłuższej ścieżki między $Q_4$ a $Q_2$. 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 >>