SVR4 scheduler




Do spisu treści tematu 3


Zadanie z laboratorium "Systemów operacyjnych"

SVR4 scheduler




Oryginalny algorytm szeregowania w Linuxie, oprócz podstawowych zalet,
takich jak prosta implementacja i gwarancja, że proces nie zostanie zagłodzony,
ma jedną poważną wadę, którą jest mała odporność na duże obciążenie systemu
- w rzeczywistości algorytm SCHED_OTHER zachowuje się jak algorytm
typu Round-Robin, gdzie wszystkie procesy dostają równy kwant czasu na
działanie, bez względu na charakterystykę ich działania (jedyny wpływ jaki
można mieć na szeregowanie, to możliwość modyfikacji wartości nice
procesu). Linux równo traktuje procesy - procesy wykonujące dużo obliczeń
(tzw. compute-bound tasks), które są wywłaszczane nie są w żaden
sposób karane, a procesy interaktywne (tzw. transput-bound tasks)
oddające dobrowolnie procesor, nie są za to nagradzane. Więcej o szeregowaniu
w Linuxie można przeczytać tutaj.


Zadanie polega na zaimplementowaniu uproszczonego wariantu algorytmu
szeregowania stosowanego w Systemie V Release 4 (w skrócie SVR4).


W jądrze Unixa SVR4 wprowadzono podział na klasy szeregowania (wg ważności):
procesów czasu rzeczywistego, procesów systemowych, procesów standardowych
(time-shared). Dzięki podziałowi na klasy, implementacja jądra pozwala
na łatwą modyfikację i dodawanie nowych algorytmów szeregowania. Ponieważ
implementacja takiego mechanizmu wymagałaby znacznego nakładu mało naukowej
pracy, przedmiotem zadania jest implementacja algorytmu szeregownia procesów
typu time-shared. Algorytm został znacznie przez autora zadania
uproszczony - w oryginale istnieje podział na niezależne kolejki priorytetowe
(w każdej z kolejek znajdują procesy o tym samym priorytecie), pominięto
też kilka innych szczegółów. Zainteresowanych odsyłam do żródła [1].


Algorytm

1. Z każdym procesem związane są następujące wartości:


counter - kwant czasu jaki pozostał procesowi na wykonanie


user_pri - statyczny priorytet ustalany przez użytkownika

dynamic_pri - dynamiczny priorytet ustalany przez jądro w
przedziale 0..59

effective_pri - efektywny priorytet procesu, będący sumą dwóch
powyższych

sched_time - czas (godzina), w którym proces został wznowiony
(czyli kiedy zaczął "zużywać" swój kwant czasu)


2. Z każdą wartością efektywnego priorytetu związane są następujące
parametry.


quantum - wartość kwantu czasu przydzielonego procesowi o
danym priorytecie


expire_pri - wartość dynamic_pri przydzielona procesowi,
gdy całkowicie wykorzysta przydzielony kwant czasu


wakeup_pri - wartość, wg której obliczany jest effective_pri,
gdy proces wraca do kolejki procesów gotowych, po tym jak został usunięty
w związku z oczekiwaniem na zasób bądź zdarzenie (w takiej sytuacji effective_pri
= wakeup_pri + user_pri, dopiero przy następnym przydziale kwantu,
do obliczenia effective_pri zostanie użyta wartość dynamic_pri).



maxwait - maksymalna liczba sekund jaką proces o danym priorytecie
może czekać


promote_pri - wartość dynamic_pri przydzielana procesowi,
gdy czeka na procesor dłużej niż maxwait sekund.

Wymienione parametry znajdują się w tablicy schedparam indeksowanej
priorytetem zwanej dalej tablicą szeregowania.

Przykład standardowych wartości w SVR4:



effective_pri

quantum

expire_pri

wakeup_pri

maxwait

promote_pri



0

100

0

10

5

10



1

100

0

11

5

11



....

....

....

....

....

....



59

10

49

59

5

59







3. Schemat podstawowych funkcji algorytmu:


szeregowanie:

if (kolejka procesów gotowych nie jest pusta)
for (każdy proces w kolejce procesów gotowych)
wybierz proces o największej wartości effective_pri;
else
wybierz proces wymiany (idle);

if (wybrany proces różny od bieżącego)
ustaw sched_time w strukturze procesu;

wznów wybrany proces;


aktualizacja:

if (bieżący proces wykorzystał swój czas)
{
effective_pri = user_pri + schedparam[dynamic_pri].expire_pri;
przeszereguj procesy;
}

if (od czasu ostatniej modyfikacji minęła sekunda)
{
for (każdy proces w kolejce procesów gotowych)
if (proces różny od bieżącego && czeka dłużej niż maxwait)
effective_pri = user_pri + schedparam[dynamic_pri].promote_pri;

zapamiętaj czas modyfikacji;
}


budzenie:

effective_pri = user_pri + wakeup_pri;
dodaj proces do kolejki procesów gotowych;



Uwagi


Należy dodać opisany algorytm szeregowania - nie należy usuwać
standardowego algorytmu SCHED_OTHER.



Nie oznacza to, że jednocześnie mogą działać procesy szeregowane standardową
metodą oraz nową - należy wprowadzić mechanizm globalnego włączania/wyłączania
nowego algorytmu dostępny za pomocą dodanej funkcji systemowej (w jądrze).
Funkcja ta to:

int sched_svr4(int mode)

Parameter mode != 0 włącza nowy tryb szeregowania. Funkcja
wywołana przez zwykłego użytkownika powinna kończyć się błędem EPERM.


Parametry tablicy szeregowania są przykładem. Ich dobór, w szczególności
dobór zakresów priorytetów, jest przedmiotem badań rozwiązującego zadanie
i powinien zostać uzasadniony.


Należy wykorzystać funkcje służące do modyfikacji parametru nice
procesu do ustawiania priorytetu użytkownika.


Dodatkowo punktowane będzie (mam nadzieję :-) zaimplementowanie mechanizmu
pozwalającego modyfikować i odczytywać parametry tablicy szeregowania.


Dla uproszczenia można usunąć kod związany z algorytmami szeregowania
procesów czasu rzeczywistego (SCHED_RR i SCHED_FIFO).
Kwestie czasu rzeczywistego nie są przedmiotem zadania.


Należy dokonać porównania standardowego algorytmu z zadanym, przedstawiając
odpowiednie wnioski. Istotne mogą być takie parametry jak: częstość przełączania
kontekstu, średni czas oczekiwania procesu na otrzymanie procesora, średnia
wielkość przydzielanego kwantu czasu, itp.


Warto zapoznać się z zadaniem
nr 16.




Bibliografia


Berny Goodheart, James Cox The Magic Garden Explained, PRENTICE
HALL 1994

LabLinux, rozdział Szeregowanie
procesów

Projekt-Linux,
rozdział Sposoby
szeregowania procesów




Autor: Grzegorz Całkowski