Linux jest systemem operacyjnym, w ktorym jednoczesnie moze wykonywac
sie wiele procesow. Poniewaz ilosc procesorow jest mniejsza od ilosci
mogacych jednoczesnie sie wykonywac procesow, dlatego system operacyjny
musi na zmiane sprawiedliwie, wedlug potrzeb i mozliwosci przydzielac czas
wszystkim dzialajacym procesom.
Scheduler jest czescia jadra Linuxa decydujaca o kolejnosci i czasie
wykonywania sie procesow na procesorze. Pod okresleniem scheduler
nalezy rozumiec szereg funkcji i struktur zaimplementowanych w jadrze,
a takze wykonywanych w czasie pracy przerwan systemu (sprzetowych i
programowych),
ktore sluza do przelaczania kontekstu (procesu) w jakim dziala procesor.
Opis powstal na podstawie wersji jadra 2.0.0. Nie wszystkie informacje sa prawdziwe dla wczesniejszych wersji. W wersji tu opisanej pojawilo sie dwie nowe metody szeregowania procesow czasu rzeczywistego (real-time processes): SCHED_FIFO i SCHED_RR.
Calosc opisu mozna podzielic na cztery czesci:
Pojecie procesu zostalo zdefiniowane w temacie 1. Tutaj pojawia sie on jeszcze raz, po to by wskazac jego zmienne i wlasnosci istotne dla szeregowania w Linuxie.
W Linuxie kazdy proces reprezentowany jest przez strukture danych task_struct. Istotne z tej struktury sa pola:
W kodzie ten proces jest okreslany nazwa INIT TASK. Ta nazwa jest nieco mylaca. Nie jest to dobrze znany proces init, ktory jest zawsze w systemie procesem ktory ma PID rowny 1. Czasami jest to proces nazywany TASK SWAPPER. Ta nazwa tez moze mylic - to cos wcale nie przelacza procesow na procesorze, jak by mogla ta nazwa sugerowac. Przelaczanie procesow jest w praktyce skomplikowana procedura wykonywana przez szereg powiazanych ze soba przerwan: zegara, urzadzen zewnetrznych itp.
Fakty sa takie:
Scheduler utrzymuje liste wszystkich procesow gotowych. Jest to lista cykliczna dwukierunkowa struktur task_struct, w ktorej powiazania sa utrzymywane w polach next_run i prev_run.
Na te kolejke procesow gotowych wygodnie jest patrzec, jako na zestaw kolejek - po jednej dla kazdej wartosci rt_priority, zatem jako na 100 roznych kolejek procesow. Dalej kazda taka kolejka bedzie nazywana kolejka koncepcyjna. W danym momencie czesc z nich moze byc pusta. Procesy z kolejki koncepcyjnej odpowiadajacej wyzszej wartosci rt_priority sa wczesniej wykonywane, niz procesy z nizszych kolejek. Zawsze przy przelaczaniu procesow na procesorze do wykonania zostaje wybrany pierwszy proces z niepustej kolejki koncepcyjnej o najwyzszej wartosci rt_priority.
Dokladniejszy opis tego jak to sie dzieje, ze procesy z kolejki procesow gotowych rzeczywiscie dziela sie procesorem jest w czesci opisujacej algorym szeregowania.
(ka)
Scheduler linuxowy udostepnia procesom trzy tryby (metody) szeregowania. Jeden dla normalnych procesow - jedynie ten tryb byl dostepny we wczesniejszych niz 2.0.0 wersjach jadra - i dwa dla procesow czasu rzeczywistego (real-time processes). Dwa ostatnie pojawily sie w wersji 2.0.0 po raz pierwszy.
Jest to standardowa, uzywana przez wiekszosc procesow, metoda dzielenia sie czasem procesora. Jest to metoda szeregowania zgodna ze standardem POSIX.1b (oficjalnie POSIX.4). Procesy szeregowane w tym trybie maja wartosc rt_priority rowna 0. Pozostaja one wiec w jednej wspolnej kolejce koncepcyjnej odpowiadajacej najnizszemu rt_priority=0. Kolejnosc wybierania procesow z tej kolejki jest uzalezniona od dynamicznie ustalanego efektywnego priorytetu bazujacego na wartosci priority procesu.
Jest to pierwszy z dwoch trybow szeregowania dla procesow czasu rzeczywistego.
Procesy szeregowane w tym trybie maja wartosc rt_priority wieksza
od zera (czyli z przedzialu [1,99] ). Oznacza to, ze proces szeregowany
w tym trybie moze sie znalezc w jednej z 99 kolejek koncepcyjnych. Proces
podlegajacy tej metodzie szeregowania, jesli znajdzie sie na poczatku kolejki
koncepcyjnej odpowiadajacej jego wartosci rt_priority
i zostanie dopuszczony do procesora, to przed swym zakonczeniem
nie bedzie mogl byc wywlaszczony przez zaden inny proces z jego
kolejki koncepcyjnej. Moze on zostac
przeniesiony na koniec tej kolejki tylko wtedy gdy odda procesor na
wlasne zyczenie (gdy wykona funkcje sytemowa sched_yield()). Zadne
inne zdarzenie nie jest w stanie przeniesc tego procesu na koniec
kolejki.
Proces taki moze byc wywlaszczony z procesora tylko
przez proces pochodzacy
z kolejki koncepcyjnej o wyzszym priorytecie (przez proces o wiekszej wartosci
parametru rt_priority), albo gdy zglosi on zadanie I/O (wtedy
zostanie on wyrzucony z kolejki procesow gotowych).
Jest to drugi tryb szeregowania przeznaczony dla procesow czasu rzeczywistego. Rozni sie ona tylko tym od trybu SCHED_FIFO, ze procesy szeregowane w tym trybie po przydzieleniu im procesora dzialaja co najwyzej przez przydzielony kwant czasu. Po przekroczeniu tego czasu system wywlaszcza taki proces i ustawia go na koniec kolejki koncepcyjnej.
Niezaleznie od trybu szeregowania, proces nowo uruchamiany, lub taki ktory zmienia tryb szeregowania lub dostaje nowa wartosc rt_priority zawsze zostaje umieszczony na koncu kolejki koncepcyjnej odpowiadajacej jego wartosci rt_priority.
Tryby SCHED_FIFO i SCHED_RR nie zostaly jeszcze dokladnie sprawdzone - czasami system, z dzialajacymi procesami szeregowanymi w tych trybach moze dzialac dziwnie, a nawet sie "zawieszac". Nie zaimplementowano jeszcze wszystkich funkcji systemowych obslugujacych takie procesy.
Uwaga dla programistow: Piszac, czy testujac program, ktory ma byc szeregowany w jednym z trybow szeregowania dla procesow czasu rzeczywistego (SCHED_FIFO i SCHED_RR), dobrze jest miec pod reka uruchomiony terminal o wiekszej wartosci parametru rt_priority niz program testowany. Moze on byc przydatny do zabicia procesu testowanego w przypadku jego zapetlenia sie. Taki proces nie dopuszcza do procesora procesu pochodzacego z kolejki o mniejszym (lub rownym priorytecie dla procesow SCHED_FIFO), dlatego moze powstawac problem gdy stracimy kontrole nad tym co piszemy.
(ka)
Wszystkie opisywane w tym punkcie funkcje sa wewnetrznymi funkcjami jadra.
{
if (biezacy proces szeregowany jest w SCHED_RR i wykorzystal swoj kwant czasu) {
przydziel mu nowy kwant;
przesun go na koniec kolejki procesow gotowych;
}
if (biezacy proces spi)
if (otrzymal nieblokowany sygnal || osiagnal ustawiony timeout)
zmien jego stan na gotowy;
else
usun go z kolejki procesow gotowych;
for (kazdy proces z kolejki procesow gotowych)
wybierz proces o najwyzszym efektywnym priorytecie;
if (najwyzszy priorytet = 0)
for (kazdy proces)
zmodyfikuj jego dynamiczny priorytet;
if (brak procesu do wykonania)
wybierz proces 0;
if (wybrany proces jest rozny od biezacego) {
ustaw ewentualny timeout dla procesu biezacego;
przelacz kontekst na wybrany proces;
}
}
Funkcja ta "oglada" najpierw biezacy proces.
Jesli jest on szeregowany w trybie SCHED_RR i
wykorzystal caly swoj kwantu czasu, to przydziela mu sie nowy
kwant rowny jego wartosci nice, a nastepnie przesuwa
na koniec kolejki procesow gotowych za pomoca funkcji
move_last_runqueue().W procedurze obslugi przerwania zegarowego oprocz wielu rzeczy nie
zwiazanych z szeregowaniem procesow odbywa sie: inkrementacja licznika
jiffies oraz wywolanie funkcji
update_process_times().
Funkcja ta dekrementuje licznik counter biezacego
procesu i jesli osiaga on wartosc zero, ustawia
flage need_resched tak, ze tuz po wyjsciu z przerwania
wywolywana jest funkcja schedule().
(ks)
Do dyspozycji programisty Linuxa udostepniono zestaw funkcji systemowych wplywajacych na prace modulu szeregujacego. Mozna wyroznic 3 ich grupy:
- zmiana wartosci nice procesu o zadana wartosc.
DEFINICJA: int nice(int increment)
WYNIK: 0 w przypadku sukcesu
-1, gdy blad: errno = EPERM (nieuprawniona proba zwiekszenia
priorytetu)
Dodatnia wartosc parametru oznacza zmniejszenie priorytetu procesu,
natomiast ujemna - zwiekszenie. Do zwiekszenia priorytetu procesu uprawniony
jest jedynie nadzorca systemu.
Dzialanie funkcji polega na dodaniu wartosci parametru (obcietej do przedzialu
-40..40 i przekonwertowanej do postaci wewnetrznej jadra) do priorytetu
(pole priority) procesu, ktory ja wywolal.
Funkcja ta zostala zastapiona przez nowoczesniejsza
funkcje setpriority().
- odczytanie wartosci nice procesu / zbioru procesow.
DEFINICJA: int getpriority(int which, int who)
WYNIK: priorytet zbioru procesow w przypadku sukcesu
-1, gdy blad: errno = EINVAL (bledna wartosc parametru which)
ESRCH (pusty zbior procesow)
Funkcja ta podaje wartosc nice zadanego zbioru procesow, czyli najwyzszy priorytet sposrod priorytetow wszystkich procesow nalezacych do tego zbioru. Zbior zadaje sie poprzez odpowiednie wartosci parametrow. I tak, w zaleznosci od wartosci parametru which, jest to:
Procesy nalezace do zbioru wyznaczane sa przez przejrzenie calej tablicy procesow.
- ustawienie wartosci nice procesu / zbioru procesow.
DEFINICJA: int setpriority(int which, int who, int niceval)
WYNIK: 0 w przypadku sukcesu
-1, gdy blad: errno = EINVAL (bledna wartosc parametru which)
ESRCH (pusty zbior procesow)
EPERM (nieuprawniona proba zmiany
priorytetu procesu)
EACCESS (nieuprawniona proba zwiekszenia
priorytetu procesu)
Funkcja ta ustawia priorytet wszystkich procesow w zadanym zbiorze.
Zbior ten zadaje sie identycznie jak w przypadku funkcji getpriority().
Pole priority kazdego procesu w zbiorze ustawiane jest na wartosc
niceval, obcieta do zakresu -20..20 i przekonwertowana
do postaci wewnetrznej jadra.
Do zmiany priorytetu procesu uprawniony jest jego wlasciciel, efektywny
wlasciciel oraz nadzorca systemu. Do zwiekszenia priorytetu procesu uprawniony
jest jedynie nadzorca systemu.
- odczytanie trybu szeregowania procesu.
DEFINICJA: int sched_getscheduler(pid_t pid)
WYNIK: tryb szeregowania procesu w przypadku sukcesu
-1, gdy blad: errno = EINVAL (bledna wartosc parametru pid)
ESRCH (nie znaleziono procesu o identyfikatorze pid)
Funkcja ta zwraca tryb szeregowania procesu okreslonego przez pid lub tez procesu biezacego, gdy pid=0.
- ustawienie trybu i parametrow szeregowania procesu.
DEFINICJA: int sched_setscheduler(pid_t pid, int policy, struct sched_param *param)
WYNIK: 0 w przypadku sukcesu
-1, gdy blad: errno = EINVAL (bledne wartosci parametrow))
ESRCH (nie znaleziono procesu o identyfikatorze pid)
EPERM (nieuprawniona proba zmiany
parametrow szeregowania procesu)
Funkcja ta ustawia tryb i parametry szeregowania procesu okreslonego przez pid lub procesu biezacego, gdy pid=0. Parametry szeregowania zawarte sa w strukturze typu sched_param, ktora w obecnej wersji jadra zawiera tylko jedno pole - statyczny priorytet realtime:
struct sched_param {
int sched_priority;
};
Nastepnie dany proces jest przesuwany na koniec kolejki procesow gotowych
i wykonuje sie przeszeregowanie.
Do zmiany parametrow procesu uprawniony jest jego wlasciciel, efektywny
wlasciciel oraz nadzorca systemu. Do ustawienia trybow realtime i zmiany
ich parametrow uprawniony jest jedynie nadzorca systemu.
Uwaga: Jest to niebezpieczna funkcja, za pomoca ktorej mozna na przyklad
zawiesic swoj komputer.
- odczytanie parametrow szeregowania procesu.
DEFINICJA: int sched_getparam(pid_t pid, struct sched_param *param)
WYNIK: 0 w przypadku sukcesu
-1, gdy blad: errno = EINVAL (bledna wartosc parametru pid)
ESRCH (nie znaleziono procesu o identyfikatorze pid)
Funkcja zapisuje do struktury *param parametry szeregowania procesu okreslonego przez pid, lub procesu biezacego dla pid=0.
- ustawienie priorytetu realtime danego procesu.
DEFINICJA: int sched_setparam(pid_t pid, struct sched_param *param)
WYNIK: 0 w przypadku sukcesu
-1, gdy blad: errno = EINVAL (bledna wartosc parametrow)
ESRCH (nie znaleziono procesu o identyfikatorze pid)
EPERM (nieuprawniona proba zmiany
parametrow szeregowania procesu)
Funkcja ta ustawia priorytet realtime dla procesu danego przez pid
lub procesu biezacego dla pid=0, przesuwa proces na koniec kolejki
procesow gotowych i wykonuje przeszeregowanie.
Jej wolanie ma sens jedynie dla procesow szeregowanych w jednym z trybow
realtime, i musi byc wykonane przez nadzorce systemu.
- odczytanie zakresu wartosci priorytetow realtime dla danego trybu szeregowania.
DEFINICJA: int sched_get_priority_min(int policy)
int sched_get_priority_max(int policy)
WYNIK: dolny/gorny zakres wartosci priorytetu realtime w przypadku sukcesu
-1, gdy blad: errno = EINVAL (bledna wartosc parametru policy)
Dla zadanego przez parametr trybu szeregowania funkcje zwracaja dolny
i gorny zakres przedzialu, w jakim moze znajdowac sie priorytet procesu
realtime szeregowanego w tym trybie.
Chociaz w Linuxie granice te sa stale, to zaleca sie uzywanie tych
funkcji dla wiekszej przenosnosci oprogramowania.
- oddanie procesora na wlasne zyczenie.
DEFINICJA: int sched_yield(void)
WYNIK: 0
Funkcja ta sluzy do samodzielnego wywlaszczenia sie biezacego procesu.
W odroznieniu od systemowej funkcji pause proces nie zostaje
uspiony. Zostaje po prostu przesuniety na koniec kolejki procesow gotowych,
a nastepnie zostaje wykonane przeszeregowanie procesow.
Jesli wszystkie procesy w systemie maja efektywny priorytet nizszy od priorytetu
procesu biezacego, to wywolanie funkcji nie przynosi zadnego efektu.
(ks)
(ka & ks)