Sr-4-wyk-1.0-Slajd34
Algorytm Bryanta i Finkela
Jest to dynamiczny algorytm, działający w środowisku fizycznie rozproszonym. Przebiega następująco. Komputer K1 wysyła zapytanie do jednego ze swoich najbliższych sąsiadów, komputera K2 . Zapytanie to ma na celu dwie rzeczy: informuje komputer K2 , o tym że K1 chciałby utworzyć parę, która stanowiłaby stabilne środowisko, odpowiednie do wędrówki procesów; poza tym zapytanie zawiera listę procesów oraz czasy jakie zajęło ich wykonywanie na K1 (ta informacja jest użyta w późniejszym etapie do oszacowania czasu potrzebnego na dokończenie wykonania procesu). K2 po otrzymaniu zapytania może wykonać następujące czynności: odrzucić zapytanie – w tym momencie K1 zmuszone jest do wysłania zapytanie do innego sąsiada; utworzyć parę z K1 – K1 i K2 odrzucają wtedy wszystkie nadchodzące do nich zapytania dopóki nie zakończą współpracy ze sobą; odłożyć zapytanie K1 do czasu gdy K2 znajdzie się w stanie umożliwiającym wędrówkę, ponieważ K2 może aktualnie przeprowadzać wędrówkę innego procesu – K1 musi poczekać do czasu, gdy K2 utworzy z nim parę lub go odrzuci (w tym czasie K1 nie może wypytywać innych komputerów). Po utworzeniu pary, komputer z większym obciążeniem (np. K1 ) wybiera proces do wędrówki na drugi komputer. Jako kryterium dla tej operacji używa się wskaźnika poprawy czasu reakcji k(i ) (ang. response time ), który równa się czasowi reakcji T1(i ) procesu na maszynie źródłowej podzielonemu przez sumę czasu reakcji T2(i ) tego procesu na maszynie docelowej i czasu T12(i ) jego przeniesienia na tę maszynę (np. z K1 na K2 ). T1(i ) może być obliczone poprzez oszacowanie czasu TE(i ) potrzebnego na ukończenie procesu; czas potrzebny na ukończenie procesu jest równy czasowi zużytemu do tej pory, T . Algorytm obliczania T1(i ) przedstawiono szczegółowo na ilustracji.
W wypadku gdy k(i )< 1 dla wszystkich procesów na K1 , K1 informuje K2 o tym fakcie i para jest zrywana. W przeciwnym razie proces, który rokuje najlepsze nadzieje na poprawienie efektywności wykonywania, jest wybierany do wędrówki. Cała ta procedura wykonywana jest do czasu, gdy nie można poprawić wydajności żadnego procesu na K2 .
