Do spisu treści tematu "Zarządzanie procesami"
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.
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)
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:
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.
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.
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.
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.