Algorytm szeregowania.html

Zasugerowano, aby ten artykuł zintegrować z artykułem Dyspozytor. (dyskusja)

Algorytm szeregowania (ang. scheduler - planista) to algorytm rozwiązujący jedno z najważniejszych zagadnień informatyki - jak rozdzielić czas procesora i dostęp do innych zasobów pomiędzy zadania, które w praktyce zwykle o te zasoby konkurują.

Najczęściej algorytm szeregowania jest implementowany jako część wielozadaniowego systemu operacyjnego, odpowiedzialną za ustalanie kolejności dostępu zadań do procesora. Oprócz systemów operacyjnych dotyczy w szczególności także serwerów baz danych.

Za najwcześniejsze prace kładące podwaliny pod teorię algorytmów szeregowania, można uznać wprowadzenie linii produkcyjnej przez Henry'ego Forda. Następnym krokiem milowym był algorytm Jacksona, stworzony w roku 1955. Ten algorytm również powstał w odniesieniu do planowania produkcji przemysłowej.

edytuj Definicja

Algorytm szeregowania n zadań stanowiących zbiór $J= \left\{J_1, ..., J_n\right\}$ jest to takie przydzielanie zadań procesorowi (lub procesorom), że każde zadanie jest przetwarzane do momentu zakończenia. Jednakże przetwarzanie danego zadania może być przerywane na bliżej nieokreślony czas.

Dla jednego procesora jest to funkcja:

$\sigma:\mathbb{R}^+\to\mathbb{N}$ , taka że:

$\forall t \in \mathbb{R}^+ \exists t_1,t_2 : [t \in \left\langle t_1, t_2 \right) \wedge \forall t' \in \left\langle t_1, t_2 \right) : \sigma \left( t \right) = \sigma \left( t' \right)]$

Zgodnie z tą definicją jest to funkcja, która dzieli czas na przedziały i każdemu przedziałowi przyporządkowuje jedną wartość naturalną będącą numerem procesu, który ma się w tym przedziale czasu wykonywać. Przyjęte jest, że przyporządkowanie wartości równej 0 oznacza procesor w stanie bezczynności. Numer nie musi mieć związku z priorytetem zadania.

Chociaż wyjaśnienie wydaje się proste, zaprojektowanie i implementacja dobrego algorytmu szeregowania nastręcza wielu trudności.

edytuj Implementacja

Zwykle implementacja algorytmu jest umieszczana w jądrze systemu, jednak nie zawsze. Ponieważ jego celem jest jedynie ustawianie listy zadań kierowanych do wykonywania a nie samo ich kierowanie, może być jednym ze zwykłych zadań, spełniającym usługę dla jądra. Taką sytuację można spotkać w systemach opartych o mikrojądro.

Planista musi także uwzględniać priorytety procesów i ich gotowość do wykonania oraz przeciwdziałać zagłodzeniu procesu poprzez przedłużający się brak dostępu do zasobów oraz tzw. inwersji priorytetów.

Większość praktycznych rozwiązań oparta jest o nadawanie zadaniom priorytetów. Jednak już samo określanie priorytetu jest problemem nietrywialnym i nie można rozpatrywać go niezależnie od co najmniej kilku czynników:

Obszaru zastosowania systemu
Celu jaki ma osiągnąć każde z zadań
Zastosowanego algorytmu szeregowania

W praktyce pod względem czasu na jaki realizowane jest planowanie kolejki zadań, można wyróżnić dwa typy planistów:

Planista długoterminowy wybiera procesy z pamięci masowej i ładuje do pamięci operacyjnej.
Planista krótkoterminowy odpowiada za ustalanie kolejności wykonywania procesów gotowych do wykonania. Musi być on bardzo szybki, w przeciwieństwie do planisty długoterminowego.

Problem szeregowania zadań powinien być rozpatrywany wielopłaszczyznowo i zwykle nie można go sprowadzić wyłącznie do rozdziału czasu procesora. Implementacja w typowym systemie powinna uwzględniać również takie elementy jak na przykład:

Korzystanie z zasobów sprzętowych takich jak na przykład pamięć masowa, sieć itd.
Lokalność pamięci cache
Różne wymagania wobec procesów (priorytety, poziom interaktywności)

W systemach operacyjnych codziennego użytku łatwo dokonać podziału na zadania interaktywne i nieinteraktywne. Zadania interaktywne przez większość czasu pozostają w stanie oczekiwania na reakcję użytkownika. Gdy taka reakcja nastąpi, powinny szybko przejść do stanu wykonywania aby ich użytkownik nie miał wrażenia, że program "zacina się". Problemem jest tu nieprzewidywalny moment, w którym do wykonywania powinno być skierowane zadanie interaktywne. Należy jednocześnie zapewnić jak najmniejsze opóźnienia w realizowaniu zadań nieinteraktywnych.

edytuj Szeregowanie a wywłaszczanie

Większość współcześnie spotykanych rozwiązań opiera się na wymuszaniu oddania kontroli czyli wielozadaniowości z wywłaszczaniem. Systemy dobrowolnego oddawania kontroli (wielozadaniowość oparta na współpracy) są rzadziej spotykane, gdyż pojedynczy źle zaimplementowany lub wrogi proces potrafi w takim wypadku zdestabilizować pracę całego systemu. Dość często stosuje się też rozwiązania mieszane - wymuszanie wobec zadań (realizowanych zwykle jako procesy) a współpraca wewnątrz zadania czyli zwykle między wątkami.

edytuj Wybrane algorytmy szeregowania

edytuj Używane najczęściej

FIFO - algorytm powszechnie stosowany, jeden z prostszych w realizacji, dający dobre efekty w systemach ogólnego przeznaczenia; zadanie wykonuje się aż nie zostanie wywłaszczone przez siebie lub inne zadanie o wyższym priorytecie;
Planowanie rotacyjne (round-robin) - każde z zadań otrzymuje kwant czasu; po spożytkowaniu swojego kwantu zostaje wywłaszczone i ustawione na końcu kolejki;
Planowanie sporadyczne - zadania otrzymują tak zwany "budżet czasu"; ten algorytm pomaga pogodzić wykluczające się reguły dotyczące szeregowania zadań okresowych i nieokresowych; wciąż nie jest implementowany przez wiele systemów, jednak znalazł się w standardzie POSIX;

edytuj Mniej powszechne

Trzy wymienione wyżej algorytmy są stosowane najczęściej. Jednak lista algorytmów szeregowania jest bardzo długa i znajdują się na niej między innymi jeszcze takie algorytmy jak:

FCFS (first come, first serve) - Bardzo podobny do kolejki FIFO - Pierwszy przyjdzie, pierwszy wykonany. Algorytm ten dokonuje najsprawiedliwszego przydziału czasu (każdemu według potrzeb), jednak powoduje bardzo słabą interakcyjność systemu - pojedynczy długi proces całkowicie blokuje system na czas swojego wykonania, gdyż nie ma priorytetów zgodnie z którymi mógłby zostać wywłaszczony. Algorytm ten stosuje się jednak z powodzeniem w systemach wsadowych, gdzie operator ładuje zadania do wykonania, a one wykonują się do skutku.
SJF (shortest job first) - Najpierw najkrótsze zadanie. Jest algorytmem optymalnym ze względu na najkrótszy średni czas oczekiwania. W wersji z wywłaszczaniem, stosowana jest metoda: najpierw najkrótszy czas pracy pozostałej do wykonania. Problemem tego algorytmu jest głodzenie długich procesów - może się zdarzyć, że cały czas będą nadchodzić krótsze procesy, a wtedy proces dłuższy nigdy nie zostanie wykonany.

edytuj Deterministyczne

W systemach operacyjnych czasu rzeczywistego (stosowanych m. in. w automatyce) najważniejszym zadaniem algorytmu szeregowania jest zapewnienie, by wykonanie danego procesu zakończyło się przed upływem zdefiniowanych dla niego ograniczeń czasowych. Opracowano w tym celu deterministyczne algorytmy szeregowania, takie jak:

RMS,
EDF

edytuj Modyfikacje

Działania planisty zwykle muszą być skonsolidowane z całością systemu. Dlatego w praktycznie używanych algorytmach szeregowania pojawiają się dodatkowe cechy, takie jak:

Planowanie priorytetowe - wybierany jest proces o najwyższym priorytecie. W tej metodzie występuje problem nieskończonego blokowania (procesu o niskim priorytecie przez procesy o wysokim priotytecie). Stosuje się tu postarzanie procesów, polegające na powolnym podnoszeniu priorytetu procesów zbyt długo oczekujących.
Planowanie wielopoziomowe - zadania przypisywane są do kolejek szeregowania w zależności od parametru opisującego każde z zadań jakim w praktyce zwykle jest priorytet. Zadania w danej kolejce są następnie szeregowane określonym algorytmem takim jak na przykład FIFO lub round-robin i kierowane do wykonania. Jeśli w danej kolejce nie ma zadań gotowych do wykonywania, planista ponownie dokonuje analizy kolejki ale dla zadań o niższym priorytecie. Zwykle możliwa jest zmiana kolejki w której szeregowane jest zadanie, poprzez zmianę priorytetu zadania.
Planowanie wieloprocesorowe - na jednakowe lub różne procesory a także całe komputery;
Synchronizacja międzyzadaniowa - ze względu na powiązanie zadań różnymi zasobami a nie tylko procesorem, konieczne jest uwzględnienie aspektu dostępu do tych innych zasobów przez szeregowane zadania;