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