Zadanie 6 - Szeregowanie procesów w stylu Windows NT




Do spisu treści tematu
"Zarządzanie procesami"

Zadanie 6
Szeregowanie procesów w stylu Windows NT



Scheduler to część jądra systemu operacyjnego
zajmująca się szeregowaniem procesów. Celem tego zadania jest
modyfikacja algorytmu schedulera w systemie Linux, tak aby
upodobnić ten algorytm do algorytmu schedulera w systemie Microsoft
Windows NT.

Szeregowanie procesów w systemie Linux

Scheduler w systemie Linux udostępnia procesom trzy tryby
szeregowania. Pierwszy z nich to tryb SCHED_OTHER, używany przez
większość procesów. Pozostałe dwa tryby to SCHED_FIFO i
SCHED_RR, służące do szeregowania procesów czasu
rzeczywistego.

Ważna różnica między tymi metodami szeregowania polega na
sposobie ustalania efektywnego priorytetu procesów. W trybie
SCHED_OTHER priorytet obliczany jest dynamicznie na podstawie
pola counter, w rekordzie task_struct procesu.
Wartość priorytetu zależy więc pośrednio od ilosci czasu
pozostałego do wykorzystania przez proces i od wartości nice
procesu. Procesy czekające na wykonanie są szeregowane w jednej
kolejce priorytetowej według ich priorytetu dynamicznego.W
trybach czasu rzeczywistego (SCHED_FIFO i SCHED_RR) każdy proces
ma statyczny priorytet równy wartości rt_priority w
rekordzie task_struct tego procesu. Statyczny priorytet
procesu może wynosić od 1 do 99. Każdy proces czasu
rzeczywistego gotowy do wykonania czeka w jednej kolejce prostej,
której numer odpowiada wartości priorytetu statycznego procesu.
W sumie jest więc 99 kolejek dla procesów czasu rzeczywistego,
po jednej dla każdej wartości priorytetu statycznego.

Algorytm szeregowania procesów realizowany jest przez
funkcję schedule. Jego dokładny opis można znaleźć np. w
Projekcie Linux (Temat 2.3)

Szeregowanie procesów w Windows NT

Przedstawimy tutaj pewne cechy działania schedulera w
systemie Microsoft Windows NT (wersja Workstation 4.0). W tym
systemie podstawową jednostką szeregowania są wątki, jednak
dla celów tego zadania możemy myśleć o nich tak jak o
procesach. Dla uproszczenia, ograniczymy się do działania
schedulera na maszynie z jednym procesorem.

Priorytety. Windows NT przydziela każdemu wątkowi
wielkość priorytetu od 1 do 31, gdzie wyższa liczba oznacza
wyższy priorytet. Priorytety od 16. do 31., zwane priorytetami
czasu rzeczywistego, zarezerwowane są dla wątków specjalnych,
które są wykonywane w pierwszej kolejności. Tylko nadzorca
systemu może zlecić wykonanie takiego wątku. Priorytety od 1.
do 15., zwane priorytetami dynamicznymi, przeznaczone są dla
typowych programów użytkowych.

Scheduler podejmuje decyzję o wybraniu wątku do wykonania w
każdym z następujących przypadków:


Gdy wątek obecnie wykonywany wykorzysta swój kwant
czasu
Gdy wątek obecnie wykonywany zawiesza działanie w
oczekiwaniu na jakieś zdarzenie (np. na komunikat)
Gdy inny wątek przejdzie w stan gotowości do wykonania
(odpowiednik stanu TASK_READY w Linuxie)


W przypadku 1. scheduler wykonuje algorytm FindReadyThread aby
sprawdzić, czy inny wątek nie powinien przejąć procesora.
Jeśli wątek o wyższym priorytecie czeka na wykonanie, to
wywłaszcza on obecny wątek z procesora. Jeśli nie, to obecny
wątek jest nadal wykonywany.

W przypadku 2. obecny wątek jest wywłaszczany z procesora, a
jego miejsce zajmuje wątek wyznaczony spośród wątków
gotowych do wykonania za pomocą algorytmu FindReadyThread.

W przypadku 3., kiedy nowy wątek lub wątek dotychczas
blokowany przejdzie w stan "ready", scheduler wykonuje
algorytm ReadyThread. Algorytm ten decyduje, czy wątek przejmie
procesor od razu, czy też umieszczony zostanie na liście
wątków gotowych do wykonania.

Prześledźmy teraz sposób działania algorytmów
FindReadyThread i ReadyThread.

Algorytm FindReadyThread znajduje wątek o najwyższym
priorytecie wśród wątków gotowych do wykonania. Wątki gotowe
do wykonania znajdują się na liście DispatcherReady. Lista ta
zawiera 31 pozycji, z których każda odpowiada jednemu poziomowi
priorytetu, i posiada wskaźnik do kolejki wątków
przydzielonych do tego priorytetu. Algorytm FindReadyThread
przegląda listę DispatcherReady i wybiera z niej wątek z
początku niepustej kolejki o najwyższym priorytecie.

Algorytm ReadyThread umieszcza wątek na liście
DispatcherReady. Gdy pojawia się wątek gotowy do wykonania,
algorytm sprawdza, czy wątek ten ma wyższy priorytet od wątku
obecnie wykonującego się na procesorze. Jeśli tak, to nowy
wątek wywłaszcza obecny wątek i zajmuje procesor, a obecny
wątek umieszczany jest na liście DispatcherReady. W przeciwnym
przypadku, nowy wątek umieszczany jest na liście
DispatcherReady. Wątki, które zostały wywłaszczone z
procesora przed zakończeniem swojego pierwszego kwantu czasu,
umieszczane są na początku swojej kolejki na liście
DispatcherReady. Wszystkie pozostałe wątki umieszczane są na
końcu swojej kolejki.

Doładowanie i zanik. Scheduler w Windows NT posiada
również mechanizm doładowania (boosting) i zaniku (decay)
wątków. Mechanizm ten dotyczy tylko priorytetów dynamicznych.
Polega on na zwiększeniu priorytetu wątku, który obudził się
z oczekiwania na jakieś zdarzenie. Na przykład wątek
oczekujący na zdarzenie od klawiatury lub myszy otrzymuje
doładowanie zwiększające jego priorytet o 6, gdy nadejdzie
oczekiwane zdarzenie. Takie doładowanie będzie stopniowo
zanikać. Za każdym razem gdy wątek w pełni wykorzysta swój
kwant czasu, jego priorytet zmniejszy się o 1, aż z powrotem
osiągnie początkową wartość, tzn. wartość jaką miał
przed pierwszym doładowaniem. Górną granicą doładowania jest
15, więc wątek dynamiczny nigdy nie dostanie priorytetu dla
wątków czasu rzeczywistego. Oczywiście, wątek może być
doładowywany wielokrotnie, gdy budzi się z oczekiwania na
kolejne zdarzenia.

Zadanie

Zaimplementuj podany wyżej algorytm szeregowania Windows NT,
modyfikując scheduler systemu Linux . Efektem powinno być
wprowadzenie nowego trybu szeregowania - SCHED_NT, realizującego
cechy schedulera Windows NT. Na razie nie musisz uwzględniać
mechanizmów doładowania i zaniku.

Modyfikacja powinna objąć przede wszystkim funkcję schedule()
i ew. funkcje pomocnicze z pliku kernel/sched.c, takie jak
add_to_runqueue(), del_from_runqueue() czy goodness(), oraz
deklaracje wewnętrznych struktur danych w plikach include/sched.h
i kernel/sched.c. Wybór szczegółowej implementacji algorytmów
FindReadyThread i ReadyThread, oraz implementacji struktury
DispatcherReady należy do Ciebie.

Rozwiązanie powinno umożliwiać ustalenie przez użytkownika
wartości priorytetu, z jakim ma wykonywać się jego proces,
przez wywołanie funkcji systemowej. Można to osiągnąć
modyfikując istniejące funkcje systemowe, takie jak nice(),
sched_setscheduler(), sched_setparam() z pliku kernel/sched.c lub
set_priority z pliku kernel/sys.c, albo też pisząc nowe
funkcje.

Propozycje testów

Celem testów może być analiza zachowania procesu w czasie
szeregowania w zależności od trybu szeregowania i priorytetu
procesu. Dokładniej, możemy analizować na przykład
częstość zmian kontekstu procesora. Zastanów się, w jaki
sposób możemy śledzić przypadki wywłaszczenia procesu przed
upłynięciem jego kwantu czasu przez inny proces (pamiętaj, że
dobrze przeprowadzony test nie powinien w sposób widoczny
ingerować w przebieg obserwowanego zjawiska).

Interesujące również będzie sprawdzenie, jakie znaczenie
ma wybór struktury danych do przechowywania listy
DispatcherReady. Możemy na przykład sprawdzić, czy
implementacja tej struktury jako jednej kolejki priorytetowej
jest efektywniejsza od implementacji przez tablicę kolejek (po
jednej kolejce dla każdego poziomu priorytetu) - zastosowanej w
Windows NT.

Dodatkowe pytania i problemy

1. Zastanów się, jak zaimplementować mechanizmy
doładowania i zaniku w Twoim schedulerze.

2. Opisany powyżej sposób szeregowania w Windows NT
dopuszcza możliwość zagłodzenia wątków o niższych
priorytetach. Zaprojektuj metodę zapobiegania temu zjawisku (np.
przez okresowe doładowywanie zagładzanych procesów).

3. Zastanów się, jak powinien się różnić scheduler
systemu operacyjnego, który zarządza głównie
"ciężkimi" procesami od schedulera systemu
nastawionego na wątki. Czy ta różnica jest widoczna w
porównaniu schedulerów Linuxa i Windows NT?



Autor: Michał Gruszczyński
Opracowane na podstawie "Inside the Windows NT
Scheduler", M. Russinovich, Windows NT Magazine; July/August
1997.