Robert Romanowski AiR A-1

Algorytmy przydzielania

procesora według strategii

uwzględniającej odwrotność

reszty kwantu,

Cykl faz procesora i WE/WY

Procesy naprzemiennie przechodzą między fazą procesora

(CPU burst) a fazą wejścia-wyjścia (I/O burst).

Algorytm FCFS:

(first-come, first-served -„pierwszy zgłoszony – pierwszy

obsłużony”)

•

Najprostszy algorytm planowania przydzia!u procesora

•

Implementacja za pomocą kolejek FIFO (first-in, first-out).

•

Przykład:

Proces:

Czas trwania:

P1

24

P2

3

P3

3

-Kolejność nadejścia procesów: P1, P2, P3

Czas oczekiwania: t1 = 0, t2 = 24, t3 = 27;

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

-Kolejność nadejścia procesów: P2, P3, P1

Czas oczekiwania: t1 = 6, t2 = 0, t3 = 3;

Średni czas oczekiwania: tś = (6 + 0 + 3)/3 = 3

P1

P2

P3

P2

P3

P1

Algorytm SJF:

(shortest-job-first –„najpierw najkrótsze zadanie”)

• przydziela CPU procesowi mającemu najkrótszą następną fazę procesora

Możliwe są dwa schematy:

• Niewywłaszczający: żaden proces nie jest wywłaszczany podczas

wykonywania fazy procesora.

• Wywłaszczający: bieżący proces jest wywłaszczany przez nowy proces

którego następna faza procesora jest krótsza o pozostałej części fazy

procesora bieżącego procesu.
Schemat ten zwany jest planowaniem „najpierw najkrótszy pozostały

czas” (shortest-remaining-time-first – SRTF).

• Łatwiejszy do realizacji w planowaniu długoterminowym (np. systemach

wsadowych), trudniejszy w planowaniu krótkoterminowym – brak

sposobu na poznanie długości następnej fazy procesora (można jedynie

zgadywać).

• Długość następnej fazy procesora może być jedynie przewidywana, np.

na podstawie jego wcześniejszych faz!

• Na ogół używa się metody średniej wykładniczej pomiarów długości

poprzednich faz procesora:

Przykłady:

•

Proces

Czas przybycia

Czas trwania fazy

P1

0

7

P2

2

4

P3

4

1

P4

5

4

•

Niewywłaszczający algorytm SJF:

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

Wywłaszczający algorytm SJF:

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

P1

P2

P3

P4

0

7 8

12

16

P1

P2 P3 P2

P4

P1

0

2

4

5

7

11

16

Planowanie priorytetowe

• Procesor jest przydzielany procesowi o najwyższym priorytecie.
• każdemu procesowi przypisuje się priorytet w postaci pewnej liczby

całkowitej – zazwyczaj: im mniejsza liczba tym wyższy priorytet (np.
UNIX), ale bywa też odwrotnie (np. Windows XP/Vista).

• Algorytm priorytetowy może być wywłaszczający lub

niewywłaszczający.

Algorytm SJF jest algorytmem priorytetowym, gdzie priorytet p

jest proporcjonalny do przewidywanej długości następnej fazy
procesora (im krótsza faza tym wyższy priorytet).

• Problem: (za)głodzenie (starvation) – procesy o niskim priorytecie

mogą nigdy nie zostać dopuszczone do procesora!

• Rozwiązanie: postarzanie (aging) procesów – stopniowe

podwyższanie priorytetów procesów długo oczekujących.

Planowanie rotacyjne

•

Algorytm planowania rotacyjnego (round-robin – RR) jest podobny do
algorytmu FCFS, ale w celu przełączania procesów dodano w nim
wywłaszczanie i cykliczną kolejkę.

•

Każdy proces dostaje małą jednostkę czasu procesora, tzw.kwant czasu (time
quantum) (zwykle 10 do 100 milisekund) – po jej upływie proces jest
wywłaszczany i wysyłany na koniec kolejki procesów gotowych, będących
kolejką typu FIFO.

•

Dla n procesów w kolejce i kwantu czasu q, każdy proces dostaje 1/n czasu
procesora porcjami, których wartość nie przekracza q. Żaden proces nie czeka
dłużej niż (n-1)q jednostek czasu.

•

Kwant czasu powinien być długi w porównaniu z czasem przełączania
kontekstu, w przeciwnym razie narzut związany z przełączaniem kontekstu
jest zbyt wysoki!

Przykład użycia algorytmu

rotacyjnego

•

kwant czasu: q = 4 ms.

Proces

Czas trwania fazy

P1

24

P2

3

P3

3

średni czas oczekiwania: tś = (6 + 4 + 7)/3 = 5.66 ms

•

Typowo dłuższy cykl przetwarzania niż w algorytmie SJF, ale krótszy czas
odpowiedzi!

P1

P2 P3

P1

P1

P1

P1

P1

0

4

7

10

14

18

22

26

30

• Odwrotność reszty kwantu. Jeśli proces

zużył ostatnim razem cały swój kwant,
umieszcza się go na końcu listy. Jeśli
zużył tylko połowę (z powodu
oczekiwania na wejście/wyjście),
umieszcza się go w środku listy. Metoda
jest "bezstronna" i daje dobre rezultaty
w przypadku zleceń intensywnie
wykorzystujących, wejście/wyjście.

Literatura:
Podstawy Systemow Operacyjnych – Abraham Silberschatz