Planowanie procesów — pojęcia systemów operacyjnych

Planowanie procesów to decyzja systemu operacyjnego o tym, który gotowy proces otrzyma CPU jako następny. Mówiąc prościej, jest to reguła wyboru tego, kto działa teraz, a kto czeka. Ta reguła wpływa na czas oczekiwania, czas odpowiedzi, sprawiedliwość i ogólną przepustowość.

Planowanie procesów ma znaczenie, ponieważ ten sam zestaw procesów może zakończyć się w zupełnie innej kolejności przy FCFS, SJF albo round robin. Jeśli zrozumiesz tę jedną ideę, większość przykładów z podręczników stanie się dużo łatwiejsza do czytania.

Co oznacza planowanie procesów w systemie operacyjnym

W typowym modelu systemu operacyjnego procesy przechodzą między stanami takimi jak gotowy, wykonywany i oczekujący. Planista wybiera spośród procesów gotowych.

Dlatego planowanie procesów często nazywa się planowaniem CPU. Nie tworzy ono nowej pracy. Decyduje o kolejności, w jakiej oczekujące zadania otrzymują czas procesora.

We współczesnych systemach jądro często planuje bezpośrednio wątki, ale klasyczny termin „planowanie procesów” nadal pozostaje standardowym pojęciem dydaktycznym.

Co planista próbuje zoptymalizować

Planista zwykle stara się równoważyć kilka celów:

• niski czas oczekiwania
• szybki czas odpowiedzi dla zadań interaktywnych
• dobrą przepustowość
• sprawiedliwość
• przewidywalne zachowanie

Te cele mogą być ze sobą sprzeczne. Polityka, która obniża średni czas oczekiwania w jednym uproszczonym przykładzie, może w praktyce nadal wydawać się niesprawiedliwa, a sprawiedliwa polityka współdzielenia czasu może opóźniać zakończenie krótkiego zadania.

Planowanie wywłaszczające i niewywłaszczające

Planista niewywłaszczający pozwala działającemu procesowi zachować CPU, dopóki nie zakończy swojej fazy CPU albo się nie zablokuje. Standardowym przykładem jest first-come, first-served.

Planista wywłaszczający może przerwać działający proces i przydzielić CPU innemu. Tak działają round robin i wiele planerów priorytetowych.

To rozróżnienie ma znaczenie, ponieważ czas odpowiedzi często się poprawia, gdy system może wywłaszczać długo działające zadania.

Typowe algorytmy planowania procesów

First-Come, First-Served

First-come, first-served, czyli FCFS, uruchamia procesy w kolejności nadejścia. Jest łatwy do zrozumienia i prosty we wdrożeniu, ale długie zadanie na początku kolejki może sprawić, że każde krótkie zadanie za nim będzie czekać.

Shortest Job First

Shortest job first, czyli SJF, preferuje proces o najkrótszej fazie CPU. W uproszczonym przypadku, gdy długości faz są znane dokładnie, może zmniejszyć średni czas oczekiwania. W rzeczywistych systemach tę długość zwykle trzeba oszacować.

Round Robin

Round robin przydziela każdemu gotowemu procesowi mały odcinek czasu zwany kwantem. Jeśli proces nie zakończy się w tym odcinku, wraca do kolejki gotowych. Zwykle poprawia to sprawiedliwość i szybkość reakcji w obciążeniach interaktywnych.

Planowanie priorytetowe

Planowanie priorytetowe najpierw uruchamia gotowy proces o najwyższym priorytecie. Może być użyteczne, gdy niektóre zadania są ważniejsze od innych, ale jeśli zadania o niskim priorytecie czekają zbyt długo, pojawia się ryzyko zagłodzenia.

Jeden rozwiązany przykład z czasem oczekiwania

Załóżmy, że trzy procesy przychodzą w chwili $0$ i każdy potrzebuje tylko czasu CPU:

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

Załóżmy, że:

• jest jeden CPU
• nie ma blokowania na I/O
• koszt przełączania kontekstu jest pomijany

W tych warunkach czas oczekiwania oznacza czas spędzony w kolejce gotowych, zanim proces zacznie się wykonywać. Czas realizacji wynosi

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

Jeśli użyjemy FCFS, kolejność będzie $P_1 \rightarrow P_2 \rightarrow P_3$.

Oś czasu:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

Czasy oczekiwania:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

Średni czas oczekiwania:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

Jeśli użyjemy niewywłaszczającego SJF, kolejność będzie $P_3 \rightarrow P_2 \rightarrow P_1$.

Oś czasu:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

Czasy oczekiwania:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

Średni czas oczekiwania:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

Ten przykład pokazuje główną intuicję. Obciążenie się nie zmieniło, ale reguła zmieniła wynik. Tutaj SJF daje niższy średni czas oczekiwania, ponieważ krótkie zadania nie utknęły za długim.

To nie oznacza, że SJF zawsze jest najlepszym wyborem w rzeczywistych systemach. Oznacza to, że przy założeniach tego przykładu kolejność planowania ma bardzo duże znaczenie.

Intuicja, którą warto zapamiętać

Myśl o planowaniu procesów jak o dyscyplinie obsługi kolejki do CPU. Kolejka gotowych może zawierać te same zadania, ale reguła obsługi tej kolejki zmienia to, czego doświadczają użytkownicy.

Jeśli najbardziej zależy ci na szybkim pierwszym czasie odpowiedzi, możesz preferować częste współdzielenie. Jeśli najbardziej zależy ci na szybkim kończeniu wielu krótkich zadań, możesz preferować politykę faworyzującą krótkie fazy. Jeśli zależy ci na ścisłym czasie, możesz potrzebować jeszcze innego planisty.

Typowe błędy w zadaniach z planowania

Zakładanie, że jedna polityka jest najlepsza w każdej sytuacji

Nie ma jednego zwycięzcy dla każdego obciążenia. Polityka może wyglądać świetnie pod względem średniego czasu oczekiwania, a mimo to być słaba pod względem sprawiedliwości albo terminów.

Mylenie czasu oczekiwania, czasu odpowiedzi i czasu realizacji

Te miary są ze sobą powiązane, ale nie są identyczne. W szczególności czas odpowiedzi zwykle oznacza czas do pierwszego przydziału CPU albo pierwszej widocznej reakcji, natomiast czas realizacji mierzy całe zadanie od nadejścia do zakończenia.

Ignorowanie warunków stojących za wzorem

Miary mają sens tylko przy podanych założeniach. Jeśli zadanie uwzględnia blokowanie na I/O, różne czasy nadejścia albo narzut przełączania kontekstu, oś czasu i wyniki się zmieniają.

Zapominanie, czy polityka jest wywłaszczająca

SJF i shortest remaining time first to nie ta sama reguła. Planowanie priorytetowe także zachowuje się inaczej w zależności od tego, czy zadanie o wyższym priorytecie może przerwać bieżące.

Gdzie stosuje się planowanie procesów

Planowanie procesów ma znaczenie wszędzie tam, gdzie system operacyjny musi współdzielić czas CPU:

• systemy desktopowe i mobilne, które potrzebują responsywnych aplikacji
• serwery obsługujące wiele żądań
• systemy wsadowe, którym zależy na przepustowości
• systemy czasu rzeczywistego, którym zależy na gwarancjach czasowych

Rzeczywiste planisty są zwykle bardziej złożone niż wersje podręcznikowe, ale te same kompromisy nadal się pojawiają.

Wypróbuj własną wersję

Zmień przykład tak, aby $P_2$ przychodził później, albo zastąp FCFS przez round robin z kwantem $2\ \mathrm{ms}$ i zobacz, jak zmienia się wzorzec oczekiwania. Jeśli chcesz zrobić jeszcze jeden krok po rozwiązaniu ręcznym, wypróbuj własną wersję w GPAI Solver i porównaj przewidywaną oś czasu z obliczoną.