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.
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żą:
KTHREAD(blok jądrowy wątku)
TEB (blok środowiska wątku)
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).
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.
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
THREAD_STATE_INITIALIZED - i
nicjalizacja
wątku
THREAD_STATE_READY
- gotowość oznacza czekanie na wykonywanie.
Dyspozytor szuka tylko wątków znajdujących się w tym stanie. Wątek w
stanie gotowości z najwyższym priorytetem przechodzi w stan pogotowia.
THREAD_STATE_RUNNING
- wykonywany - procesor wykonuje jego instrukcje dopóki jądro go nie
wywłaszczy chcąc uruchomić wątek o wyższym priorytecie, jego kwant upłynął,
zakończył swoje działanie lub dobrowolnie zrezygnował z wykonywania się
THREAD_STATE_STANDBY
- stan pogotowia. Wątek który znajduje się w tym stanie będzie
wykonywany w pierwszej kolejności. W systemie wieloprocesorowym każdy procesor
utrzymuje jeden wątek w stanie pogotowia.
THREAD_STATE_TERMINATED
- kiedy proces kończy działanie przechodzi w ten stan.
THREAD_STATE_WAIT
- wątek jest w stanie oczekiwania jeśli czeka na sygnał od obiektu
dyspozytora. Wątek może się znaleźć w tym stanie w momencie gdy: czeka na
obiekt synchronizujący jego działanie, operację wejścia-wyjścia. Po
otrzymaniu przechodzi w stan gotowości
THREAD_STATE_TRANSITION
- stan przejściowy - gdy jądro oczekuje na zasoby niezbędne do działania
systemu np. gdy następuje brak pamięci.
THREAD_STATE_UNKNOWN
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:
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:
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.
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
procesy pierwszoplanowe - czyli procesy interakcyjne
procesy drugoplanowe (wsadowe).
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.
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:
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.
Do szeregowania procesów, jądro wykorzystuje strukturę zwaną bazą 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. |
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.
Scenariusz 2: Wątek o niższym priorytecie jest wywłaszczany przez wątek o wyższym priorytecie
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.
Scenariusz 3: Gdy działający wątek zużywa kwant, dyspozytor musi sprawdzić czy należy zmniejszyć priorytet tego wątku oraz czy inny wątek może skorzystać z procesora
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 i ReadyThread są kluczowymi algorytmami do wyznaczania kolejności przydziały procesora.
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).
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
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.
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.
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.
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 |
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 |