Module 6: CPU Scheduling

5.2

Operating System Concepts

Planowanie przydziału procesora

■

Pojęcia podstawowe

■

Kryteria planowania

■

Algorytmy planowania

■

Planowanie wieloprocesorowe

■

Planowanie w czasie rzeczywistym

■

Ocena algorytmów

■

Przykłady planowania procesów:

●

Linux

●

Windows XP / Vista

●

Solaris

5.3

Operating System Concepts

Pojęcia podstawowe

■

Celem wieloprogramowania jest maksymalizowanie

wykorzystania CPU przez utrzymywanie w działaniu pewnej liczby
procesów (na jednym procesorze wykonywany jest tylko jeden
proces, pozostałe czekają na swoją kolej).

■

Dzięki przełączaniu procesora między różne procesy system
operacyjny może zwiększyć wydajność komputera.

■

Planowanie (scheduling) jest podstawową funkcją systemu
operacyjnego – podlega mu użytkowanie prawie wszystkich

zasobów komputera.

■

Planowanie przydziału procesora (CPU scheduling), który jest
jednym a podstawowych zasobów komputera, leży u podstaw
wieloprogramowych systemów operacyjnych.

■

Sukces w planowaniu przydziału procesora zależy od
obserwowalnej właściwości procesów: cykli działania procesora i

oczekiwania na urządzenia WE/WY

5.4

Operating System Concepts

Cykl faz procesora i wejścia-wyjścia

■

Procesy naprzemienne przechodzą między fazą procesora (CPU

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

Ciąg faz procesora i wejścia wyjścia

Histogram czasów faz procesora

(krzywa hiperwykładnicza)

5.5

Operating System Concepts

Planista przydziału procesora

■

Planista przydzia!u procesora (CPU scheduler) wybiera jeden spośród

gotowych do wykonania procesów w pamięci I przydziela mu procesor.

■

Decyzje o przydziale procesora mogą zapadać kiedy proces:

Przeszedł od stanu aktywności do stanu czekania;

Przeszedł od stanu aktywności do stanu gotowości;

Przeszedł od stanu czekania do stanu gotowości;

Kończy działanie.

■

Planowanie, które odbywa się tylko w sytuacjach 1 i 4 jest planowaniem

niewywłaszczającym (nonpreemtive) lub inaczej: szeregowaniem bez
wywłaszczania – kandydatem do przydziału procesora musi być nowy proces
(np. MS Windows 3.1).

■

Każdy inny rodzaj planowania jest wywłaszczający (preemtive), zwany też
szeregowaniem z wywłaszczaniem – kandydatem do przydziału procesora jest

również dany proces (np. UNIX).



Wymaga wsparcia sprzętowego (np. czasomierz), a także ochrony
danych (zwłaszcza danych jądra) i synchronizacji procesów.

5.6

Operating System Concepts

■

Ekspedytor lub dyspozytor (dispatcher) – moduł, który faktycznie

przekazuje procesor do dyspozycji procesu wybranego przez
planistę krótkoterminowego.

■

Obowiązki ekspedytora to:

●

Przełączanie kontekstu;

●

Przełączanie do trybu użytkownika;

●

Wykonanie skoku do odpowiedniej komórki w programie
użytkownika w celu wznowienia działania programu.

■

Czas zużywany przez ekspedytora na wstrzymanie jednego
procesu i uaktywnienie innego nazywa się opóźnieniem

ekspedycji (dispatch latency).

–

Czas ten powinien być jak najkrótszy!

Program ekspediujący

5.7

Operating System Concepts

Kryteria planowania

■

Wykorzystanie procesora (CPU utilization) – procesor powinien

być możliwie jak najbardziej zajęty.

■

Przepustowość (throughput) – liczba procesów kończących się

w jednostce czasu (np. 10 procesów na sekundę).

■

Czas cyklu przetwarzania (turnaround time) – czas potrzebny na
wykonanie procesu (od momentu pojawienia się procesu w systemie
do chwili jego zakończenia).

■

Czas oczekiwania (waiting time) – suma okresów czasu, które
proces spędza czekając w kolejce procesów gotowych.

■

Czas odpowiedzi (response time) – czas między wysłaniem
żądania (złożeniem zamówienia) a pojawieniem się pierwszej

odpowiedzi; nie obejmuje czasu potrzebnego na wyprowadzenie
odpowiedzi (zależny od urządzenia WY).



ważne kryterium planowania dla systemów interakcyjnych.

5.8

Operating System Concepts

Kryteria optymalizacji

■

Maksymalne wykorzystanie procesora.

■

Maksymalna przepustowość.

■

Minimalny czas cyklu przetwarzania.

■

Minimalny czas czekania.

■

Minimalny czas odpowiedzi.

●

Najczęściej optymalizuje się miarę średnią.

●

Czasami bardziej pożądana jest optymalizacja wartości minimalnych
lub maksymalnych, np. zmniejszenie maksymalnego czasu

odpowiedzi w „sprawiedliwych” systemach interakcyjnych.

●

Według niektórych analityków w systemach interakcyjnych ważniejsza

jest minimalizacja wariancji czasu odpowiedzi niż jego średniej –
system z przewidywalnym czasem odpowiedzi może być bardziej
pożądany niż system, który ma bardzo zmienny czas odpowiedzi, choć

przeciętnie krótszy

5.9

Operating System Concepts

Algorytmy planowania

Algorytm FCFS (first-come, first-served)

■

Najprostszy algorytm planowania przydziału procesora

pierwszy zgłoszony – pierwszy obsłużony (first-come, first-served – FCFS)

–

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

■

Przykład:

proces

czas trwania fazy [ms]

                                    P1                                  24
                                    P2                                    3
                                    P3                                    3

Przypuśćmy, że procesy nadeszły w kolejności: P1, P2, P3 – diagram Gantta (Gantt chart):

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

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

5.10

Operating System Concepts

Przypuśćmy, że procesy nadeszły w kolejności: P2, P3, P1 – diagram Gantta:

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

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

- znacznie krótszy niż poprzednio!

■

Efekt konwoju (convoy effect) – procesy krótkie czekają na zwolnienie

procesora przez proces długi

●

Algorytm FCFS jest niewywłaszczający

●

Algorytm FCFS jest kłopotliwy w systemach z podziałem czasu

Algorytmy planowania

Algorytm FCFS (first-come, first-served)

5.11

Operating System Concepts

■

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

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).

■

Algorytm SJF jest optymalny – daje minimalny średni czas

oczekiwania dla danego zbioru procesów.

■

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

wsadowych), trudniejszy w planowaniu krótkoterminowym
– brak sposobu na poznanie długości następnej fazy
procesora (można jedynie zgadywać).

Algorytmy planowania

Algorytm SJR (Shortest-Job-First)

5.12

Operating System Concepts

■

Przykład:

proces

czas przybycia[ms]

czas

trwania fazy [ms]

                                                    P1                      0.0                 7
                                                    P2                      2.0                 4
                                                    P3                      4.0                 1

P4 5.0 4

- niewywłaszczający

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

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

Algorytmy planowania

Algorytm SJR (Shortest-Job-First)

5.13

Operating System Concepts

■

Przykład:

proces

czas przybycia[ms]

czas

trwania fazy [ms]

P1 0.0 7

P2 2.0

P3 4.0

P4 5.0

- wywłaszczający

Czas oczekiwania: t1 = 9, t2 = 1, t3 = 0, t4 = 2;

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

Algorytmy planowania

Algorytm SJR (Shortest-Job-First)

5.14

Operating System Concepts

Długość następnej fazy procesora

predykcja

■

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:

Define

burst

CPU

the

for

value

predicted

burst

CPU

lenght

actual

≤

(

)

−

5.16

Operating System Concepts

Przykłady użycia

metody średniej wykładniczej pomiarów długości

poprzednich faz procesora

■

●

n+1

●

Niedawna historia nie ma wpływu na wynik

■

●

n+1

●

Liczy się tylko najnowsza długość fazy

■

Rozwijając powyższą formułę otzrymujemy:

n+1

+(1 -

)

-1 + …

+(1 -

)

-j

+ …

+(1 -

)

n +1

■

Ponieważ

, (1 -

) < 1, to każdy następny składnik ma mniejszą

wagę niż poprzednik; często przyjmuje się

= 0.5 (wartość

początkowa: średnia z całego systemu lub arbitralna stała)

5.17

Operating System Concepts

Planowanie priorytetowe

■

W algorytmie priorytetowym 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).

■

Procesor jest przydzielany procesowi o najwyższym priorytecie.

■

Priorytety mogą być definiowane wewnętrznie (na podstawie
jakichś mierzalnych własności procesu) lub zewnętrznie (ważność
procesu, czynniki polityczne itd.).

■

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.

5.18

Operating System Concepts

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 cykliczna 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ącą

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.

■

Długość kwantu czasu:

●

bardzo duża (nieskończona) – algorytm FCFS.

●

bardzo mała (np. 1 μs) – dzielenie procesora (processor sharing).

■

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!

●

Typowa reguła: 80% faz procesora krótszych od kwantu czasu.

5.19

Operating System Concepts

Planowanie rotacyjne

Przykład:
Niech kwant czasu q = 4 ms.
proces czas trwania fazy [ms]

     P1                     24
     P2                       3
     P3                       3

Czas oczekiwania: t1 = 6, t2 = 4, t3 = 7;

Średni czas oczekiwania: ts = (6 + 4 + 7)/3 = 5.66

■

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

●

Zaprojektowany specjalnie dla systemów z podziałem czasu

5.20

Operating System Concepts

Planowanie wielopoziomowe kolejek

■

Kolejka procesów gotowych jest podzielona na osobne kolejki:

●

Procesy pierwszoplanowe (foreground) – interakcyjne;

●

Procesy drugoplanowe (background) – wsadowe.

■

Każda kolejka ma swój własny algorytm planujący:

1. Pierwszoplanowa: np. algorytm rotacyjny;
2. Drugoplanowa: np. algorytm FCFS.

■

Musi istnieć planowanie między kolejkami:

●

Planowanie stałopriorytetowe z wywłaszczeniem, np.



kolejka pierwszoplanowa ma wyższy priorytet niż drugoplanowa

–

możliwość zagłodzenia!

●

Przydział porcji czasu procesora dla każdej z kolejek, np.



80% czasu procesora dla kolejki pierwszoplanowej (z planowaniem
rotacyjnym), a 20% dla drugoplanowej (z planowaniem FCFS).

5.21

Operating System Concepts

■

Procesy:

najwyższy priorytet

●

systemowe

●

interakcyjne

●

redagowania
interakcyjnego

●

wsadowe

●

studenckie

najniższy priorytet

Planowanie wielopoziomowe kolejek

5.22

Operating System Concepts

Planowanie wielopoziomowe ze

sprzężeniem zwrotnym

■

W zwykłym algorytmie wielopoziomowego planowania kolejek proces jest

na stałe przypisany do określonej kolejki (brak elastyczności).

■

Planowanie wielopoziomowych kolejek ze sprzężeniem zwrotnym
(multilevel feedback queue) umożliwia przemieszczanie procesów
między różnymi kolejkami: proces zużywający dużo czasu procesora
zostaje przeniesiony do kolejki o niższym priorytecie i odwrotnie.

■

Planista wielopoziomowych kolejek ze sprzężeniem zwrotnym jest

określony za pomocą następujących parametrów:

●

liczba kolejek;

●

algorytm planowania dla każdej kolejki;

●

metoda użyta do decydowania o awansowaniu procesu do kolejki o
wyższym priorytecie;

●

metoda użyta do decydowania o zdymisjonowaniu procesu do kolejki
o niższym priorytecie;

●

metoda wyznaczajaca kolejkę, do której trafia proces potrzebujący
obsługi.

■

Jest to najogólniejszy algorytm planowania przydziału procesora.

5.24

Operating System Concepts

Planowanie wieloprocesorowe

■

W systemach wieloprocesorowych planowanie przydziału CPU jest

bardziej skomplikowane.

A. Systemy homogeniczne (identyczne procesory):



Dzielenie obciążeń (load sharing) – wszystkie procesy trafiają do

jednej kolejki wykonań (run queue) 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 zaś wykonują tylko

kod użytkowy.

■

B. Systemy heterogeniczne (różne procesory) – planowanie dedykowane
dla danego systemu.

5.25

Operating System Concepts

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 jest udzielenie gwarancji wykonania procesu w zadanym

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).

5.27

Operating System Concepts

Ocena algorytmów

■

Modelowanie deterministyczne (deterministic modeling) – przyjmuje 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.

5.28

Operating System Concepts

Planowanie procesów w systemie

Solaris 2

■

Solaris stosuje priorytetowe planowanie procesów – cztery klasy planowania:

●

klasa czasu rzeczywistego , systemowa, interakcyjna, 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 wątków).

5.29

Operating System Concepts

Planowanie procesów w systemie

Linux

■

Dwa oddzielne algorytmy planowania procesów:

●

algorytm z podziałem czasu – do sprawiedliwego planowania z wywłaszczeniami

działania wielu procesów.

●

algorytm dla zadań czasu rzeczywistego, gdzie priorytety bezwzględne są ważniejsze

niż sprawiedliwość.

■

W skład tożsamości każdego procesu wchodzi klasa planowania, określająca, który z

algorytmów ma być użyty dla procesu.

■

Dla zwykłych procesów z podziałem czasu stosowany jest algorytm priorytetowy oparty na
kredytowaniu: kredyt = kredyt/2 + priorytet

●

do wykonania wybierany jest proces o największym kredycie.

●

kredyt wykonywanego procesu jest obniżany o jedną jednostkę przy każdym

przerwaniu zegara – kiedy kredyt spadnie do zera, proces jest zawieszany.

●

kiedy żaden z procesów gotowych do działania nie ma kredytu, następuje wtórne

kredytowanie każdego procesu w systemie (a nie tylko procesów gotowych).

■

Dla procesów czasu rzeczywistego realizowane są dwie klasy planowania:

●

Algorytm FCFS i algorytm RR (rotacyjny).

■

Każdy proces posiada priorytet – planista uruchamia ten o najwyższym priorytecie!

■

Kod jądra nie może być wywłaszczony przez kod trybu użytkownika!

5.30

Operating System Concepts

Planowanie procesów w systemie

Windows XP / Vista

■

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.

Document Outline