Informatyka MIMUW

Szeregowanie w systemie UNIX

Algorytm rotacyjny z wywłaszczaniem polega na tym, że po upływie kwantu czasu (około 1 sekundy) następuje przełączenie kontekstu na inny proces o takim samym priorytecie. Jeśli nie ma procesu o takim samym priorytecie, proces kontynuuje działanie przez kolejny kwant czasu. Jeśli jednak przed upływem kwantu czasu pojawi się proces gotowy o wyższym priorytecie nastąpi wywłaszczenie, tym samym również przełączenie kontekstu. Wyjątkiem od tej reguły jest przypadek wykonywania programu jądra. Jądro w tradycyjnym systemie UNIX jest niewywłaszczalne, co oznacza, że nie można przerwać procesu, który działa w trybie jądra, nawet jeśli pojawi się proces o wyższym priorytecie. Proces może oczywiście wejść w stan oczekiwania, wówczas jądro stanie się dostępne dla innych procesów. Przełączenie kontekstu następuje zatem w następujących przypadkach:

• bieżący proces wchodzi w stan oczekiwania w wyniku zażądania dostępu do zasobu (operacji wejścia-wyjścia, synchronizacji itp.) lub kończy swoje działanie,
• w wyniku przeliczenia priorytetów jakiś proces gotowy uzyskuje wyższy priorytet niż proces bieżący,
• następuje wejście w stan gotowości (obudzenie) procesu o wyższym priorytecie.

Zakres priorytetu od 0 do 49 zarezerwowany jest dla procesów w trybie jądra, a pozostałe wartości są priorytetami procesów w trybie użytkownika.

• Stosowany jest algorytm rotacyjny z wywłaszczaniem, oparty na priorytetach dynamicznych.
• Wartość priorytetu jest z zakresu od 0 do 127, mniejsza wartość liczbowa oznacza wyższy priorytet.
• Priorytet (dynamiczny) składa się z części statycznej i części modyfikowanej przez planistę.
• Część statyczna składa się z bazy (definiowanej przez system) oraz wartość nice (ustalanej przez użytkownika lub nadzorcę).
• Priorytet procesu ustalany jest zawsze, gdy proces ten przechodzi z trybu jądra do trybu użytkownika.
• Okresowo (mniej więcej co 1 sekundę) przeliczane są priorytety wszystkich procesów gotowych.

Struktury danych na potrzeby szeregowania

W systemie dąży się do tego, aby procesy jak najszybciej opuszczały tryb jądra, gdyż jest to zasób krytyczny dla funkcjonowania systemu i niewywłaszczalny. Dlatego większość procesów, znajdujących się w trybie jądra jest uśpiona w oczekiwaniu na jakieś zdarzenia (np. zakończenie operacji wejścia-wyjścia). Jeśli jakiś proces jest budzony w wyniku zajścia oczekiwanego zdarzenia, otrzymuje on tzw. priorytet uśpienia tego zdarzenia, który jest oczywiście priorytetem poziomu jądra. Na przykład: priorytet uśpienia dla wyjścia z terminala wynosi 28, a priorytet uśpienia dla operacji dyskowej wynosi 20. Obudzony w ten sposób proces ma wyższy priorytet niż wykonywany proces poziomu użytkownika, więc następuje wywłaszczenie. Gdyby jednak wykonywany był kod jądra przez jakiś proces, wznowienie procesu oczekującego nastąpi dopiero po zwolnieniu jądra (opuszczeniu bądź wejściu w oczekiwanie) przez proces wykonywany.

• Na potrzeby szeregowania procesy zorganizowane są w kolejkę priorytetową— qs.
• Każda pozycja tablicy kolejek odpowiada czterem wartościom priorytetu.
• Wektor bitowy whichqs wskazuje pozycje, na których są niepuste kolejki.
• Wyróżnia się 3 zakresy priorytetu:
  • poziom jądra dla procesów nieprzerywalnych,
  • poziom jądra dla procesów przerywalnych,
  • poziom użytkownika.

Kolejka priorytetowa

Struktura qs jest tablicą kolejek, czyli odpowiednich wskaźników. Sama kolejka jest zbudowana na liście dwukierunkowej i łączy deskryptory procesów, dokładnie struktury proc, stanowiące część pełnego deskryptora procesu.

W systemie jest 1 proces o priorytecie z przedziału 0 – 3, 2 procesy o priorytecie z przedziału 4 – 7, 3 procesy o priorytecie z przedziału 8 – 11, nie ma procesu o priorytecie z przedziału 12 – 15 itd. Wektor whichqs wskazuje pozycje niepuste i umożliwia szybką lokalizację kolejki o najwyższym priorytecie, w której jest jakiś proces.

slajd 6

Parametry funkcji priorytetu

Parametr cpu jest wartością liczbową, która jako miara wykorzystania procesora jest zwiększana, gdy proces jest wykonywany oraz stopniowo zmniejszana, gdy proces nie wykorzystuje procesora.

Wartość nice może być zwiększana przez użytkownika zwykłego, co skutkuje zmniejszeniem priorytetu, natomiast zmniejszana (w celu zwiększenia priorytetu) może być przez nadzorcę. Domyślnie wartość nice ustawiana jest na 20.

Wyodrębnienie parametrów pri i usrpri wynika z różnicy wartości priorytetu w trybie użytkownika i w trybie jądra. W trybie jądra proces otrzymuje priorytet wyższy, wynikający np. z rodzaju operacji wejścia-wyjścia, jakiej zażądał. Przed powrotem do trybu użytkownika priorytet musi jednak wrócić do poprzedniej wartości. W trybie użytkownika zatem wartości parametrów pri i usrpri są takie same, a w trybie jądra wartość parametru pri jest mniejsza (wyższy priorytet), niż usrpri.

• cpu_i — miara dotychczasowego wykorzystania procesora przez i-ty proces,
• baza_i — priorytet bazowy procesu i-tego,
• nice_i — składowa priorytetu procesu i-tego definiowana przez użytkownika,
• pri_i — priorytet procesu i-tego (mniejsza wartość oznacza wyższy priorytet),
• usrpri_i — priorytet procesu i-tego w trybie użytkownika.

Przeliczanie priorytetu

1. Każdy takt zegara (lub co któryś, np. co 4, zależnie od implementacji) zwiększa wartość cpu bieżącego (wykonywanego) procesu.
2. Przy każdym przeliczaniu priorytetów procesów gotowych (co około 1 sekundę) wartość ta, niezależnie od tego, czy była zwiększana, czy nie, dzielona jest przez 2 (współczynnik zaniku).
3. Przy każdym przeliczaniu priorytetów, po zmniejszeniu wartości parametru cpu następuje przeliczenie priorytetu użytkownika, zgodnie z podanym wzorem. Na priorytet ten składa się więc:
   • baza — umożliwiająca podział na pasma priorytetów,
   • cpu — miara wykorzystania procesora,
   • nice — wartość określana przez użytkownika.
4. Jeśli proces jest w trybie użytkownika (jego priorytet pri jest na poziomie użytkownika) następuje zmiana parametru pri. Konsekwencją tej zmiany może być jednak konieczność umieszczenia procesu w innej kolejce. Operacja przebiega zatem tak, że najpierw proces jest usuwany z kolejki, następuje podstawienie nowej wartości parametru pri , a następnie ponowne powiązanie deskryptora w kolejce na właściwej pozycji. Taki sposób przeliczania ogranicza skalowalność, gdyż czas potrzebny na tę operację jest proporcjonalny do liczby procesów. Zwiększająca się liczba procesów powoduje więc wydłużenie tego czasu.

slajd 8

Przykład

Przykład obrazuje zmiany priorytetów trzech procesów w systemie. Początkowy priorytet (załóżmy, że jest to baza + nice ) każdego z procesów wynosi 60, a miara wykorzystania procesora wynosi 0. 60 razy na sekundę następuje takt zegara, który zmienia parametr cpu. Proces P₁ wykorzystuje jako pierwszy procesor (oś czasu skierowana jest w dół, ). Po 60 taktach następuje przeliczenie priorytetów. Parametr cpu₁ osiąga wówczas wartość 60 i jest dzielony przez 2. Podobnie jest to robione dla pozostałych procesów, ale dla nich wartość parametru cpu jest cały czas 0, gdyż nie wykorzystywały one procesora. Połowa przeliczonej wartości parametru cpu dodawana jest do statycznej części priorytetu procesu P₁ , co daje wynik 75. Wyższy priorytet mają zatem procesy P₂ i P₃ , czyli następuje przełączenie kontekstu na proces P₂. Po kolejnych 60 taktach następuje przeliczenie priorytetów. W międzyczasie wartość cpu₂ zwiększyła się do 60 i nie zmieniła się w przypadku pozostałych procesów. Po przemnożeniu przez współczynnik zaniku cpu1 wynosi 15, cpu₂ — 30, a cpu₃ — cały czas 0. Po dodaniu połowy wartości parametru cpu do statycznej części otrzymujemy usrpri1 o wartości 67, usrpri₂ o wartości 75 i usrpri₃ o wartości 60. Najwyższy priorytet ma więc proces P₃, a po kolejnych 60 taktach priorytet procesu P₁ ponownie wzrośnie do największego w systemie (wartość 63).

slajd 9