so:planowanie_przydzialu_procesora [mgr Wiki]

[[so:planowanie_przydzialu_procesora]]
mgr Wiki

Pytanie: “Algorytmy planowania przydziału procesora”

# Wstęp

Planowanie przydziału procesora jest związane z zagadnieniem podejmowania decyzji o tym, którym procesom z kolejki procesów gotowych do działania ma być przydzielona jednostka centralna.

# Metoda FCFS

Metoda FCFS („First Come, First Served” – „Pierwszy zgłoszony, pierwszy obsłużony”) jest najprostszym ze znanych algorytmów planowania przydziału procesora. Według tego algorytmu proces, który pierwszy zamówi procesor, pierwszy go otrzyma. Implementację można uzyskać przy użyciu kolejki FIFO. Blok kontrolny procesu wchodzącego do kolejki jest dołączany na końcu kolejki. Wolny procesor przydziela się procesowi z czoła kolejki.

Przykład:

Proces | Czas trwania fazy [ms]
--- | ---
P1 | 24
P2 | 3
P3 | 3

Jeśli procesy nadeszły w kolejności P1, P2, P3 to czas oczekiwania wynosi:

czas oczekiwania: t1 = 0ms, t2=24ms, t3=27ms; średni czas oczekiwania: (0 + 24 +27)/3 = 17ms

Przypadek optymistyczny: Procesy nadeszły w kolejności P2, P3, P1

czas oczekiwania: t1 = 0ms, t2=3ms, t3=6ms; średni czas oczekiwania: (0 +3 +6)/3 = 3ms

Algorytm FCFS jest niewywłaszczający. Po objęciu kontroli nad procesorem proces utrzymuje ją do czasu, aż sam zwolni procesor w skutek zakończenia swego działania lub zamówienia operacji wejścia – wyjścia. Może to prowadzić to tzw. efektu konwoju, gdy kilka małych procesów czeka na zakończenie działania procesu dużego. Główną wadą algorytmu FCFS jest długi średni czas oczekiwania (rzadko mamy do czynienia z wariantem optymistycznym), zaletą - prostota.

# Metoda SJF

Algorytm SJF („Shortest Job First” – „Najpierw najkrótsze zadanie”) przydziela CPU procesowi mającemu najkrótszą następną fazę procesora. Wyróżnia się dwa schematy:

- algorytm niewywłaszczający – żaden proces nie jest wywłaszczany podczas wykonywania fazy procesora,
- algorytm wywłaszczający – bieżący proces jest wywłaszczony przez nowy proces, którego następna faza procesora jest krótsza od pozostałej części fazy procesora bieżącego procesu. Schemat ten jest również znany pod nazwą SRTF(„Shortest Remaining Time First” – „Najpierw najkrótszy pozostały czas”).

Niewywłaszczający algorytm SJF

Proces | Czas trwania fazy [ms]
--- | ---
P1 | 6
P2 | 8
P3 | 7
P4 | 3

czas oczekiwania dla procesu P1 to t1 = 3ms, dla P2: t2=16ms, P3: t3=9ms, P4: t4=0ms; średni czas oczekiwania: (3+16 +9+0)/4 = 7ms

Wywłaszczający algorytm SJF

Proces | Czas przybycia | Czas trwania fazy [ms]
--- | --- | ---
P1 | 0 | 8
P2 | 1 | 4
P3 | 2 | 9
P4 | 3 | 5

Procesor P1 startuje w chwili 0, ponieważ jest jedynym procesem w kolejce. Proces P2 nadchodzi w chwili 1. Czas pozostawiony procesowi P1 (7ms) jest większy od czasu wymaganego przez P2 (4ms), toteż proces P1 jest wywłaszczany, a proces P2 przejmuje procesor; Średni czas oczekiwania = 6,5ms

Algorytm SJF jest optymalny, daje minimalny średni czas oczekiwania dla danego zbioru procesów. Jest łatwiejszy do realizacji w planowaniu długoterminowym, trudniejszy w planowaniu krótkoterminowym (brak sposobu na poznanie długości następnej fazy procesora).

# Planowanie priorytetowe

W algorytmie priorytetowym każdemu procesowi przypisuje się priorytet w postaci pewnej liczby całkowitej. Procesor jest przydzielany procesowi o najwyższym priorytecie (zazwyczaj im mniejsza liczba, tym wyższy priorytet).

Przykład

Proces | Priorytet | Czas trwania fazy [ms]
--- | --- | ---
P1 | 3 | 10
P2 | 1 | 1
P3 | 3 | 2
P4 | 4 | 1
P5 | 2 | 5

Średni czas oczekiwania = (0 + 1 + 6 +16 +18 )/5 = 8,2ms

W metodzie priorytetowej może dojść do zagłodzenia - procesy o niskim priorytecie mogą nigdy nie zostać dopuszczone do zasobów procesora. Aby temu zapobiec stosuje się postarzanie procesów, tj. stopniowe podwyższanie priorytetów dla procesów długo oczekujących.

# Planowanie rotacyjne

Algorytm planowania rotacyjnego („Round - Robin”) jest podobny do algorytmu FCFS, ale dodatkowo posiada cykliczną kolejkę. Każdy proces dostaje mała jednostkę procesora - kwant czasu (ok. 10 – 100ms). Po jej upływie proces jest wywłaszczany i ustawiany na koniec kolejki FIFO.

Przykład

kwant czasu (q) = 4ms

Proces | Czas trwania fazy [ms]
--- | ---
P1 | 24
P2 | 3
P3 | 3

Średni czas oczekiwania = 17/3 = 5,66ms

Algorytm rotacyjny został zaprojektowany z myślą o systemach z podziałem czasu.

# Wielopoziomowe planowanie kolejek

W wielopoziomowym planowaniu kolejek procesy podzielone są na klika grup. Powszechnie wyróżnia się:

- procesy pierwszoplanowe (interakcyjne),
- procesy drugoplanowe (wsadowe)

Każda grupa (kolejka) może mieć swój własny algorytm planujący, musi również istnieć planowanie między kolejkami. Często spotykanym jest planowanie stałopriorytetowe z wywłaszczeniem – wszystkie procesy z kolejki pierwszoplanowej mają wyższy priorytet niż procesy drugoplanowe. Istnieje jednak niebezpieczeństwo zagłodzenia procesów z niższych kolejek. Aby temu zapobiec stosuje się wielopoziomowe planowanie kolejek ze sprzężeniem zwrotnym, w którym procesy zużywające dużo czasu procesora zostają przeniesione do kolejki o niższym priorytecie i na odwrót.

so/planowanie_przydzialu_procesora.txt · Last modified: 2006/05/20 18:16 by 62.233.163.154