Podstawową jednostką szeregowania w systemach z rodziny NT jest wątek. Wątek jest punktem kontrolnym wewnątrz procesu. Na proces składa się wirtualna przestrzeń adresowa zawierająca m. in. wykonywalny kod, zbiór zasobów oraz jeden lub więcej wątków wykonujących się w przestrzeni adresowej. Scheduler nie czy wątki należą do tego samego, czy różnych procesów i bierze pod uwagę jedynie ich priotytety.
W systemie Windows występują 32 priorytety, przy czym wyższy numer oznacza wyższy priorytet. Wątki mogą mieć przypisane priorytety od 1 do 31. Priorytet zerowy jest używany dla systemowego wątku bezczynności (idle), który jest wykonywany, gdy żaden z pozostałych wątków nie jest gotowy do wykonywania. Priorytety o numerach 16 - 31, nazywane priorytetami czasu rzeczywistego (realtime), są zarezerwowane dla operacji, w których czas wykonania jest krytyczny. Do nadania wątkowi priorytetu z tyego przedziału wymaganę są uprawnienia administratora. Priorytety od 1 do 15, nazywane dynamicznymi (dynamics) są przeznaczone dla zwykłych wątków.
Nadawanie wątkowi priorytetu za pomoćą Win32 API odbywa się dwustopniowo: Za pomocą klasy i względnego priorytetu. Klasa określa środek pewnego przedziału priorytetów. Klasy występujące w Win32 API, wraz z odpowiadającymi im priorytetami to:
Oprócz tego dostępne są dwa specjalne modyfikatory: time-critical i idle, które powodują przeniesienie danego wątku odpowiednio na szczyt i koniec odpowiadającemu wątkowi zakresu. Tak więc nadanie priorytetu time-criticalwątkowi z przedziału czasu rzeczywistego ustawi jego priorytet na 31, a idle na 16. Analogiczne dla zakresu dynamicznego będą to priorytety 15 i 1. Począwszy od Windows 2000 istnieje możliwość grupowania wątków w tzw. zadania (job), dzięki czemu można m.in. zmieniać przyznawać priorytety całym zestawom wątków.
[Powrót]Zarządzanie wątkai powinno odbywać się w taki sposób, aby żaden z wątków nie uniemożliwiał wykonania pracy innemu. Aby to osiągnąć w systemie Windows zastosowano algorytm oparty na kwantach czasu i umożliwoający wywłaszczanie wątków. Aby system pracował "płynnie" nawet przy wielu działających wątkach keanty czasu procesora są stosunkowo krótkie. Ich długość zależy od wersji systemu, jego konfiguracji oraz innych czynników opisanych w dalszej części. Generalnie kwant ma długość z przeziału kilkudziesięciu - kilkuset milisekund.
Uruchomienie schedulera zachodzi w każdej z poniższych sytuacji:
W przypadku wygaśnięcia czasu przydzielonego wątkowi scheduler uruchamia algorytm FindReadyThread aby zdecydować czy inny wątek powinien przejąc procesor. Gdy jakiś wątek przerywa działanie przed upłynięciem jego kwantu czasu również jest uruchamiany algorytm FindReadyThread. Kiedy tworzony jest nowy wątek, bądź zablokowany wątek przechodzi do stanu ready to execute scheduler uruchamia algorytm ReadyThread, który ustala, czy gotowy wątek powinien od razu otrzyamać procesor, czy znaleźć się na liście wątków oczekujących.
[Powrót]Scheduler trzyma dowiązania do wszystkich wątków gotowych-do-uruchomienia w strukturze Dispatcher Ready List. Jest to 31-elementowa lista o pozycjach odpowiadających prirytetom wątków. Elementami listy są kolejki oczekujących wątków (być może puste).
FindReadyThread znajduje wątek o najwyższym priorytecie gotowy do uruchomienia. W tym celu przegląda listę Dispatcher Ready List począwszy od najwyższych priorytetów szukając pierwszej niepustej kolejki, a następnie wybiera pierwszy wątek z tej kolejki.
[Powrót]Przydział priorytetów wątkom nie jest startyczny. W wielu sytuacjach Windows zwiększa priorytety wątków z zakresu dynamicznego (czyli dolnej piętnastki). Najczęstszą [przyczyną jest wystąpienie zdarzenia na które czekał zawieszony wątek. Na zdarzenie wciśnięcia klawisza zwiększa o 6 priorytet wątku oczekującego na wejście z klawiatury.
Awansowanie dotyczy wyłącznie wątków z zakresu dynamicznego. Priorytety wątków czasu rzeczywistego mogą być zmienione wyłącznie na żądanie programu. Co więcej. Awansowanie nigdy nie powiduje przekroczenia granicy pomiędzy zakresem dynamicznym a rzeczywistym, tzn żaden wątek nie może awansować powyżej 15 poziomu. Awans wątku ma charakter tymczasowy. Po każdym kwancie czasu procesora wykorzystanym przez awansowany wątek jego priorytet spada o 1, aż do osiągnięcia pierwotnego stanu.
Innym sposobem faworyzowania wątku jest wydłużenie kwantu czasu przyznawanego wątkowi. W zależności od ustawień możliwe jest przyznanie wątkom związanym z aplikacją pierwszoplanową podwojonych bądź potrojonych długości kwantu.
[Powrót]Opisany powyżej model może w łatwy sposób doprowadzić do zagłodzenia wątków o niższych priorytetach. Bedzie tak w sytuacji gdy dwa lub więcej wątków o wysokim priorytecie wykonuje się naprzemiennie nie dopuszczając wątku o niskim priorytecie. Zapobieganie zagłodzeniom odbywa się w następujący sposób: Co sekune uruchamiany jest NT Balance Set Manager, Jednym z wykonywanych przez niego zadań jest algorytm ScanReadyQueues odpowiadający za przeciwdziałanie zagłodzenom.
ScanReadyQueues przegląda listę Dispatcher Ready List począwszy od wątków o priorytecie 31 szukając wątku który nie miał dostępu do procesora od conajmniej 3 sekund. Gdy taki znajdzie podwaja przysługujący wątkowi kwant czasu, ustawia jego priorytet na 15 (najwyższy dla dynamicznych) i uruchamia ReadyThread ze znalezionym wątkiem jako argumentem. Po wykorzystaniu przez wątek czasu procesora jego priorytet i długość kwantu są przywracane do standardowych wartości.
[Powrót]Systemy Windows z rodziny NT wsperają tzw. symmetric multiprocessing (SMP). W systemach SMP wszystkie procesory są identyczne i mają równy dostęp do pamięci i zasobów komputera. Schemat systemu symetrycznego jest przedstawiony na rysunku w podpunkcie A) w przeciwieństwie do systemu asymetrycznego B).
Jądro systemów Windows z rodziny NT może obsłużyć do 32 procesorów, jednak liczba ta jest sztucznie ograniczana w zależności od licencji na system operacyjny. Do szeregowania procesów są wykorzystywane te same struktuy danych co w systemach jednoporocesorowych. W celu uniknięcia błędu do skorzystania z nich jest wymagane założenie blokady, tak aby tylko jeden procesor w danym momencie operował na Dispatcher Ready List.
Zdarzenia powodujące uruchomienie schedulera są takie same jak w przypadku systemów jednoprocesorowych. Takie same są też nazwy procedur, różnią się natomiast implementacje.
[Powrót]Scheduler daje też możliwość twardego przywiązania wątków do wybranych procesorów lub grup procesorów. Twarde dowiązanie (hard affinity) jest listą procesorów, na których dany wątek może być wykonywany. Scheduler nigdy nie umieści wątku na procesorze spoza listy. Użycie twardego dowiązania pozwala na rozdzielenie działających aplikacji pomiędzy procesory, dzięki czemu można rozdysponować współdziałające aplikacje pomiędzy procesory, aby nie rywalizowały e sobą o dostęp do procesora.
Twarde dowiązania są rozwiązaniem dosyć radykalnym i istnieje możliwość zaistnienia sytuacji, w której na jednym procesorze nie wykonuje się żaden wątek, podczas gdy drugi jest ciągle zajęty. Rozwiązaniem pośrednim jest wskazanie preferowanego procesosa. Scheduler będzie się starał przydzielić wątek do wybranego procesora. Gdy jednak będzie on zajęty przez wątek o wyższym priorytecie to scheduler przeszuka pozostałe procesory.
Podsumowując: w systemie wieloprocesorowym scheduler, aby spełnić powyższe wymagania musi z każdym wątkiem przechowywać informacje o:
Funkcja FindReadyThread zawsze wykonuje się na procesorze dla którego szuka kolejnego wątku do uruchomienia. Algorytm przeszukuje niepustą kolejkę o najwyższym priorytecie w poszukiwaniu wątku spełniającego warunki:
Przykład działania FindReadyThread jest pokazany na rysunku. Rozważmy listę wątków przedstawioną na rysunku. Scheduler szuka wątku do uruchomienia na procesorze 1. Najwyższą niepustą kolejką jest 10.
Gdy wątek staje się gotowym do uruchomienia scheduler musi zdecydować, czy umieścić go na Dispatcher Ready List, czy wyznaczyć do natychmiastowego wykonania. W przypadku systemu wieloprocesorowego zadanie jest trudniejsze, gdyż należy rozważyć wiele jednostek obliczeniowych. Algorytm ReadyThread, odpowiedzialny za to zadanie, jako pierwszą wytyczną przyjmuje numer procesona na którym ostatnio wykonywał się wątek. Po założeniu blokady na Dispatcher Ready List, scheduler sprawdza czy któryś z procesorów na któruch dany wątek może się wykonywać jestw danej chwili bezczynny. Jeżeli tak przekazuje wolnemu procesorowi wykonanie wątku. Ponieważ sam ReadyThread wykonuje się w specjalnym, bezwątkowym kontekście procesor używany do jego wykonania może również być uznzny za bezczynny.
Gdy nie ma wolnych procesorów albo wątek nie może być wykonywany na żadnym z bezczynnych ReadyThread rozpoczyna poszukiwania wśród pozostałych procesorów. Najpierw sprawdza procesor preferowany przez przetwarzany wątek. W następnej kilejności brany jest pod uwagę procersor, na którym wątek był ostatnio wykonywany. Jeżeli na rozważanym procesorze wykonuje się wątek o priorytecie mniejszym bądź równym priorytetowi naszego wątku wykonywany wątek zostaje wywłaszczony a procesor zaczyna wykonywać nowy wątek. W przeciwnym wypadku przetwarzany wątek zostaje umieszczony w odpowiedniej kolejce na Dispatcher Ready List. Po zakończeniu działania ReadyThread zwalnia blokadę z Dispatcher Ready List.
[Powrót]Zastosowany w Windows mechanizm szeregowania może w niektórych sytuacjach prowadzić do raczej nieporządanych scenariuszy. Gdy wszystkie procesory są zajęta, a wątek gotowy do wykonania ma priorytet niższy niż wątki wykonujące się na procesorach: preferowanym i ostatnio używanym, ReadyThread może wywołać niezwykłe konsekwencje. Dzisje się tak, ponieważ algorytm nie bierze pod uwagę innych procesorów w systemie. Rozważmy sytuację na rysunku:
Wątek 0, o priorytecie 9 właśnie przeszedł do stanu "gotowy do uruchomienia". Mimo, że jego priorytet jest wyższy niż priorytety watków działających na 3 z 4 dostępnych procesorów zostanie on umieszczony na Dispatcher Ready List. Stanie się tak, gdyż procesor, na którym wykonywał się ostatnio wątek jest zajęty przez wątek o wyższym priorytecie. W tej sytuacji, dopóki nie zostanie wywołane FindReadyThread drugi pod względem priorytetu wątek w systemie będzie zawieszony w oczekiwaniu na procesor.
ReadyThread może prowadzić do niepotrzebnej migracji wątków pomiędzy procesorami. Pozpatrzmy wariację poprzedniej sytuacji przedstawioną na schemacie:
Tutaj wątek 1 wykonujący się na CPU 0 ma priorytet 8 zamiast 10. Tak więc ReadyThreat wywłaszczy wątek pierwszy aby zrobić misjsce dla wątku 0 o priorytecie 9. Ponieważ wątek 1 jest wciąż gotowy do uruchomienia, zostanie dla niego wywołane ReadyThread. ReadyThread sprawdzi, że ma on niższy priorytet niż proces wykonujący się na jego ostatnim procesorze (co nie jest zaskakujące, zważywszy, że właśnie został przez niego wyrugowany) i umieści go na Dispatcher Ready List. Jeżeli następnym zdarzeniem inicjującym FindReadyThread będzie wygaśnięcie kwantu czasu wątku 4. FindReadyThread wyciągnie wątek 1 z kolejki, umieści do uruchomienia na procesorze 3 a wątek 4 znajdzie się na liście.
Ostatecznie wątek 1 migrował z procesora 0 na 3. Wątek 4 może się znaleźć na procesorze 1. lub 2., gdy któryś z nich wywoła FindReadyThread.
Niepotrzebnego mieszania wątków można by uniknąć, gdyby FindReadyThread zrezygnował z rozpatrywania procesora na którym wątek był ostatnio uruchamiany, a brał pod uwagę jedynie wykonujący się wątek o najniższym priorytecie. Porównajmy dwa warianty przemieszczania wątków przedstawione na schemacie:
Wątki o priorytetach 9, 8 i 7 wykonują się na 3 procesorach. W najgorszym wypadku stosowania miękkiego dowiązania, wątek 10 stając się gotowym do wykonania może spowodować przemieszczenia przedstawione na diagramie A. Natomiast sprawdzanie wyłącznie wątku o najniższym priorytecie przedstawione na diagramie B spowoduje znacznie mniej ruchu pomiędzy procesorami.
Szeregowanie w oparciu o wywłaszczanie wątku o najniższym priorytecie jest prostsze niż to opartena miękkim dowiązaniu. Pozwala także uniknąc zędnego przetasowywania wątków. Jednakże Microsoft pozostaje przy bierzącej strategii twierdząć, że SQL Server osiąga wyższą wydajność przy takiej implementacji.
[Powrót]Zobacz prezentację swf pokzaująca działanie schedulera w Windows.