Page 1
Algorytmy
planowania dostępu
do procesora
Page 1
Algorytmy
planowania dostępu
do procesora
Page 2
Algorytmy Szeregowania
Zadań
Planista (ang.scheduler), moduł
systemu operacyjnego zajmujący
się nadzorowaniem kolejek
procesów ubiegających się o
dostęp do zasobów systemowych,
takich jak pamięć operacyjna,
jednostka centralna (CPU),
urządzenia zewnętrzne (np. dyski).
Zależnie od funkcji rozróżnia się
planistę procesora, planistę zadań,
planistę przydziału pamięci,
spooler i innych.
Page 3
Algorytmy Szeregowania
Zadań
Dodatkowo Planista musi uwzględniać
priorytety, gotowość do działania oraz
przeciwdziałać zagłodzeniu procesu
(czyli nie dopuścić żeby dany proces
nigdy nie był wykonany) W systemach
operacyjnych czasu rzeczywistego
najważniejsze aby dany proces
skończył się przed zaplanowanym
dla nie go czasem.
Page 4
Algorytmy Szeregowania
Zadań
Rozróżniamy dwa rodzaje
planistów: krótkoterminowy
który wybiera procesy
spośród gotowych do
wykonania (musi być bardzo
szybki) oraz długoterminowy
który wybiera zadania z
pamięci masowej i ładuje do
pamięci operacyjnej.
Page 5
Algorytmy Szeregowania
Zadań
Wywłaszczenie – technika używana
w środowiskach wielozadaniowych,
w której algorytm szeregujący
(scheduler) może wstrzymać
aktualnie wykonywane zadanie
(np. proces lub wątek), aby
umożliwić działanie innemu.
Page 6
Wybrane algorytmy
szeregowania
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;
Używane najczęściej
Page 7
Wybrane algorytmy
szeregowania
Planowanie rotacyjne (round-
robin, znane też jako algorytm
karuzelowy) - każde z zadań
otrzymuje kwant czasu; po
spożytkowaniu swojego kwantu
zostaje wywłaszczone i
ustawione na końcu kolejki;
Używane najczęściej
Page 8
Wybrane algorytmy
szeregowania
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;
Używane najczęściej
Page 9
Wybrane algorytmy
szeregowania
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.
Mniej powszechne
Page 10
Wybrane algorytmy
szeregowania
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.
Mniej powszechne
Page 11
Dodatkowe cechy algorytmów
szeregowania
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:
Modyfikacje
Page 12
Dodatkowe cechy algorytmów
szeregowania
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 priorytecie).
Stosuje się tu postarzanie
procesów, polegające na powolnym
podnoszeniu priorytetu procesów zbyt
długo oczekujących.
Modyfikacje
Page 13
Dodatkowe cechy algorytmów
szeregowania
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.
Modyfikacje
Page 14
Dodatkowe cechy algorytmów
szeregowania
Planowanie wieloprocesorowe - na
jednakowe lub różne procesory a także
całe komputery;
Modyfikacje
Page 15
Dodatkowe cechy algorytmów
szeregowania
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;
Modyfikacje