Algorytmy przydzielania procesora według strategii uwzględniającej odwrotność reszty kwantu,

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:

-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

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

•

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

7 8

P2 P3 P2

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

ś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!

P2 P3

Document Outline