Scheduler O(1)

Wstęp

Każdy procesor może być w jednej chwili przydzielony tylko jednemu procesowi. Ponieważ procesów przeważnie jest więcej niż procesorów, procesy korzystające z procesora muszą się zmieniać. Do regulowania któremu procesowi przyznać procesor służy właśnie scheduler. Jedną z ważniejszych zmian wprowadzonych w jądrze 2.6 jest wprowadzenie schedulera działającego w czasie stałym. Dzięki temu poprawiła się znacznie współpraca Linuxa z komputerami wieloprocesorowymi.

Co to jest scheduler?

Scheduler jest to część jądra odpowiadająca za przydzielanie procesora procesom zgodnie z pewnym algorytmem. Scheduler nie jest odrębną częścią, jego fragmenty znajdują się w różnych częściach jądra. Głównymi zadaniami schedulera są:
- wywłaszczanie procesów, które zbyt długo zajmują procesor
- wywłaszczenie procesu o niższym priorytecie gdy gotowy jest proces o wyższym priorytecie
- przydzielanie procesora nowemu procesowi, gdy proces aktywny zasypia lub dobrowolnie zrzeka się procesora

Scheduler w jądrze 2.4

Klasy procesów

Linux rozróżnia następujące klasy procesów (wg malejących priorytetów):
- procesy czasu rzeczywistego (SCHED_RR i SCHED_FIFO)
- zwykłe procesy (SCHED_OTHER)
- idle

Procesy znajdują się w jednym ze stanów:
- wykonywany
- gotowy do wykonania
- oczekujący.

Procesy czasu rzeczywistego (RT)

Procesy RT mają pierwszeństwo przed procesami zwykłymi gdyż mają wyższy priorytet. Ponadto gdy jakis proces RT przechodzi do stanu "gotowy do wykonania" a wykonywany jest proces zwykły zostaje on natychmiast wywłaszczony.
Procesy RT są podzielone na 99 podklas (kolejek koncepcyjnych) ponumerowanych od 1 do 99 - na ich podstawie przydzielane sa priorytety statyczne. Im wyższy numer kolejki tym wyższy priorytet procesu.
Do wykonania jest wybierany zawsze pierwszy proces z danej kolejki. Proces który zasypia zostaje przeniesiony na koniec swojej kolejki. Jednak proces który został wywłaszczony przez proces o wyższym priorytecie nie zostaje przeniesiony! Proces może dobrowolnie zrzec sie procesora na rzecz kolejnego procesu ze swojej kolejki.

SCHED_FIFO

Proces taki jest szeregowany zgodnie z zasadą kolejki prostej tzn. nie może być wywłaszczony przez proces z tej samej kolejki koncepcyjnej. Gdy proces taki zostanie wywłaszczony przez proces o wyższym priorytecie, procesor zostanie mu zwrócony gdy nie będzie procesów o wyższym priorytecie gotowych do działania. Proces wędruje na koniec kolejki gdy zrzeknię sie procesora lub zaśnie.

SCHED_RR

Proces są szeregowane w obrębie kolejki koncepcyjnej zgodnie z algorytmem Round-Robin. Procesom z tej grupy przyznawany jest kwant czasu dostępu do procesora. Po zużyciu kwantu czasu proces zostaje przeniesiony na koniec swojej kolejki i orzymuje kwant czasu równy swojemu priorytetowi statycznemu.
Proces wędruje na koniec kolejki gdy skończy mu się kwant czasu, zrzeknie się procesora lub zaśnie. Priorytet dynamiczny jest obliczany przez funkcje goodness() jako 1000 + priorytet statyczny (zakres: 1001 - 1099).

Procesy zwykłe (SCHED_OTHER)

Jeśli procesy gotowe nie zużyły swoich kwantów czasu, do wykonania zostaje wybrany proces o najwyższym priorytecie dynamicznym. Jest on wyliczany na podstawie:

-liczba niewykorzystanych jednostek kwantu czasu (im większa tym większy priorytet)
-proces aktualnie wykonywany ma podwyższony priorytet, żeby uniknąć przełączania kontekstów.
-proces który ostatnio wykonywał się na innym procesorze ma niższy priorytet aby zmniejszyć prawdopodobieństwo zmiany procesora.
-priorytet statyczny którym jest parametr nice od -19 do 20

Jeśli wszystkie procesy gotowe zużyły swoje kwanty czasu następuje obliczenie priorytetów dynamicznych dla każdego procesu tej grupy na podstawie priorytetu statycznego. Każdy proces otrzymuje kwant czasu zgodny ze wzorem:
kwant = priorytet statyczny + (niewykorzystane jednostki czasu)/2.
Procesy śpiące, które nie wykorzystały swojego kwantu czasu otrzymują zwiększony kwant czasu oraz wyższy priorytet.

Reasumując procesy tej grupy o wyższym priorytecie otrzymują większy kwant czasu oraz szybciej uzyskują procesor.

Scheduler w jądrze 2.6

Procesy

Główne cechy algorytmu pozostały te same: podział na priorytet dynamiczny i statyczny, epoki, kwanty czasu pozostały. Zostały jednak wprowadzone pewne ulepszenia, które znacznie usprawniły działanie schedulera.

Procesy czasu rzeczywistego mają priorytety od 0 do 99 jednak teraz im mniejsza liczba tym wyższy priorytet.

Procesy zwykłe mają priorytety od 100 do 139. Priorytet dynamiczny obliczany jest na podstawie nice (jak dawniej od -19 do 20), priorytet = 120 - nice Ponadto nowościa jest, że priorytet dynamiczny jest uzależniony od interaktywności procesu. Ściślej zależy to od tego ile czasu proces spędza na obliczeniach a ile na oczekiwaniu na użytkownika. Interaktywność może się zmieniać w czasie wykonywania procesu, waha się w granicach od -5 do 5.

Struktury

W nowym algorytmie wykorzystano następujące struktury:
- Mapa bitowa od 0 do 139 mówiąca o tym czy istnieją procesy o danym priorytecie.
- Tablica list procesów jest to tablica list od 0 do 139 w polu pod indeksem i znajduje się lista procesów o priorytecie i

Ponadto procesy zwykłe gotowe do działania przetrzymywane sa w dwóch tablicach:
- expired te które już wykorzystały swój kwant czasu
- active te które jeszcze nie wykorzystały swojego kwantu czasu
Tablice te są oddzielne dla każdego procesora, wskaźniki do nich trzymane sa w strukturze runqueue. Dzięki temu jest większa zależność procesu z procesorem. Gdy jednak któryś z procesorów zostaje przeładowany pracą "oddaje" kilka procesów innemu procesorowi.

Algorytm

idx = sched_find_first_bit(array->bitmap);        /* znalezienie najwyższego priorytetu                    */
queue = array->queue + idx;                       /* znalezienie odpowiedniej kolejki                      */
next = list_entry(queue->next, task_t, run_list); /* znalezienie procesu, który teraz będzie się wykonywał */
Algorytm wyboru procesu w jądrze 2.6 wygląda nastepująco:

Z mapy bitowej obliczany jest najwyższy priorytet posiadany przez którys z procesów.
Z tablicy list wybierany jest pierwszy proces z listy o wyszukanym priorytecie.
Jak łatwo obliczyć algorytm wykonuje się w czasie stałym O(140)+O(1) = O(1)

Gdy rozpoczynamy nową epokę zamieniane są jedynie wskaźniki na tablice active i expired. Kwanty czasu przyznane procesom w nowej epoce są obliczane natychmiast po tym jak procesy wyczerpały swoje kwanty czasowe w poprzedniej epoce. Robi to funkcja scheduler_tick()

Podsumowanie

Algorytm zaimplementowany w jądrze 2.4 był dobry choć nowy ma nad nim pewną przewagę.
Wybory procesów którym przyznawane są procesory wykonują się w czasie stałym.
Nowy algorytm zapewnie lepszą obsługę procesów interaktywnych.
Lepsza i wydajniejsza obsługa komputerów wieloprocesorowych poprzez przypisanie procesów konkretnym procesorom.