Sr-4-wyk-1.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.
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 .
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.
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.
