Sr-4-wyk-1.0-Slajd29
Klasyfikacja metod równoważenia obciążenia
Na rysunku została przedstawiona przykładowa klasyfikacja algorytmów równoważenia obciążenia.
Na najwyższym poziomie wyróżniono lokalne (ang. local ) i globalne (ang. global ) równoważenie obciążenia. Ze względu na temat wykładu my zajmiemy się tą drugą klasą algorytmów.
Po zejściu na niższy poziom zauważymy dwa kolejne typy algorytmów: statyczne (ang. static ) i dynamiczne (ang. dynamic ). Algorytmy statyczne charakteryzują się przede wszystkim tym, że zadania są tutaj przypisywane do procesorów a priori tzn. przed rozpoczęciem ich wykonywania. Po rozpoczęciu wykonywania, proces nie może już ulec przemieszczeniu.
Algorytmy statyczne można podzielić na: algorytmy optymalne (ang. optimal ) oraz suboptymalne (ang. sub-optimal ).
W wypadku wyboru gałęzi z dynamicznym równoważeniem obciążenia, dostaniemy dwa odgałęzienia w postaci algorytmów scentralizowanych (ang. centralized ) i rozproszonych (ang. distributed ). W pierwszym przypadku odpowiedzialność za szeregowanie procesów ponosi jedna wybrana maszyna. Z drugiej strony w rozproszonych algorytmach decyzja podejmowana jest przez kilka węzłów obliczeniowych.
Wśród rozproszonych dynamicznych algorytmów szeregowania procesów można wyróżnić dwie dodatkowe kategorie: algorytmy, które bazują na współpracy pomiędzy węzłami oraz algorytmy, które tej współpracy nie wykorzystują.
Obok przedstawionych kryteriów klasyfikacyjnych algorytmów równoważenia obciążenia, istnieją też inne, nie przedstawione na rysunku:
– algorytmy adaptacyjne (ang. adaptive ), czyli takie które potrafią wykorzystać poprzednie stany systemu przy podejmowaniu decyzji, a nie tylko bieżący stan, jak to robią algorytmy nieadaptacyjne;
– algorytmy, które stosują strategię zapoczątkowania równoważenia obciążenia przez serwer (ang. server-iitiative ) – serwer szuka zbyt obciążonych maszyn i np. wysyła część zadań na inne mniej zajęte maszyny – lub przez źródło (ang. source-initiative ), które jest zbyt obciążone pracą;
– algorytmy, które wykorzystują negocjowanie;
– algorytmy bez wywłaszczania (ang. non-pre-emptive ) tzn. takie, które przydzielają tylko nowoutworzone zadania. Algorytmy z wywłaszczaniem mogą z kolei przerywać procesy w trakcie wykonywania i je przenosić.
