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
Wyszukiwarka
Podobne podstrony:
zadania 1 5 10ZADANIE (10)CAD ZADANIA 4 6 10cw3 zadanie 10ZADANIE (10)stat zadania1 10zadania 10ZADANIE (10)ZADANIE (10)Analiza Zadania 10ZADANIE (10)ZADANIE (10)ZADANIE (10)ZADANIE (10)Zadanie20 10 11Zadanie20 10 11więcej podobnych podstron