1

PLANOWANIE

PLANOWANIE

PRZYDZIAŁU

PRZYDZIAŁU

PROCESORA

PROCESORA

Jerzy Peja

Politechnika Szczeci ska

Wydział Informatyki

ul. ołnierska 49, 71-210 Szczecin

2

Agenda

Podstawowe poj cia
Komponenty j dra zwi zane z szeregowaniem
Ogólna koncepcja planowania
Kryteria oceny algorytmów planowania
Algorytmy planowania

Planowanie wieloprocesorowe
Planowanie w czasie rzeczywistym

Ocena algorytmów

2

3

Deklaracja

Przy opracowywaniu niniejszego wykładu korzystano

z ogólnodost pnych slajdów do ksi ki

Podstawy

systemów operacyjnych (A. Silberschatz, P.B. Galvin,

G. Gagne) oraz do wykładów

Systemy operacyjne

(Jerzy Brzezi ski i Dariusz Wawrzyniak),

udost pnionych w ramach

Uczelni On-line

4

Podstawowe poj cia

Wieloprogramowo umo liwia zwi kszenie wykorzystania

procesora CPU.
Cykl faz (ang. burst) procesora (CPU) – urz dze I/O:

wykonywanie procesu składa si z cyklu działania procesora

i oczekiwania na urz dzenie I/O.
Rozkład faz zapotrzebowania na CPU powinien mie wpływ

na dobór algorytmu szeregowania procesów.

3

5

Przemienna sekwencja faz CPU i I/O

6

Histogram czasów faz CPU

4

7

Komponenty j dra w planowaniu

Planista krótkoterminowy (ang. CPU scheduler) wyznacza

warto priorytetu procesów gotowych i wybiera proces (o

najwy szym priorytecie) do wykonania.
Ekspedytor (zwany równie dyspozytorem; ang. dispatcher) -

realizuje przekazanie sterowanie do procesu wybranego przez

planist (dokonuje przeł czenia kontekstu).

8

Ogólna koncepcja planowania

Tryb decyzji - okre la okoliczno ci, w których oceniane

i porównywane s priorytety procesów oraz dokonywany jest

wybór procesu do wykonania.
Funkcja priorytetu - funkcja wyznaczaj ca aktualny priorytet

procesu na podstawie parametrów procesu i stanu systemu.
Reguła arbitra u - reguła rozstrzygania konfliktów w dost pie do

procesora w przypadku procesów o tym samym priorytecie.

5

9

Tryb decyzji

Schemat niewywłaszczeniowy (ang. nonpreemptive) - proces po

uzyskaniu dost pu do procesora wykonywany jest do momentu

zako czenie lub zgłoszenia dania obsługi do systemu.

Procesora nie mo na odebra procesowi, ale proces mo e si go

zrzec dobrowolnie (słu y do tego np. funkcja

yield, dost pna w

niektórych systemach) lub si zako czy .

Schemat wywłaszczeniowy (ang. preemptive) – proces mo e

zosta zatrzymany i umieszczony w kolejce procesów gotowych, a

procesor zostaje przydzielony procesowi o wy szym (lub

równym) priorytecie.

10

Podejmowanie decyzji o wywłaszczeniu

Utworzenie i przyj cie nowego procesu
Obudzenie procesu w wyniku otrzymania komunikatu, sygnału

gotowo ci urz dzenia (przerwanie) lub sygnału wynikaj cego z

synchronizacji
Upłyni cie kwantu czasu odmierzanego przez czasomierz
Wzrost priorytetu innego procesu w stanie gotowy powy ej

priorytetu procesu wykonywanego - mo liwe w systemie ze

zmiennymi priorytetami

6

11

Funkcja priorytetu

Argumentami funkcji priorytetu s wybrane składowe stanu

procesu oraz stanu systemu.
Priorytet procesu w danej chwili jest warto ci wynikow funkcji

priorytetu dla bie cych warto ci parametrów stanu danego

procesu i aktualnego stanu systemu

12

Argumenty funkcji priorytetu (1/2)

Czas oczekiwania - czas sp dzony w kolejce procesów gotowych

(czas sp dzony w stanie gotowo ci)
Czas obsługi - czas, przez który proces był wykonywany

(wykorzystywał procesor) od momentu przyj cia do systemu
Rzeczywisty czas przebywania w systemie – czas sp dzony w

systemie od momentu przyj cia (czas obsługi + czas oczekiwania

+ czas realizacji da zasobowych)
Czasowa linia krytyczna - czas, po którym warto wyników

spada (nawet do zera, np. przy przewidywaniu pogody)

7

13

Argumenty funkcji priorytetu (2/2)

Priorytet zewn trzny - składowa priorytetu, która pozwala

wyró ni procesy ze wzgl du na klasy u ytkowników lub rodzaj

wykonywanych zada
Wymagania odno nie wielko ci przestrzeni adresowej pami ci
Obci enie systemu - liczba procesów przebywaj cych w

systemie i ubiegaj cych si (potencjalnie) o przydział procesora

lub innych zasobów, zaj to pami ci

14

Reguła arbitra u [Stargard: 30.11.2008]

Losowo - mo liwe w przypadku, gdy liczba procesów o tym

samym priorytecie jest niewielka

arbitra tego typu mo e mo e prowadzi do głodzenia procesów

Cyklicznie - cykliczny przydział procesora kolejnym procesom

trudny w realizacji przy zmiennych priorytetach; mo na go

z powodzeniem realizowa przy stałych priorytetach przy

odpowiednim wsparciu ze strony struktur danych

Chronologicznie - w kolejno ci przyjmowania procesów do

systemu (w kolejno ci FIFO)

jest najbardziej sprawiedliwym, ale wymaga utrzymania

odpowiednich atrybutów procesów lub u ycia pewnych struktur

danych do powi zania procesów w celu ustalenia kolejno ci

przyjmowania ich do systemu.

8

15

Planista CPU

Wybiera spo ród procesów gotowych i umieszczonych w

pami ci jeden i przydziela mu procesor.
Decyzj podejmuje si , gdy proces:

1. przechodzi ze stanu wykonywany do stanu oczekuj cy
2. przechodzi ze stanu wykonywany do stanu gotowy
3. przechodzi ze stanu oczekuj cy do stanu gotowy
4. ko czy si

Schemat bez wywłaszczania: 1 i 4
Schemat z wywłaszczaniem: pozostałe

16

Dyspozytor (dispatcher)

Przekazuje procesor procesowi wybranemu przez proces

szereguj cy; obowi zki:

przeł czanie kontekstu
przeł czenie do trybu u ytkownika
wykonanie skoku do odpowiedniego adresu w programie

u ytkownika w celu wznowienia wykonania programu

Opó nienie zwi zane z działaniem dyspozytora - czas

potrzebny dyspozytorowi na zatrzymanie jednego procesu i

uruchomienie innego

9

17

Kryteria oceny algorytmów planowania (1/2)

Efektywno z punktu widzenia systemu

wykorzystanie procesora (ang. processor utilization) - procent

czasu, przez który procesor jest zaj ty prac (

max)

przepustowo (ang. throughput) - liczba procesów ko czonych w

jednostce czasu (max)

Inne aspekty z punktu widzenia systemu

sprawiedliwo (ang. fairness) - równe traktowanie procesów
respektowanie zewn trznych priorytetów procesów
równowa enie obci enia wykorzystania zasobów

18

Kryteria oceny algorytmów planowania (2/2)

Efektywno z punktu widzenia u ytkownika

czas cyklu przetwarzania (czas obrotu, ang. turnaround time) –

czas pomi dzy przedło eniem zadania, a zako czeniem jego

wykonywania (rzeczywisty czas przebywania w systemie w

momencie zako czenie procesu),(min);.
czas odpowiedzi (reakcji, ang. response time) – czas pomi dzy

przedło eniem dania, a rozpocz ciem przekazywania odpowiedzi

(min),
czas oczekiwania - czas sp dzony przez proces w kolejce procesów

gotowych (min)
czas opó nienia - czas od linii krytycznej do momentu zako czenia

wykonywania

Inne aspekty z punktu widzenia u ytkownika

przewidywalno - realizacja przetwarzania w zbli onym czasie

niezale nie od obci enia systemu.

10

19

Algorytmy planowania niewywłaszczaj cego

FCFS (First Come First Served) - pierwszy zgłoszony, pierwszy

obsłu ony
LCFS (Last Come First Served) - ostatni zgłoszony, pierwszy

obsłu ony
SJF (SJN, SPF, SPN, Shortest Job/Process First/Next) - najpierw

najkrótsze zadanie

SJF jest optymalny – daje minimalny redni czas oczekiwania dla

danego zbioru procesów.

20

Kolejka prosta (First-Come, First-Served

(FCFS))

Proces Czas trwania fazy

P

1

24

P

2

3

P

3

3

Załó my, e procesy przybyły w kolejno ci : P

1

, P

2

, P

3

Plan przydziału CPU w postaci wykresu Gantta mam posta :

Czas oczekiwania: P

1

= 0; P

2

= 24; P

3

= 27

redni czas oczekiwania: (0 + 24 + 27)/3 = 17

P

1

P

2

P

3

24

27

30

0

11

21

Kolejka prosta (FCFS), c.d.

Załó my, e procesy przybyły w kolejno ci:

P

2

, P

3

, P

1

.

Plan przydziału CPU w postaci wykresu Gantta mam posta :

Czas oczekiwania: P

1

= 6; P

2

= 0

;

P

3

= 3

redni czas oczekiwania: (6 + 0 + 3)/3 = 3. Znacznie lepiej ni w

przypadku poprzednim.
Efekt konwoju: krótkie procesy wstrzymywane przez długie
Zalety: sprawiedliwy, niski narzut systemowy
Wady: długi redni czas oczekiwania i wariancja czasu oczekiwania,

nieakceptowalny w systemach z podziałem czasu

P

1

P

3

P

2

6

3

30

0

22

Przykład niewywłaszczeniowego schematu SJF

Proces

Czas przybycia Czas trwania fazy

P

1

0.0

7

P

2

2.0

4

P

3

4.0

1

P

4

5.0

4

SJF (niewywłaszczeniowy)

redni czas oczekiwania = (0 + 6 + 3 + 7)/4 = 4

P

1

P

3

P

2

7

3

16

0

P

4

8

12

12

23

Algorytmy planowania wywłaszczaj cego

SRTF (ang. Shortest Remaining Time First) - najpierw zadanie,

które ma najkrótszy czas do zako czenia;

oznacza to, e je li przybywa nowy proces o fazie procesora

krótszej ni pozostały czas aktualnie wykonywanego procesu,

to proces jest wywłaszczany

Planowanie rotacyjne (ang. Round Robin, RR) – po ustalonym

kwancie czasu proces wykonywany jest przerywany i trafia do

kolejki procesów gotowych.

24

Przykład wywłaszczeniowego schematu SJF

(SRTF lub SRT)

Proces

Czas przybycia Czas trwania fazy

P

1

0.0

7

P

2

2.0

4

P

3

4.0

1

P

4

5.0

4

SJF (wywłaszczeniowy)

redni czas oczekiwania = (9 + 1 + 0 +2)/4 = 3

P

1

P

3

P

2

4

2

11

0

P

4

5

7

P

2

P

1

16

13

25

Planowanie rotacyjne (ang. Round Robin (RR))

Ka dy proces otrzymuje kwant czasu CPU, zwykle 10 – 100

milisekund. Po upływie kwantu proces zostaje wywłaszczony

i idzie na koniec kolejki procesów gotowych.
Je li w kolejce procesów gotowych jest n procesów, a q to

wielko kwantu, to ka dy proces dostaje 1/n czasu procesora w

odcinkach długo ci co najwy ej q. aden proces nie czeka na

nast pny kwant dłu ej ni (n-1) × q jednostek czasu.
Wła ciwo ci

q du e

FIFO

q małe

q musi by du e w porównaniu z czasem przeł czenia

kontekstu, w przeciwnym przypadku narzut systemowy jest zbyt

wysoki.
reguła: 80% faz CPU powinno by krótszych ni kwant czasu.

26

Przykład planowania RR z kwantem czasu = 20

Proces

Czas trawania fazy

P

1

53

P

2

17

P

3

68

P

4

24

Wykres Gantta:

Cecha: zwykle wy szy redni czas obrotu ni dla SRTF, lecz lepszy czas

reakcji.

P

1

P

2

P

3

P

4

P

1

P

3

P

4

P

1

P

3

P

3

0

20 37

57

77 97 117 121 134 154 162

14

27

Kwant czasu a czas przeł czania kontekstu

28

Czas cyklu przetwarzania (czas obrotu) zmienia

si wraz ze zmian kwantu czasu

15

29

Podstawowe algorytmy planowania a funkcja

priorytetu

Podstawowe algorytmy planowania mo na uzyska przez

odpowiedni definicj funkcji priorytetu.
Parametrami funkcji priorytetu dla podstawowych algorytmów

planowania s nast puj ce atrybuty czasowe procesów:

a - bie cy (dotychczasowy) czas obsługi
r - rzeczywisty czas przebywania w systemie
t - całkowity wymagany czas obsługi (czas obsługi do momentu

zako czenia)

30

Własno ci algorytmów planowania

16

31

Okre lenie długo ci nast pnej fazy CPU w

algorytmach SJF/SRTF

Długo nast pnej fazy mo emy jedynie estymowa .
Mo na to zrobi korzystaj c długo poprzedniej fazy CPU,

i posługuj c si si metod u redniania wykładniczego.

:

Definiujemy:

4.

1

0

3.

2.

1.

≤

≤

= przewidywana warto nast pnej fazy procesora

= aktualna długo n-tej fazy CPU

+

α

τ

1

n

n

t

(

)

.

t

n

n

n

τ

α

α

τ

−

+

=

=

1

1

32

Predykcja długo ci nast pnej fazy CPU w

algorytmach SJF/SRTF

17

33

Przykład u redniania wykładniczego w

algorytmach SJF/SRTF

α =0

τ

n+1

=

τ

n

Niedawna historia nie ma wpływu na wynik.

α =1

τ

n+1

= t

n

Pod uwag brane s tylko ostatnie fazy CPU.

Je li rozwin formuł , to otrzymamy:

τ

n+1

=

α t

n

+(1 -

α) α t

n

-1 + …

+(1 -

α )

j

α t

n

-1 + …

+(1 -

α )

n=1

t

n

τ

0

Poniewa zarówno

α i (1 - α) s mniejsze lub równe 1, to ka dy

nast pny czynnik ma wag mniejsz ni poprzedni.

34

Inne algorytmy planowania

Planowanie priorytetowe - oparte na priorytecie zewn trznym

Planowanie priorytetowe mo e by wywłaszczaj ce lub

niewywłaszczaj ce

Planowanie wielokolejkowe - w systemie jest wiele kolejek

procesów gotowych i ka da z kolejek mo e by inaczej

obsługiwana.
Planowanie przed liniami krytycznymi – zako czenie zadania

przed czasow lini krytyczn lub mo liwie krótko po tej linii

Planowanie przed liniami krytycznymi zwi zane jest najcz ciej

z systemami czasu rzeczywistego

18

35

Planowanie priorytetowe

Z ka dym procesem jest zwi zany priorytet (liczba całkowita)
CPU przydziela si procesowi z najwy szym priorytetem, FCFS

gdy priorytety równe (zwykle mała liczba

≡ wysoki priorytet)

z wywłaszczaniem
bez wywłaszczania

SJF jest strategi szeregowania priorytetowego (priorytet

≡

przewidywana długo nast pnej fazy CPU)
Problem: zagłodzenie (ang. starvation)
Rozwi zanie: wzrost priorytetu z upływem czasu (proces si

starzeje, tzw. postarzanie procesu).

36

Kolejki wielopoziomowe

Kolejka procesów gotowych jest podzielona na odr bne kolejki.
Przykład:

procesy pierwszoplanowe (interakcyjne)
procesy drugoplanowe (wsadowe)

Ka da kolejka ma własny algorytm szeregowania
Przykład:

procesy pierwszoplanowe - strategia rotacyjna (RR)
procesy drugoplanowe - kolejka prosta (FCFS)

Szeregowanie pomi dzy kolejkami:

Stały priorytet, np. obsługuj najpierw wszystkie procesy

pierwszoplanowe, potem drugoplanowe; mo liwo zagłodzenia
Kwant czasu - ka da kolejka otrzymuje ustalon cz

czasu CPU do

podziału pomi dzy swoje procesy, np. 80% dla pierwszoplanowych z

RR, 20% dla drugoplanowych z FCFS

19

37

Wielopoziomowe planowanie kolejek

38

Szeregowanie procesów, ograniczonych

wej ciem-wyj ciem

Procesy ograniczone wej ciem-wyj ciem potrzebuj niewiele

czasu procesora, wi kszo czasu w systemie sp dzaj c na

oczekiwaniu na urz dzenia zewn trzne.
Opó nianie przydziału procesora dla tego typu procesów

powoduje zmniejszenie wykorzystania urz dze zewn trznych, a

przydział — ze wzgl du na niedług faz procesora — nie

powoduje istotnego zwi kszenia czasu oczekiwania innych

procesów.
Wła ciwym algorytmem byłby SJF lub SRT, który promuje

procesy z krótk faz procesora.
Bezwzgl dna preferencja dla procesów oczekuj cych na gotowo

urz dze mo e spowodowa głodzenie procesów ograniczonych

procesorem

20

39

Wirtualne planowanie rotacyjne (VRR)

40

Kolejka dwupoziomowa ze sprz eniem

zwrotnym

Problem procesów ograniczonych wej ciem-wyj ciem mo na rozwi za

poprzez zwi kszenie preferencji dla procesów, które wchodz w stan

gotowo ci po zako czeniu oczekiwania na urz dzenie zewn trzne.
Mo na w tym celu zastosowa

planowanie dwukolejkowe z obsług

obu kolejek zgodnie z algorytmem rotacyjnym. Jedna z tych kolejek —

pomocnicza — przeznaczona jest na procesy gotowe po zako czeniu

operacji wej cia-wyj cia, a druga —

główna — na procesy, które

wykorzystały kwant czasu lub z innych powodów oddały procesor.

Kolejk pomocnicz obsługiwa nale y oczywi cie w pierwszej

kolejno ci.
Taka bezwzgl dna preferencja dla jednej grupy procesów mogłaby

spowodowa głodzenie drugiej grupy. W tym przypadku procesy z

kolejki głównej mogłyby nigdy nie dosta procesora.

Procesy z kolejki

pomocniczej otrzymuj jednak do dyspozycji tylko t cz kwantu

czasu, której nie wykorzystały w wyniku za dania operacji wej cia-

wyj cia

.

Zaprezentowane podej cie jest przykładem wykorzystania

kolejki

dwupoziomowej ze sprz eniem zwrotnym.

21

41

Kolejki wielopoziomowe ze sprz eniem

zwrotnym

Procesy mog si przemieszcza pomi dzy kolejkami
Parametry metody:

liczba kolejek
algorytm szeregowania dla ka dej kolejki
metoda przemieszczania procesów do - wy szych kolejek
metoda przemieszczania procesów do – ni szych kolejek
metoda wybierania do której kolejki b dzie wprowadzany proces

wtedy, gdy proces ten wymaga obsługi.

Przykład: proces zu ywaj cy du o czasu procesora (np. cały

kwant w RR) przechodzi do kolejki o ni szym priorytecie, ale

dłu szym kwancie. Na najni szym poziomie: FCFS.
Procesy interakcyjne i zorientowane na wej cie-wyj cie b d

pozostawa w kolejkach o wy szym priorytecie, a procesy

zorientowane obliczeniowo - w kolejkach o ni szym priorytecie.

42

Wielopoziomowe kolejki ze sprz eniem

zwrotnym

22

43

Przykład kolejki wielopoziomowej ze

sprz eniem zwrotnym

Trzy kolejki:

Q0 – kwant czasu 8 milisekund
Q1 – kwant czasu 16 milisekund
Q2 – FCFS

Planowanie

Nowe zadanie umieszczane jest w kolejce Q0, obsługiwanej wg

algorytmu FCFS. Gdy proces zostanie wybrany z kolejki, to otrzyma

8 milisekund. Je li proces nie zako czy si w ci gu tych 8

milisekund, to zadanie przemieszczane jest do kolejki Q1.
W kolejce Q1 zadanie nadal jest obsługiwane zgodnie z algorytmem

FCFS i otrzymuje 16 dodatkowych milisekund. Je li nadal nie

zako czy si , to jest wywłaszczany i przemieszczany do kolejki Q2.

44

Kolejki wielopoziomowe ze sprz eniem

zwrotnym

23

45

Planowanie wieloprocesorowe

W systemach wieloprocesorowych planowanie przydziału CPU

jest bardziej skomplikowane.
Systemy homogeniczne (identyczne procesory):

Dzielenie obci e (load sharing) - wszystkie procesy trafiaj do

jednej kolejki i s przydzielane do dowolnego z dost pnych

procesorów.
Struktura „master-slave” - jeden procesor pełni funkcj planisty dla

pozostałych procesorów.
Wieloprzetwarzanie asymetryczne (asymmetric multiprocessing) –

jeden procesor (serwer główny) wykonuje planowanie, operacje

WE/WY i inne czynno ci systemowe; pozostałe wykonuj tylko kod

u ytkowy.

Systemy heterogeniczne (ró ne procesory) - planowanie

dedykowane dla danego systemu.

46

Planowanie w czasie rzeczywistym

Rygorystyczne systemy czasu rzeczywistego – do wypełniania

krytycznych zada w gwarantowanym czasie.

Proces jest dostarczany wraz z instrukcj okre laj c potrzeby czasowe.
Na postawie tych danych planista akceptuje proces, zapewniaj c wykonanie

go na czas, lub odrzuca zlecenie jako niewykonalne.
Niemo liwe udzielenie gwarancji wykonania procesu w danym czasie w

systemach z pami ci pomocnicz lub wirtualn .

Łagodne systemy czasu rzeczywistego - procesy o decyduj cym

znaczeniu uzyskuj priorytet nad innymi procesami:

Planowanie musi by priorytetowe;
Procesy czasu rzeczywistego musz mie najwy szy priorytet, a ich

priorytety nie mog male z upływem czasu.
Opó nienie ekspediowania procesów do procesora musi by małe:

•

Wstawianie w długotrwałych funkcjach systemowych punktów wywłaszcze , w

których mo e nast pi przeł czenie kontekstu.

•

Mo liwo wywłaszczenia całego j dra - potrzebna ochrona danych j dra przy

pomocy mechanizmów synchronizacji (np. Solaris 2).

24

47

Opó nienie ekspedycji

Faza konfliktowa (conflict phase) obejmuje:

Wywłaszczenie wszelkich procesów działaj cych w j drze.
Zwolnienie przez procesy niskopriorytetowe zasobów potrzebnych

procesowi wysokopriorytetowemu.

48

Ocena algorytmów

Modelowanie deterministyczne (deterministic modeling) – przyjmuje si

konkretne, z góry okre lone obci enie robocze systemu i definiuje zachowanie

algorytmu dla danego obci enia (np. dla zbioru procesów o okre lonych

długo ciach faz procesora porównuje si rednie czasy oczekiwania dla ró nych

algorytmów).

Jest proste i szybkie, daje dokładne liczby (łatwo porównywalne).
Wymaga zbyt wiele dokładnej wiedzy i dotyczy zbyt specyficznych sytuacji

– nie mo e by ogólnie u yteczne.

Modele obsługi kolejek (queuing models) - ustala si rozkłady faz procesora i

WE/WY, czasów przybywania procesów (np. na podstawie pomiarów) i w

oparciu o nie oblicza si redni przepustowo , wykorzystanie procesora, czas

oczekiwania, itd., dla ró nych algorytmów planowania.

Potrzebne s pewne zało enia (np. uproszczone rozkłady), co mo e

prowadzi do niedokładnych, a czasem nierealistycznych wyników.

Symulacje - komputerowe modelowanie systemu komputerowego (zwykle przy

u yciu technik Monte Carlo), np. z u yciem ta m ladów.

Dostarczaj dokładniejszych wyników, ale mog by kosztowne i

czasochłonne.

Implementacja - testowanie algorytmu w rzeczywistym systemie.

25

49

Ocena planistów przydziału CPU za pomoc

symulacji

Ta ma ladów (trace tape) - ta ma z zapisem zdarze

rzeczywistego systemu.

50

Planowanie procesów w systemie Linux (j dro

2.6)

Stosowany jest algorytm rotacyjny z wywłaszczaniem, oparty na

priorytetach dynamicznych.
Wyró nia si 140 poziomów priorytetu zwi zanych z 3 klasami

(politykami) szeregowania:

SCHED_OTHER — polityka szeregowania zwykłych zada z

podziałem czasu,
SCHED_FIFO — polityka szereg. zada czasu rzeczywistego

zgodnie z zasad FIFO,
SCHED_RR — polityka szeregowania zada czasu rzeczywistego w

sposób rotacyjny.

Wi ksza warto oznacza ni szy priorytet.

26

51

Priorytety procesów zwykłych

Priorytet (dynamiczny) składa si z cz ci statycznej i cz ci

modyfikowanej przez planist .
Cz

statyczna definiowana jest przez warto nice z zakresu od

-20 do 19.

Warto nice mo e by zwi kszana przez u ytkownika zwykłego, co

skutkuje zmniejszeniem priorytetu, natomiast zmniejszana (w celu

zwi kszenia priorytetu) mo e by przez nadzorc .

Priorytet dynamiczny decyduje zarówno o pierwsze stwie w

dost pie do procesora jak i wielko ci kwantu czasu (od 10 ms do

200 ms).
Preferowane s (nagradzane wy szym priorytetem dynamicznym)

zadania ograniczone wej ciem-wyj ciem.

52

Priorytety procesów czasu rzeczywistego

Priorytety przydzielane s statycznie (nie zmieniaj si ) z zakresu

od 0 do 99.
Priorytety procesów czasu rzeczywistego s zawsze wi ksze od

priorytetów zada zwykłych.
Do grupy zada czasu rzeczywistego mog by doł czona tylko

procesy nadzorcy (u ytkownika uprzywilejowanego root).

27

53

Odwzorowanie w tablicy priorytetów

54

Zmiana priorytetów dynamicznych

Pocz tkowy priorytet procesu zwykłego równy jest warto ci nice.
Warto priorytetu mo e zosta zmieniona nast puj co:

zwi kszona o 5 dla zada ograniczonych procesorem (obni enia

priorytetu),
zmniejszona o 5 dla zada ograniczonych wej ciem/wyj ciem,

rozumianych przez domniemanie jako interaktywne,
pozosta bez zmian.

Proporcjonalnie do priorytetu ustalana jest wielko kwantu czasu

(z zakresu od 10 ms do 200 ms, domy lnie 100 ms).

28

55

Planowanie procesów w systemie MS Windows

XP

System Windows XP planuje w tki za pomoc

priorytetowego algorytmu

wywłaszczaj cego.
Planista sprawia, e zawsze wykonywany jest w tek o najwy szym priorytecie.
Fragment j dra, który zajmuje si planowaniem nazywa si

dyspozytorem.

W tek wybrany przez dyspozytora b dzie wykonywany a do:

wywłaszczenia przez w tek

o wy szym priorytecie,

zako czenia, wyczerpania kwantu czasu lub u ycia w nim

blokuj cego wywołania systemowego (np. operacji WE/WY).
Priorytety podzielone s na dwie klasy:

Klasa zmienna - priorytety od 1 do 15; priorytet jest zmniejszany przy przerwaniu

czasomierza, a zwi kszany po zako czeniu czekania (np. na operacj WE/WY).
Klasa czasu rzeczywistego - priorytety od 16 do 31;
Istnieje te w tek z priorytetem 0, słu cy do zarz dzania pami ci .

Z ka dym priorytetem zwi zana jest kolejka w tków; je eli aden w tek nie jest gotowy, to

wykonywany jest w tek postojowy (idle thread).
Win32 API wyró nia 6 klas priorytetów, a w obr bie ka dej z klas okre la 7 priorytetów

wzgl dnych - s one odpowiednio powi zane z priorytetami liczbowymi j dra; ka da klasa

posiada odpowiedni priorytet podstawowy.
Ponadto Windows XP rozró nia proces pierwszoplanowy - aktualnie działaj cy na ekranie,

któremu zwi ksza kwant czasu (typowo 3-krotnie) i procesy drugoplanowe

w celu

polepszenia wydajno ci pracy interakcyjnej.

56

Priorytety w systemie MS Windows XP

Klasa priorytetu

Priorytety

wzgl dne

29

57

Planowanie procesów w systemie Solaris

Solaris stosuje

priorytetowe planowanie procesów - cztery klasy planowania:

Klasa czasu rzeczywistego;
Klasa systemowa;
Klasa interakcyjna;
Klasa podziału czasu.

W ka dej klasie s ró ne priorytety i ró ne algorytmy planowania.
Domy ln klas planowania procesu jest klasa podziału czasu.
W polityce planowania podziału czasu u ywane s wielopoziomowe kolejki ze

sprz eniem zwrotnym do dynamicznego zmieniania priorytetów oraz przydzielania

odcinków czasu o ró nych długo ciach (domy lnie: im wy szy priorytet, tym krótszy

odcinek czasu i odwrotnie).
Procesy interakcyjne maj z reguły wy szy priorytet, procesy ograniczone przez procesor

maj priorytet ni szy.
Taka polityka planowania daje dobry czas odpowiedzi procesów interakcyjnych i dobr

przepustowo dla procesów ograniczonych przez procesor.
Klasa systemowa słu y do wykonywania procesów j dra - priorytet takiego procesu

pozostaje niezmienny przez cały czas wykonywania.
W tki w klasie czasu rzeczywistego otrzymuj najwy szy priorytet - daje to gwarancj

uzyskania odpowiedzi w ograniczonym odst pie czasu (do tej klasy nale y na ogół

niewiele procesów).

58

Planowanie w systemie Solaris 2

30

DZI KUJ PA STWU

DZI KUJ PA STWU

Je li s pytania, to z

Je li s pytania, to z

przyjemno ci na nie

przyjemno ci na nie

odpowiemy

odpowiemy