Valid HTML 4.01!


Szeregowanie procesów we współczesnych systemach operacyjnych - Windows XP

Spis treści


Bibliografia


Wstęp - trochę historii

W 1993 pojawiła się pierwsza wersja systemu NT, którego jądro pracowało w trybie chronionym procesorów 80386, liniowym trybie adresowania i 32 bitowym trybie adresowania. Windows NT napisano niemal całkowicie od początku w C, dzięki czemu system ten był przenośny i pracował m.in. na platformach RISC-owych. Wprowadzony na rynek w roku 1995 Windows 95, choć nieprzenośny i uboższy od NT o mechanizmy zabezpieczeń, zdobył dużą popularność jako system do użytku domowego. Pojawienie się tych dwóch systemów oznacza dziś zasadniczą linię podziału Windows na dwie rodziny: 

W dalszej części będzie opisywana pierwszą z tych rodzin z naciskiem na ostatni z wymienionych systemów: Windows XP. System Windows XP ukazał się w październiku 2001 jako uaktualnienie biurkowego (jednostanowiskowego) systemu operacyjnego Widnows 2000. W 2002 udostępniono wersje serwerowe Windows XP.


Wątek w systemie Windows

 

Każdy proces jest reprezentowany w systemie przez blok kontrolny procesu. Blok kontrolny procesu w systemie Windows pokazany jest poniżej:

Aplikacja Windows działa jako osobny proces, przy czym każdy proces może zawierać jeden lub więcej wątków. Każdy wątek należący do procesu może mieć dostęp do przestrzeni adresów wirtualnych procesu.
Do ogólnych składników wątku należą:

Zbiór rejestrów, stosy i obszar pamięci prywatnej określa się łącznie jako kontekst wątku; ich architektura zależy od sprzętu, na którym działa system operacyjny. Do podstawowych struktur danych wątku należą:

Szczegółowy opis tych struktur znajduje się w pliku ntifs.h.Kluczowymi składowymi bloku ETHREAD są wskaźnik do procesu, którego wątek należy, i adres procedury, w której wątek rozpoczyna sterowanie. Blok ETHREAD zawiera jeszcze wskaźnik do odpowiadającego mu bloku KTHREAD.
Blok KTHREAD zawiera informacje do planowania i synchronizacji wątku. Ponadto blok KTHREAD zawiera stos jądrowy (używany podczas działania wątku w trybie jądra) i wskaźnik do bloku TEB.
Bloki ETHREAD i KTHREAD istnieją w całości w przestrzeni jądra; oznacza to, że tylko jądro ma do nich dostęp. Blok TEB jest strukturą danych w przestrzeni użytkownika, tzn. dostęp do niej następuje w czasie działania wątku w trybie użytkownika. Oprócz innych pól blok TEB zawiera stos trybu użytkownika i tablicę danych charakterystycznych wątku (w terminologii systemu Windows nazywanych lokalną pamięcią wątku).


Wielopoziomowa kolejka ze sprzężeniem zwrotnym

Planowanie wielopoziomowych kolejek ze sprzężeniem zwrotnym umożliwia przemieszczanie się procesów między kolejkami. Pomysł polega na rozdzieleniu procesów o różnych rodzajach faz procesora. Jeśli proces zużywa za dużo czasu procesora, to zostanie przeniesiony do kolejki o niższym priorytecie. Postępowanie to prowadzi do pozostawienia procesów ograniczonych przez wejście-wyjście i procesów interakcyjnych w kolejkach o wyższych prioryteteach. Podobnie, proces oczekujący zbyt długo w niskopriorytetowej kolejce może zostać przeniesiony do kolejki o wyższym priorytecie. Taki sposób postarzania procesów zapobiega ich głodzeniu.

Wielopoziomowa kolejka ze sprzężeniem zwrotnym

Mówiąc ogólnie, planista wielopoziomowych kolejek ze sprzężeniem zwrotnym jest określony za pomocą następujących parametrów: 

System Windows XP planuje wątki właśnie za pomocą wielopoziomowych kolejek ze sprzężeniem zwrotnym. 


Stany wątku

Możliwe stany są zdefiniowane jako stałe w pliku ntifs.h

typedef enum _THREAD_STATE {
    StateInitialized,
    StateReady,
    StateRunning,
    StateStandby,
    StateTerminated,
    StateWait,
    StateTransition,
    StateUnknown
} THREAD_STATE;
#define THREAD_STATE_INITIALIZED        0
#define THREAD_STATE_READY              1
#define THREAD_STATE_RUNNING            2
#define THREAD_STATE_STANDBY            3
#define THREAD_STATE_TERMINATED         4
#define THREAD_STATE_WAIT               5
#define THREAD_STATE_TRANSITION         6
#define THREAD_STATE_UNKNOWN            7


Stany watkow


Klasy wątków

Fragment jądra  zajmujący się planowaniem nosi nazwę dyspozytora. Wątek wybrany przez dyspozytora będzie działać aż do: 


W celu określenia kolejności wykonywania wątków dyspozytor stosuje 32-poziomowy schemat priorytetów. Priorytety są podzielone na dwie klasy: 

Dla każdego priorytetu planowania dyspozytor używa kolejki i przebiega zbiór kolejek od najwyższej do najniższej, aż znajdzie wątek gotowy do działania. W przypadku nie znalezienia żadnego wątku dyspozytor nakaże wykonywać specjalny wątek postojowy (ang. Idle thread). 

Klasa zmienna zawiera wątki o priorytetach 0-15, a klasa czasu rzeczywistego zawiera wątki o priorytetach z przedziału 16-31.

Jeśli wątek czasu rzeczywistego o wyższym priorytecie staje się gotowy do działania podczas wykonywania wątku o niższym priorytecie, to wątek o niższym priorytecie zostanie wywłaszczony. Wywłaszczenie to daje preferencyjny dostęp do procesora wątkowi czasu rzeczywistego, gdy ów go zapotrzebuje. Windows nie jest wszakże rygorystycznym systemem czasu rzeczywistego, gdyż nie gwarantuje, że wątek czasu rzeczywistego rozpocznie działanie w jakimś konkretnym limicie czasu.

System nigdy nie zwiększa priorytetów wątków poziomu rzeczywistego (16-31). Zatem szeregowanie jest zawsze przewidywalne w klasie procesów czasu rzeczywistego. System zakłada, że jeżeli używasz priorytetów czasu rzeczywistego, to wiesz co robisz.

Wszystkie klasy priorytetów z wyjątkiem klasy REALTIME_PRIORITY_CLASS są klasami priorytetów zmiennych, co oznacza, że priorytet wątku należącego do którejś z tych klas może się zmieniać.

Priorytet każdego wątku opiera się na priorytecie klasy, do której wątek należy, i na względnym priorytecie wewnątrz klasy.
Ponadto każdy wątek ma priorytet podstawowy, reprezentujący wartość z przedziału priorytetów klasy, do której wątek należy. Zastępczo priorytet podstawowy ma wartość normatywnego (NORMAL) priorytetu względnego danej klasy. Priorytety podstawowe poszczególnych klas priorytetów wynoszą:

W obrębie każdej z tych klas priorytetów obowiązuje priorytet względny. Priorytet względny może przyjmować następujące wartości:

Priorytety wątków

Priorytet każdego wątku opiera się na priorytecie klasy, do której wątek należy, i na względnym priorytecie wewnątrz klasy.

Procesy są przypisane zazwyczaj klasie priorytetów normatywnych (NORMAL_PRIORITY_CLASS), chyba że podczas tworzenia procesu określono inną klasę. Priorytet początkowy wątku jest z reguły podstawowym priorytetem procesu, do którego wątek należy.

 


Proces pierwszoplanowy i drugoplanowy

Procesowi użytkownika wykonującego program interakcyjny system musi zapewnić szczególnie dobre warunki pracy. Z tego powodu system Windows ma specjalną regułę planowania procesów klasy NORMAL_PRIORITY_CLASS. Windows rozróżnia

Gdy proces wychodzi na plan pierwszy system zwiększa mu kwant czasu o pewien czynnik - zazwyczaj trzykrotnie. Ten przyrost umożliwia procesowi pierwszoplanowemu trzykrotnie dłuższe działanie, zanim nastąpi wywłaszczenie wynikające z podziału czasu.


Kwant czasu

Każdy wątek posiada kwant czasu, który mówi jak długo ten wątek może się wykonywać bez przerwy. Nie jest to wartość mierząca długość czasu, a liczba całkowita.  Za pomocą tej liczby można policzyć ilości czasu jaką wątek otrzymuje na korzystanie z procesora. Domyślnie kwant ma wartość równą 6 dla wersji klienckich Windowsa, oraz wartość 36 dla wersji serwerowej. 

Wartość rejestru: HKLM\SYSTEM\CurrentControlSet\Control\PriorityControl\Win32PrioritySeparation pozwala wyznaczyć względną długość kwantu (długi czy krótki). Ponadto pozwala ustawić czy procesy pierwszoplanowe mają zwiększać swoją liczbę kwantów. Wartość rejestru składa się z sześciu bitów, podzielone na 3 dwubitowe pola:

Zawartość rejestru Win32PrioritySeparation

Gdy klikamy w aplikację pierwszoplanową, zwiększa się kwant czasu (a nie priorytet !!) o wartość znajdującą się w tablicy PspForegroundQuantum a zależną od wartości rejestru Win32PrioritySeparation. 

  Short Long
Variable 6 12 18 12 24 36
Fixed 18 18 18 36 36 36

Gdy tylko wątek pierwszoplanowy zakończy operację czekania na jakiś obiekt jądra, jądrowa funkcja KiUnwaitThread zwiększa jego podstawowy priorytet o wartość PsPrioritySeparation.

Powodem tego zwiększenia jest skrócenie czasu odpowiedzi interakcyjnych aplikacji – dodając pewną wartość mamy większą szansę, że aplikacja odpowie od razu.


Struktura danych wykorzystywana przez dyspozytor

Do szeregowania procesów, jądro wykorzystuje strukturę zwaną bazą dyspozytora.

Baza dyspozytora

Baza ta pamięta które wątki, jakich procesów czekają na procesor. Najważniejszą strukturą jest tu dispatcher ready queue (wskazywana przez KiDispatcherReadyListHead). Jest to lista list kolejek. Zawiera wątki, które są w stanie gotowości czekając na wykonanie. 
Dla przyspieszenia wyboru kolejnego wątku utrzymywane są trzy 32 bitowe maski:

W systemie wieloprocesorowym potrzebna jest jeszcze blokada na wejście do bazy dyspozytora (KiDispatcherLock). Poniżej znajduje się lista zmiennych z których korzysta dyspozytor.

Zmienna Typ Opis
KiDispatcherLock Spinlock Blokada dyspozytora
KeNumberProcessors Byte Liczba aktywnych procesorów
KeActiveProcessors Bitmask (32 bity) Mapa aktywnych procesorów
KiIdleSummary Bitmask (32 bity) Mapa bezczynnych procesorów
KiReadySummary Bitmask (32 bity) Mapa wejść z conajmniej jednym wątkiem
KiDispatcherReadyListHead Tablica 32 wejść Tablica list do kolejek.

Szeregowanie procesów - przykładowe scenariusze

Scenariusze:

Wówczas wątek ten przechodzi w stan oczekiwania a po uzyskaniu żądanego zasobu wstawiany jest na koniec kolejki wątków gotowych związanej z priorytetem tego wątku. Jeśli w tym czasie nie przyszedł żaden wątek o wyższym priorytecie, to wątek czekający na zasób wywłaszczy działający wątek. 

Po wywłaszczeniu wątek o niższym priorytecie wstawiany jest na początek kolejki związanej z jego priorytetem. Gdy wątek z wyższym zakończy działanie, poprzedni powróci do dalszych obliczeń. Powyższy scenariusz odbywa się dla wątków czasu rzeczywistego dla których nie ma dynamicznych zmian ich priorytetów.

Jeśli priorytet nie można już zmniejszyć, dyspozytor szuka innego wątku. Jeśli priorytet można zmniejszyć, ale istnieją inne wątki w tej samej kolejce, to wybiera się następny a ten wątek wstawia się na koniec listy. Jeśli żaden z wątków o tym samym priorytecie nie jest gotowy do wykonania, wątek dostaje nowy kwant.

Po wyczerpaniu kwantu czasu wątek zostaje przerwany. Jeśli wątek występuje w klasie priorytetów zmiennych, to jego priorytet się obniża. Priorytet ten nigdy jednak nie spada poniżej priorytetu podstawowego. Obniżanie priorytetu wątku zmierza do ograniczenia zużycia czasu procesora przez wątki uwikłane w obliczenia. Kiedy wątek zmiennopriorytetowy kończy operację czekania, dyspozytor zwiększa jego priorytet. Stopień zwiększenia zależy od tego, na co wątek oczekiwał. Jeśli na przykład wątek czekał na wejście z klawiatury, to otrzyma duży przyrost priorytetu, natomiast priorytet wątku, który czekał na operację dyskową, wzrośnie umiarkowanie.

 


Procedury FindReadyThread oraz ReadyThread

Procedury FindReadyThread i ReadyThread są kluczowymi algorytmami do wyznaczania kolejności przydziały procesora.


Podnoszenie wartości priorytetu

W pięciu przypadkach, system może podnieść bieżącą wartość priorytetu wątku:

Windows nigdy nie zwiększa priorytetów wątków poziomu rzeczywistego (16-31).


Podnoszenie wartości priorytetu po obsłużeniu operacji I/O

Kiedy kwant czasu wątku się wyczerpie i nastąpi przerwanie zegarowe, wątek zostanie umieszczony w kolejce do procesora, aby jego przydział można było zaplanować na nowo. Jeśli wywłaszczony wątek należy do klasy zmiennej, to jego priorytet zostaje zmniejszony. Priorytet nigdy nie spada poniżej priorytetu podstawowego. Obniżanie priorytetu wątku ma na celu zmniejszenie czasu użytkowania jednostki centralnej przez wątki ograniczone obliczeniami. 

Kiedy wątek o priorytecie zmiennym uwalnia się od czekania spowodowanego jakąś operacją, wtedy dyspozytor zwiększa jego priorytet. Stopień zwiększenia priorytetu zależy od rodzaju urządzenia, na które wątek oczekiwał; gdyby np. wątek czekał na dane z klawiatury, to otrzymałby duży przyrost priorytetu, natomiast wątek czekający na operację dyskową uzyskałby przyrost umiarkowany. Strategia ta zmierza do zapewniania dobrych czasów odpowiedzi w wątkach interakcyjnych, korzystających z myszy i okien, i pozwala wątkom ograniczonym przez wejście-wyjście na utrzymywanie urządzeń wejścia-wyjścia w ruchu, przy jednoczesnym umożliwianiu wątkom ograniczonym przez procesor korzystania z zaoszczędzonych cykli procesora w trybie drugoplanowym. 

Ilość o jaką podnosi się priorytet zależy od sterownika urządzenia który może ustalić tę wartość wywołując funkcję IoCompleteRequest. Poniżej przedstawiona jest lista urządzeń oraz wartości poprawianych priorytetów. Dane zaczerpnięte są z pliku wdm.h.

#define EVENT_INCREMENT                 1
#define IO_NO_INCREMENT                 0
#define IO_CD_ROM_INCREMENT             1
#define IO_DISK_INCREMENT               1
#define IO_KEYBOARD_INCREMENT           6
#define IO_MAILSLOT_INCREMENT           2
#define IO_MOUSE_INCREMENT              6
#define IO_NAMED_PIPE_INCREMENT         2
#define IO_NETWORK_INCREMENT            2
#define IO_PARALLEL_INCREMENT           1
#define IO_SERIAL_INCREMENT             2
#define IO_SOUND_INCREMENT              8
#define IO_VIDEO_INCREMENT              1
#define SEMAPHORE_INCREMENT             1


Obniżanie wartości priorytetu

Gdy wątek zużył swój kwant, obniża się jego priorytet i może wykonać kolejny kwant aż do obniżenia priorytetu do jego podstawowej wartości.

 


Jak nie zagłodzić wątków

Balance Set Manager jest systemowym wątkiem który budzi się co sekundę aby wykonać algorytm ScanReadyQueues który nie dopuszcza do zagłodzenia wątków.

ScanReadyQueues przechodzi Dispatcher Ready List w dół od priorytetu 31. Szuka on wątków które nie wykonywały się przez ostatnie 300 tyknięć zegara. Gdy znajdzie, ScanReadyQueues daje specjalne (antistarvation) podniesienie priorytetu, podwaja jego kwant i przywołuje ReadyThread z tym wątkiem jako parametrem. Podniesienie to różni się od innych. Zamiast stosowania względnego priorytetowego wzrostu, antistarvation daje maksymalny dynamiczny priorytet = 15 (przed SP2 = 14, od Service Pack 2 = 15). Po wykonaniu wydłużonego kwantu zarówno priorytet jak i długość kwantu maleje do stanu sprzed. 

Balance Set Manager w rzeczywistości nie przeszukuje całej listy kolejek wątków gotowych. Aby zminimalizować zużycie czasu, przeszukuje jedynie 16 gotowych wątków. Jeśli jest więcej wątków o tym priorytecie, zapamiętuje miejsce gdzie ostatnio zakończył działanie i następnym razem zaczyna od tego miejsca. Zwiększa priorytety maksymalnie tylko dziesięciu takim wątkom po czym kończy działanie zapamiętując gdzie skończył przeszukiwanie.


Algorytm planowania w systemach wieloprocesorowych

Pojęcia

 

Po nałożeniu blokady na Dispatcher Ready List FindReadyThread przeszukuje Dispatcher Ready List w celu znalezienia gotowego wątku.

Gdy wątek jest gotowy do uruchomienia, system próbuje przydzielić mu bezczynny procesor. Jeśli taki jest to wybiera się szukając najpierw idealny, ostatni lub bierząco wykonywany. Jeśli żaden z nich nie jest bezczynny, Windows wybiera pierwszy szukając od najwyższego numeru procesora do najniższego.

Jeśli wszystkie procesory są zajęte a wątek jest gotowy, Windows szuka wątku do wywłaszczenia zaczynając od idealnego procesora, następnie ostatniego. Jeśli nia ma to szuka od największego.

Jeśli wybrany procesor ma już wątek do kolejnego wykonania (wątek w stanie standby) a priorytet tego wątku jest niższy, nowy usuwa ten wątek ze stanu standby wprowadzając go w stan ready. Jeśli priorytet wykonywanego wątku jest mniejszy, wykonywany wątek jest zaznaczany jako wywłaszczony i system kolejkuje przerwanie do wyrzucenia tego procesu na rzecz nowego.

Uwaga: System nie sprawdza priorytetów wszystkich wątków na wszystkich procesorach a tylko na jednym wybranym. Jeśli nowy proces nie wywłaszczy starszego, to jest wstawiany do kolejki.

Wybór wątku do uruchomienia na wybranym CPU.
W systemie wieloprocesorowym, wybór nowego wątku do wykonania nie jest taki prosty. Wybiera się wątek który spełnia następujące warunki:

Jak widać, w SMP nie zawsze wątki z najwyższymi priorytetami wykonują się pierwsze. Dzieje się tak też wtedy gdy affinity mask danego wątku nie zawiera procesora, który właśnie jest bezczynny.


Job object

Job Object jest obiektem jądra, który pozwala zarządzać grupą procesów. Proces może być członkiem tylko jednego job object

 

API Function

Opis

CreateJobObject Tworzy job object.
OpenJobObject Otwiera istniejący job object.
AssignProcessToJobObject Dodaje proces do job object.
TerminateJobObject Kończy wszystkie procesy w job object.
SetInformationJobObject Ustawia ograniczenia na job object.
QueryInformationJobObject Pobiera informacje o job object takie jak liczba procesów, lista ID procesów, itd.

Dla job object możliwa możliwe jest ustawienie między innymi następujących parametrów:

Scheduling Class

Quantum Units

0 6
1 12
2 18
3 24
4 30
5 36
6 42
7 48
8 54
9 Infinite if real-time; 60 otherwise

Win API dla wątków

API

Opis

Suspend/ResumeThread Zawiesza/Wznawia wątek.
Get/SetPriorityClass Zwraca/Ustawia priorytet klasy procesu (podstawowy).
Get/SetThreadPriority Zwraca/Ustawia priorytet klasy wątku (względny).
Get/SetProcessAffinityMask Zwraca/Ustawia affinity mask procesu.
SetThreadAffinityMask Zwraca/Ustawia affinity mask wątku (podzbiór affinity mask procesu).
Get/SetThreadPriorityBoost Zwraca/Ustawia wielkość wzrostu priorytetu (tylko dla zmiennej klasy).
SetThreadIdealProcessor Ustawia preferowany procesor dla wątku. 
Get/SetProcessPriorityBoost Zwraca/Ustawia wielkość wzrostu priorytetu (używana, przy tworzeniu nowego wątku).
SwitchToThread Wątek oddaje swój kwant czasu .
Sleep Przechodzi w stan uśpienia na pewien x milisekun. Zerowa wartość powoduje oddanie swojego kwantu czasu.

©Mikołaj Moszczyński