Sr-4-wyk-2.0-Slajd35
Algorytm Baraka i Shiloha
Algorytm Baraka i Shiloha jest algorytmem do globalnego równoważenia obciążenia. W algorytmie tym zakłada się, że każdy komputer przechowuje informację o obciążeniu pewnej stałej liczby innych komputerów. Co pewien czas informacje o obciążeniach wymieniane są losowo pomiędzy parami komputerów. Przy użyciu tych informacji, algorytm stara się zminimalizować rozbieżności w obciążeniu poszczególnych komputerów.
W skład algorytmu wchodzą trzy komponenty składowe.
1) Algorytm do obliczania obciążenia procesora, który służy do szacowania lokalnego obciążenia komputera. Lokalne obciążenie obliczane jest co pewien określony czas, a następnie jest uśredniane w danym okresie czasu. W algorytm tym wykorzystywany jest również tzw. wektor obciążenia, L , w którym przechowywane są lokalnie informacje o obciążeniach komputerów. Na pierwszej pozycji wektora L przechowywana jest informacja o lokalnym obciążeniu komputera. Kolejne pozycje wektora L zawierają wartości obciążenia innych komputerów. Wartość L[j ] oznacza pozycję j w wektorze obciążenia i zawiera szacowane obciążenie komputera j .
2) Kolejnym komponentem jest algorytm wymiany informacji między komputerami, który jest odpowiedzialny za przekazywanie informacji o obciążeniach między komputerami. Wymiana informacji polega w skrócie na przesłaniu pewnej części wektora obciążenia L do innych komputerów, tak aby były dobrze poinformowane o stanie obciążenia.
Poniżej opiszemy bardziej szczegółowo działanie algorytmu wymiany informacji.
Co pewien czas każdy komputer wykonuje kilka operacji. Aktualizuje informację o wartości swojego obciążenia w wektorze L , a następnie wybiera losowy komputer i i wysyła do niego pierwszą połowę swojego wektora obciążenia, Lr . Po otrzymaniu części wektora obciążenia, każdy komputer oszacowuje obciążenie każdego innego komputera poprzez połączenie otrzymanego wektora ze swoim własnym wektorem obciążenia L . Należy nadmienić, że porządek wartości w wektorze L implikuje wiek informacji. Łączenie połowy wektora obciążenia podczas jego podziału jest pewną formą starzenia danych (ang. aging ). W kolejnym kroku algorytm stara się oszacować obciążenie komputera używając w tym celu średniej liczby procesów, które żądają usługi w pewnej jednostce czasu. Wartość tego obciążenia jest użyta następnie do określenia czasu reakcji (ang. response time ) procesora. Do komputera, który ma najmniejszy czas reakcji można teraz przenieść proces. Specjalny proces działa dodatkowo na każdym komputerze i sprawdza czy są procesy, które mogą być poddane wędrówce.
3) Ostatnim komponentem w podejściu Baraka i Shiloha jest migracja procesów, której nie będziemy jednak tutaj już przedstawiać.
Algorytm Baraka i Shiloha jest algorytmem optymalnym globalnie przy założeniu, że wektor L ma rozmiar, który jest równy liczbie wszystkich komputerów w sieci.
