Piotr Karpiuk

Szeregowanie procesów

Szkic

Algorytm szeregujący ma za zadanie wybrać spośród procesów przebywających w kolejce procesów gotowych jeden proces, któremu przekazany zostanie procesor. Wybór jest uzależniony od wielu czynników, takich jak czas przebywania w kolejce, ilość już wykorzystanych jednostek czasu procesora, czy też klasa szeregowania do której przypisany jest proces. Czynniki te znajdują swoje odzwierciedlenie w pojęciu priorytetu procesu, czyli wartości liczbowej określającej stopień ubiegania się procesu o czas procesora. Ponieważ niektóre spośród wymienionych czynników zmieniają się w trakcie życia procesu, dynamicznej zmianie ulegać może również priorytet.

Najbardziej ogólny podział procesów pozwala wyróżnić dwa ich rodzaje:

Procesy "zwykłe" z podziałem czasu

Jeżeli tylko takie procesy będą okupowały kolejkę procesów gotowych, wówczas każdy z nich w nie za długim czasie otrzyma procesor. Mechanizm dynamicznej zmiany priorytetów takich procesów gwarantuje bowiem obniżenie priorytetu aktualnie wykonywanego procesu na tyle, że inny proces-kandydat stanie się bardziej uprawniony do przejęcia procesora. Operację odebrania procesora aktualnie wykonującemu się procesowi bez jego wiedzy nazywamy wywłaszczaniem. Oczywiście proces zawsze może oddać procesor dobrowolnie zasypiając w oczekiwaniu na zdarzenie lub kończąc się zanim priorytet wystarczająco spadnie.

Przy takim podejściu nadejdzie w końcu moment, gdy wartość priorytetu wszystkich procesów w kolejce procesów gotowych spadnie do zera. Wtenczas następuje ponowne przydzielenie procesom kwantów czasu w wyniku przeliczania priorytetów wszystkich procesów (również tych uśpionych w oczekiwaniu na zdarzenie). Okres czasu pomiędzy sąsiednimi dwiema tego typu operacjami nazywamy epoką (ang. epoch). Przeliczanie odbywa się według wzoru:

nowy_priorytet = priorytet_bazowy + priorytet / 2

Priorytet_bazowy jest dziedziczony od rodzica w chwili utworzenia procesu i może być zmniejszony wywołaniem funkcji systemowej nice() (lub dowolnie zmieniony - tylko przez administratora - za pomocą funkcji systemowej nice lub set_priority()) - planista (ang. scheduler) nie modyfikuje tej wartości. Zauważmy że wartość priorytetu procesu w chwili przeliczania może być większa od zera gdy proces nie znajduje się w kolejce procesów gotowych lecz śpi w oczekiwaniu na zdarzenie. Dzięki temu proces taki otrzyma wyższą wartość priorytetu niż wszystkie procesy w kolejce procesów gotowych, i co za tym idzie, z dużym prawdopodobieństwem przejmie procesor zaraz po przebudzeniu. W ten oto sposób Linux faworyzuje procesy ukierunkowane na wejście/wyjście (ang. I/O bound) czego spodziewanym efektem jest skrócenie czasu reakcji procesu na zdarzenie.
Nawiasem mówiąc bazując na dotychczasowych wyjaśnieniach można udowodnić że wartość priorytetu nigdy nie osiągnie wartości większej niż priorytet_bazowy * 2 - co ty na to Czytelniku?

Wszystkie procesy zwykłe (i tylko one) należą do klasy szeregowania SCHED_OTHER.

Procesy czasu rzeczywistego

W istocie jest to określenie nieco na wyrost, albowiem Linux nie jest systemem czasu rzeczywistego i nie jest w stanie zagwarantować czasu reakcji procesów na zdarzenia. Wynika to z faktu, że jądro Linuxa jest niewywłaszczalne - nie sposób zagwarantować czasów wykonania poszczególnych wywołań systemowych a ich przerwanie nie jest możliwe. (Nawiasem mówiąc problem ten częściowo rozwiązano w systemie SVR4, którego jądro posiada ustalone punkty wywłaszczania w których wywołania systemowe mogą być zawieszane [Goodheart]). Niektórzy proponują podział procesów czasu rzeczywistego na sztywne (ang. hard) i miękkie (ang. soft), kwalifikując procesy czasu rzeczywistego Linuxa do tej drugiej kategorii.

Procesy tego typu w Linuxie tworzą uprzywilejowaną kastę. Każdemu z nich przypisany jest priorytet statyczny będący liczbą całkowitą z przedziału 1..99, który nie jest nigdy modyfikowany przez planistę. Żaden proces czasu rzeczywistego nie zostanie bez swojej zgody wywłaszczony na rzecz procesu zwykłego ani nawet na rzecz innego procesu rzeczywistego o niższym priorytecie statycznym.

Procesy czasu rzeczywistego mogą przynależeć do jednej z dwóch klas szeregowania: SCHED_RR lub SCHED_FIFO. Przynależność procesu do jednej z tych klas odgrywa znaczenie w sytuacji gdy w kolejce procesów gotowych znajdzie się kilka procesów czasu rzeczywistego o tej samej wartości priorytetu statycznego. Możemy sobie wyobrazić, że z każdym poziomem priorytetu statycznego jest związana osobna kolejka procesów (tzw. kolejka koncepcyjna). Proces czasu rzeczywistego w chwili otrzymania stanu TASK_RUNNING ustawia się na końcu swojej kolejki. Procesor znajduje się we władaniu procesu znajdującego się na początku kolejki koncepcyjnej o najwyższym priorytecie.

W przypadku procesu klasy SCHED_FIFO planista nie może go wywłaszczyć - proces może tylko zrzec się procesora zasypiając w oczekiwaniu na zdarzenie, kończąc się lub świadomie się zrzekając procesora na rzecz równie uprzywilejowanego kolegi poprzez wywołanie funkcji systemowej sched_yield() (w tym ostatnim przypadku proces nie zmienia swojego stanu a jedynie przechodzi na koniec swojej kolejki koncepcyjnej).

Z kolei proces należący do klasy SCHED_RR oprócz priorytetu statycznego posiada również priorytet dynamiczny, podobnie jak zwykłe procesy. W miarę upływu czasu maleje wartość priorytetu dynamicznego i gdy procesowi skończy się kwant czasu lub gdy pojawi się nowy proces o tym samym priorytecie statycznym - aktualnie wykonywany proces zostaje wywłaszczony i przeniesiony na koniec kolejki koncepcyjnej.

Z oczywistych względów tylko administrator jest uprawniony do tworzenia procesów czasu rzeczywistego, jak również zmiany klasy szeregowania procesu (funkcja systemowa sched_setscheduler()).

Pod maską

Zapewne dręczy Cię pytanie jak wyglądają kolejki procesów oczekujących i kolejka procesów gotowych, oraz jak się ma kolejka procesów gotowych do kolejek koncepcyjnych o których wspomniano wyżej.

Kolejki procesów oczekujących

Istnieje wiele kolejek procesów oczekujących, z których każda przyporządkowana jest zdarzeniu innego typu. Kolejki mają postać jednokierunkowych list cyklicznych:

struct wait_queue {
    struct task_struct * task;
    struct wait_queue * next;
}

Z uwagi na strategiczne znaczenie kolejek i częstość ich używania, wymagają one szczególnej ochrony przed utratą spójności. Istnieją dwie procedury do modyfikacji kolejek, obie na początku blokują przerwania i opuszczają semafor, na końcu podnoszą semafor i odblokowują przerwania.

void add_wait_queue(struct wait_queue **queue, struct wait_queue *entry)

Wstawia entry na początek listy queue.

void remove_wait_queue(struct wait_queue **queue, struct wait_queue *entry)

Usuwa entry z kolejki.

Z chwilą zajścia zdarzenia budzone są wszystkie procesy na danej kolejce.

Kolejka procesów gotowych

Elementami cyklicznej dwukierunkowej kolejki procesów gotowych są struktury task_struct procesów ze statusem TASK_RUNNING. Kolejki koncepcyjne (na których - przypomnijmy - wiszą procesy czasu rzeczywistego) są logicznie "zanurzone" w kolejce procesów gotowych, co obrazowo przedstawia rysunek.

task_struct

struct task_struct *next_run, *prev_run

dowiązania do następnego i poprzedniego procesu gotowego

long rt_priority

Numer kolejki koncepcyjnej procesu (0..99). W kolejce numer N czekają procesy czasu rzeczywistego o statycznym priorytecie równym N. Tylko procesy czasu rzeczywistego używają tego pola.

Rys. 1. Kolejki koncepcyjne

Podobnie jak w przypadku kolejek procesów oczekujących, również w przypadku kolejki procesów gotowych istnieją funkcje do manipulowania elementami kolejki - modyfikują one jedynie wskaźniki next_run i prev_run oraz zmienną globalną nr_running.

void add_to_runqueue(struct task_struct * p)

Dodaje proces p na początek kolejki (tuż za procesem init).

void del_from_runqueue(struct task_struct * p)

Usuwa proces p z kolejki.

void move_first_runqueue(struct task_struct * p)

Przesuwa proces p na początek kolejki procesów gotowych, tj. tuż za proces idle.

void move_last_runqueue(struct task_struct * p)

Przesuwa proces p na koniec kolejki procesów gotowych, tj. tuż przed proces idle.

Algorytm schedule

task_struct - cd.

policy

Klasa szeregowania procesu (SCHED_OTHER dla procesów zwykłych, SCHED_FIFO i SCHED_RR dla procesów czasu rzeczywistego)

state

Stan procesu (TASK_RUNNING dla procesów gotowych)

counter

Dynamiczny priorytet procesu (liczba pozostałych procesowi jednostek czasu w kwancie), nie wykorzystywany przez procesy czasu rzeczywistego SCHED_FIFO. Przy rozpoczęciu nowej epoki pole to zawiera długość kwantu procesu. Przerwanie zegarowe zmniejsza wartość tego pola o 1.

priority

Priorytet bazowy procesu. Makro INIT_TASK ustawia wartość bazowego okresu kwantu procesu 0 (swapper) na wartość DEF_PRIORITY:

#define DEF_PRIORITY (20 * HZ / 100)

gdzie HZ oznacza częstotliwość przerwań zegarowych i w komputerach PC jest ustawiona na 100. Ostatecznie więc w komputerach PC DEF_PRIORITY wynosi 20 taktów, czyli ok. 210 milisekund.

last_processor

Numer procesora na którym ostatnio wykonywał się dany proces

need_resched - flaga ustawiana przez procedurę obsługi przerwania w sytuacji gdy konieczne jest późniejsze wywołanie algorytmu szeregującego zadania.

Okoliczności wykonywania algorytmu szeregującego mogą być następujące:

• zaśnięcie procesu w oczekiwaniu na zdarzenie,
• zakończenie procesu,
• przejście z trybu jądra do trybu użytkownika (na koniec wywołania funkcji systemowej lub przerwania)

Działanie funkcji schedule() w przybliżeniu jest następujące:

• Wykonuje zaległe zadania zlecone przez ograniczone czasowo procedury przerwań (zwłaszcza przerwanie zegarowe).
• Po kolei dla każdego procesu w kolejce procesów gotowych wywoływana jest funkcja goodness() i pierwszy proces o najwyższej, nieujemnej wartości zwróconej przez funkcję przejmuje procesor.
• Jeżeli nie ma gotowego procesu czasu rzeczywistego i wszystkie procesy zwykłe wyczerpały swój kwant czasu, następuje przeliczenie priorytetów dynamicznych i tym samym przydzielenie nowych kwantów czasu.

Wartości zwracane przez goodness():

• -1000 dla procesów wykonujących się na innym procesorze lub nie mogących się wykonywać na danym procesorze,
• 1000 + rt_priority dla procesów czasu rzeczywistego,
• 0 dla procesu zwykłego który wyczerpał swój kwant czasu,
• counter + 1 dla procesu aktualnie wykonywanego (+1 aby nie wykonywać zbędnego przełączania kontekstu w przypadku gdy priorytet aktualnie wykonywanego procesu tylko nieznacznie różni się od najlepszego kandydata do przejęcia procesora),
• counter + PROC_CHANGE_PENALTY dla procesu który poprzednio wykonywał się na tym samym procesorze (zaleca się aby dany proces był wykonywany ciągle przez ten sam procesor, aby uniknąć kosztów odświeżania pamięci podręcznej procesora),
• counter w pozostałych przypadkach.

Funkcje systemowe

Istnieje kilka funkcji systemowych pozwalających użytkownikom kontrolować parametry szeregowania procesów. Większość z tych funkcji - oczywiście - może być wywoływanych tylko przez administratora systemu. Oto najważniejsze z nich.

nice(newprio)

Zmienia priorytet bazowy procesu (pole task_struct.priority) według wzoru:

priority -= newprio/20 * DEF_PRIO + 0.5

Następnie otrzymana wartość jest odpowiednio przycinana tak aby spełniała warunek:

1 <= priority <= 2 * DEF_PRIO

getpriority, setpriority

Odczyt i zmiana priorytetu statycznego grupy procesów.

sched_yield

Dobrowolne zrzeczenie się procesora i przejście na koniec kolejki procesów gotowych.

sched_getscheduler

Odczyt informacji o klasie szeregowania wskazanego procesu.

sched_setscheduler

Umożliwia zmianę klasy szeregowania wskazanego procesu (tylko root).

Wydajność

Algorytm planisty jest stosunkowo prosty, efektywny i łatwy do zaimplementowania. Z uwagi na fakt że jest wykonywany często, słusznie położono nacisk na wydajność aby nie powiększać i tak już sporego narzutu czasowego związanego z przełączaniem kontekstu. Mało wyszukany algorytm posiada również niestety swoje wady, m.in. koszt przeliczania kwantów na początku epoki staje się znaczący gdy liczba procesów staje się duża, preferowanie procesów wykonujących częste operacje I/O niepotrzebnie przyspiesza procesy wsadowe często korzystające z urządzeń zewnętrznych (np. silnik bazy danych), z kolei programy interaktywne które intensywnie korzystają z procesora moga reagować wolno, ponieważ zwiększenie priorytetu dynamicznego dzięki blokującym operacjom I/O może nie zrekompensować zmniejszenia spowodowanego używaniem procesora.

Informacje uzupełniające

Zwykły proces tworząc potomka zrzeka się na jego korzyść połowy swojego kwantu czasu. W ten sposób zapobiega się tendencjom do namnażania potomków celem zawładnięcia czasem procesora kosztem procesów wykonujących inne operacje.

Potrzeba wywłaszczania jądra nie jest jedynym zmartwieniem w przypadku implementacji procesów realizujących politykę sztywnego czasu rzeczywistego (ang. hard real time), np. procesy czasu rzeczywistego często muszą korzystać z zasobów wymaganych także przez zwykłe procesy w wyniku czego może się zdarzyć że proces czasu rzeczywistego będzie musiał poczekać na taki zasób (odwrócenie priorytetów); ponadto proces czasu rzeczywistego może wymagać usługi jądra spełnianej w imieniu innego procesu o niższym priorytecie (ukryte szeregowanie).

Szeregowanie w SVR2 [Bach] Warto wiedzieć, że mechanizm szeregowania procesów w systemie Linux nie jest bynajmniej kanonem wśród systemów operacyjnych, a nawet w świecie Unixa. Aby uzmysłowić sobie różnorodność podejść do tego problemu, proponuję króciutko przyjrzeć się rozwiązaniu zaczerpniętemu z systemu SVR2. Priorytety procesów dzielą się na dwie klasy: priorytety poziomu użytkownika (dla procesów wywłaszczonych podczas powrotu z trybu jądra do trybu użytkownika) i poziomu jądra (dla procesów wykonujących algorytm sleep). Druga klasa podlega dalszemu podziałowi - procesy o niższym priorytecie są budzone po otrzymaniu sygnału. Liczbowo niska wartość priorytetu oznacza wysoki priorytet szeregowania. Każdej wartości priorytetu przyporządkowana jest kolejka procesów. Zasypiający proces otrzymuje priorytet uzależniony od powodu zaśnięcia (patrz rysunek). W tablicy procesów przechowywany jest czas procesora zużyty ostatnio przez proces. Wartość ta (nazwijmy ją CPU) jest zwiększana podczas przerwania zegarowego. Raz na sekundę przeliczane są priorytety wszystkich procesów przebywających w kolejce procesów gotowych: CPU := CPU / 2 priorytet := CPU / 2 + priorytet_bazowy Wartość priorytetu_bazowego jest równa wartości poziomu użytkownika 0. Skutkiem takiego przeliczenia jest przemieszczanie się procesów o priorytetach poziomu użytkownika wśród kolejek priorytetowych. Zauważmy że jądro nie modyfikuje priorytetów poziomu jądra, jak również nie pozwala aby w wyniku przeliczenia priorytetów jakiś proces uzyskał wartość z zakresu poziomu jądra.

Bibliografia

[Bach] Budowa systemu operacyjnego UNIX, Maurice J. Bach, WNT 1995.

[Bovet] Linux kernel, Daniel P. Bovet, Marco Cesati, Wydawnictwo RM, Warszawa 2001.

[Goodheart] Sekrety magicznego ogrodu. UNIX System V Wersja 4 od środka, Berny Goodheart, James Cox, WNT 2001.

Piotr Karpiuk, pk167277@zodiac.mimuw.edu.pl