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

1. Należy dodać opisany algorytm szeregowania - nie należy usuwać standardowego algorytmu SCHED_OTHER.
        
   
2. 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.
              
3. 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.
       
4. Należy wykorzystać funkcje służące do modyfikacji parametru nice procesu do ustawiania priorytetu użytkownika.
       
5. Dodatkowo punktowane będzie (mam nadzieję :-) zaimplementowanie mechanizmu pozwalającego modyfikować i odczytywać parametry tablicy szeregowania.
       
6. 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.
         
7. 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.
      
8. Warto zapoznać się z zadaniem nr 16.
        
       

Bibliografia

1. Berny Goodheart, James Cox The Magic Garden Explained, PRENTICE HALL 1994
2. LabLinux, rozdział Szeregowanie procesów
3. Projekt-Linux, rozdział Sposoby szeregowania procesów