Pr-1st-1.1-m05-Slajd51

Złożoność czasowa algorytmu detekcji zakleszczenia w środowisku synchronicznym dla modelu k spośród r (2)

Zauważmy najpierw, że faza potwierdzania jest propagowana (wiadomość typu CONFIRM zostaje wysłana do następników) przez monitor procesu pasywnego, dopiero po otrzymaniu odpowiedniej liczby wiadomości typu CONFIRM. W ogólności oznacza to, że muszą dotrzeć wiadomości typu CONFIRM od wszystkich następników (tak jak w naszym przykładzie). Czas wymagany do osiągnięcia takiego stanu detekcji zależy od najdłuższej ścieżki między inicjatorem fazy potwierdzania a danym monitorem. Dla uzasadnienia tego stwierdzenia rozważmy graf, w którym inicjator $Q_x$ fazy potwierdzania jest połączony ze swoim poprzednikiem $Q_y$ dwoma ścieżkami o długości $l_1$ i $l_2$, gdzie $l_1<l_2$. W tym wypadku, pierwsza wiadomość typu CONFIRM może dotrzeć do $Q_y$ po $l_1$ jednostkach czasu. Przypuśćmy teraz, że do uaktywnienia wymagane są dwie wiadomości typu CONFIRM. Ta druga wiadomość typu CONFIRM wymaga jednak $l_2>l_1$ jednostek czasu i stąd obie wiadomości stają się dostępne po czasie równym $max(l_1,l_2)$. W ogólności jednak, $l_2$ może być równe $l$ - długości najdłuższej ścieżki w grafie. Tak więc, nawet gdy pominiemy opóźnienia wnoszone przez węzły, przesłanie wiadomości typu CONFIRM może zabrać $l$ jednostek czasu. Następnie jednak, wiadomości typu ACK przesłane są w kierunku przeciwnym do odpowiednich inicjatorów fazy potwierdzania i ich transmisja również zabiera w najgorszym wypadku $l$ jednostek czasu.

Z drugiej strony zauważmy też, że wiadomość typu ACK jest wysłana natychmiast po otrzymaniu wiadomości typu CONFIRM, jeśli monitor otrzymał już wcześniej wiadomość typu CONFIRM, lub gdy warunek uaktywnienia nie jest spełniony. Stąd w ogólności, pesymistyczna złożoność czasowa fazy potwierdzania wynosi $2l$. Ponieważ jednak faza potwierdzania jest jak wiadomo zagnieżdżona w fazie powiadamiania, to aby wyznaczyć złożoność całego algorytmu trzeba dodać do złożoności fazy potwierdzania złożoność powiadomienia inicjatora fazy potwierdzania (przekazania mu wiadomości typu NOTIFY), jak również złożoność odpowiadającą przesłaniu wiadomości typu od inicjatora fazy potwierdzania do inicjatora detekcji.

Ponieważ wiadomości typu NOTIFY są przysyłane równolegle do monitorów wszystkich procesów tworzących zbiór ${{𝒪}{𝒰}{𝒯}}_i$, więc przesłanie to wymaga co najwyżej $d$ kroków (jednostek czasu). To samo można stwierdzić o czasie propagacji wiadomości typu po zakończeniu fazy potwierdzania. W efekcie dochodzimy do wniosku, że złożoność czasowa algorytmu wynosi $2d+2l$. Wniosek ten potwierdza ostatnio prezentowany przykład. Rzeczywiście, ponieważ analizowany graf jest scharakteryzowany przez średnicę $d=1$ oraz $l=3$, więc liczba kroków w najgorszym przypadku powinna wynosić 8. Ta sama liczba kroków okazała się również niezbędna w naszym przykładzie.

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