Szeregowanie procesów w Linuxie 2.6x

Cechy charakterystyczne:

• działa na zasadzie wywłaszczania procesów
• złożoność czasowa O(1) (nowość)
• możliwość wywłaszczenia procesu wykonującego kod jądra (nowość)

Wywłaszczanie procesów:

Większość nowoczesnych systemów operacyjnych działa na zasadzie wywłaszczania procesów. Algorytm szeregujący decyduje, kiedy dany proces musi zwolnić procesor na rzecz innego procesu. Alternatywne podejście polega na czekaniu aż proces dobrowolnie zwolni procesor (co w prosty sposób może prowadzić do zagłodzenia).

Złożoność czasowa O(1).

Dzięki zastosowanym nowym strukturom danych oraz wyliczaniu nowych kwantów czasu (czasu procesora) za każdym razem, gdy proces wyczerpie poprzedni kwant (zamiast wyliczać wszystkie kwanty czasu zbiorowo), szeregowanie procesów w jądrach 2.6x działa w czasie stałym, a wiec nie jest zależne od obciążenia systemu.

Możliwość wywłaszczenia procesu wykonującego kod jądra.

Wiele systemów operacyjnych, w tym także poprzednie realizacje Linuxa, nie pozwala na wywłaszczenie procesu będącego w trakcie wykonywania kodu jądra. Wywłaszczenie takiego procesu jest możliwe dopiero gdy powróci on do trybu użytkownika. Taka implementacja jest na pewno prostsza, ale cierpi na tym interaktywność.

Seria 2.6 dopuszcza wywłaszczenie procesu znajdującego się w trybie jądra, pod warunkiem, że nie ustawił żadnej blokady.

Zastosowane struktury danych i algorytmy:

• kolejka procesów aktywnych runque, która zawiera 2 tablice prio-array (priority arrays):

- active - w niej znajdują się procesy, które nie wyczerpały jeszcze

swojego kwantu czasu (zazwyczaj)

- expired - zawiera procesy, które wykorzystały już swój kwant czasu

• proces szeregujący wykorzystuje również niektóre pola struktury thread_info i task_struct.

struct runqueue
Struktura runqueue stanowi podstawę dla całego algorytmu szeregowania procesów. Jest to kolejka zawierająca wszystkie aktywne procesy przydzielone do danego procesora (kiedy proces zasypia, jest z niej usuwany). Runqueue zawiera dwie tablice prio-array oraz dodatkowe informacje, takie jak liczba aktywnych procesów, czy stempel czasowy końca poprzedniej epoki.
 
struct runqueue {
 spinlock_t lock; /* zabezpiecza tą kolejkę */
 
 unsigned long nr_running; /* liczba aktywnych procesów */
 
/* ... */
 unsigned long expired_timestamp; /* czas ostatniej podmiany wzkaźników active i expired */
 
 
 unsigned long long timestamp_last_tick; /* timestamp of last scheduler tick */
 
 task_t *curr, *idle; /* aktualny process i process idle*/
 
/* ... */
 
 prio_array_t *active, *expired, arrays[2]; /* wskaźniki active I expired oraz rzeczywiste tablice, na które wskazują */
 
 
/* ... */
 };

struct prio-array

Jest to tablica zawierająca po jednej kolejce procesów dla każdego możliwego priorytetu (dynamicznego).

struct prio_array {
 unsigned int nr_active; /* liczba aktywnych procesów w tej tablicy */
 unsigned long bitmap[BITMAP_SIZE]; /* mapa bitowa przechowująca informacje o tym, które kolejki w tablicy nie są puste */
 struct list_head queue[MAX_PRIO]; /* kolejki procesów o równych priorytetach */
 };

Znalezienie pierwszego procesu o danym priorytecie jest oczywiście bardzo proste. Natomiast aby znaleźć najwyższy priorytet, dla którego lista procesów nie jest pusta, korzystamy z mapy bitowej. W ten sposób można szybko odnaleźć proces o najwyższym priorytecie.

Algorytm – szkic:

· sprawdzenie w bitmapie tablicy active jaki jest najwyższy spośród priorytetów procesów w active i wybranie z tablicy active pierwszego z procesów o takim właśnie priorytecie

· kiedy proces wyczerpie swój kwant czasu, wyliczany jest nowy priorytet i kwant czasu, a proces przenoszony jest do tablicy expired, na koniec kolejki procesów o takim samym priorytecie (są od tego wyjątki, ale o tym później)

· kiedy w tablicy active nie ma już aktywnych procesów, zamieniane są wskaźniki active i expired. Jest to koniec epoki. Uwaga: w tym miejscu nie są już przeliczane priorytety ani kwanty czasu.

Priorytety.

· priorytet statyczny, czyli wartość nice przesunięta do przedziału [100, 139].

· priorytet dynamiczny, wyliczany na podstawie priorytetu statycznego i stopnia interaktywności procesu

Priorytet statyczny.

Wartość nice mieści się w przedziale od -19 do 20 (domyślna wartość to 0), przy czym 20 oznacza najniższy priorytet. Priorytet statyczny przechowywana jest w polu static_prio struktury task_struct. Nice może być modyfikowane przez użytkownika za pomocą funkcji nice(), zwiększającej tę wartość o podany argument. Tylko root ma prawo ją zmniejszyć.

Priorytet dynamiczny

Kluczem do obliczenia priorytetu dynamicznego jest wartość sleep_avg. Określa ona stopień interaktywności procesu. Za każdym razem, kiedy proces jest budzony, jego sleep_avg jest zwiększane. Natomiast czas wykonywania tego procesu jest odejmowany od jego sleep_avg.

Funkcja effective_prio()oblicza priorytet dynamiczny na podstawie wartości static_prio oraz stopnia interaktywności procesu (sleep_avg).

Jeżeli proces jest procesem czasu rzeczywistego, funkcja zwraca jego priorytet bez żadnych zmian. W p.p. od priorytetu statycznego odejmowany jest bonus o wartości od -5 do 5.

Bonus to po prostu przeskalowana wartość sleep_avg.

Wyliczanie kwantu czasu:

· nowy kwant czasu wyliczany jest na podstawie priorytetu statycznego (funkcja task_timeslice())

· po wykonaniu fork() kwant czasu procesu macierzystego jest rozdzielany pomiędzy ojca i syna

#define BASE_TIMESLICE(p) (MIN_TIMESLICE \
+ ((MAX_TIMESLICE - MIN_TIMESLICE) * \
(MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1)))
 
 static unsigned int task_timeslice(task_t *p)
 {
  return BASE_TIMESLICE(p);
 }

Wyjątki, o których obiecałam opowiedzieć:

Niektóre procesy, po wyczerpaniu przydzielonego im kwantu czasu procesora, mogą zostać z powrotem umieszczone w tablicy active, zamiast w expired. Dzieje się to w dwóch przypadkach:

· interaktywne procesy

· procesy czasu rzeczywistego

Interaktywne procesy

Interaktywne procesy, po wyczerpaniu przydzielonego im kwantu czasu procesora wstawiane są powrotem do tablicy active z nowym kwantem czasu. Dzieje się tak pod warunkiem, że żaden z procesów w tablicy expired nie jest zagłodzony.

Jeżeli interaktywny proces zajmuje procesor zbyt długo, może zostać wywłaszczony przez inny proces o tym samym priorytecie. Jak długie jest „zbyt długo” określa stała TIMESLICE_GRANULARITY.

Procesy czasu rzeczywistego.

Procesy czasu rzeczywistego mają pierwszeństwo przed pozostałymi procesami, które mogą uzyskać dostęp do procesora dopiero, kiedy wszystkie procesy czasu rzeczywistego przestaną być aktywne lub dobrowolnie oddadzą procesor.

Są dwa sposoby szeregowania procesów RT:

- SCHED_FIFO

- SCHED_RR

Procesy czasu rzeczywistego maja priorytety od 1 do MAX_RT_PRIO-1 (czyli od 1 do 99). Priorytety zwykłych procesów odpowiadają wartościom 100 – 140.

Szeregowanie procesów w systemach wieloprocesorowych.

W systemie wieloprocesorowym każdy procesor utrzymuje swoją własną kolejkę procesów aktywnych.

Jeżeli jest to możliwe, proces wykonuje się ciągle na tym samym procesorze. Jeśli jednak wystąpią większe różnice pomiędzy obciążeniem procesorów, część procesów przenoszona jest pomiędzy kolejkami procesów aktywnych.

Linux 2.6x scheduler a Linux 2.4x scheduler

2.6	2.4
Szeregowanie w czasie O(1)	O(liczba aktywnych procesów)
Możliwość wywłaszczenia procesu wykonującego kod jądra	Brak takiej możliwości (gorsza obsługa procesów czasu rzeczywistego)
Średni kwant czasu: 100 ms	Średni kwant czasu: 210 ms
Plik kernel.sched.c jest trzy razy dłuższy	Prostsza logika, ale mniej przewidywalne zachowanie
Procesy wykonujące dużo obliczeń mają obniżany priorytet, a interaktywne podwyższany.	Nie przewiduje obniżenia priorytetu zachłannego procesu wykonującego dużo obliczeń, procesy interakcyjne miałyby dzięki temu większe szanse otrzymać procesor

Uwagi końcowe

Działanie procesu szeregującego można dostosowywać do konkretnych zastosowań, a co za tym idzie do różnych wymagań, manipulując stałymi w kodzie jądra, a następnie kompilując je. Można na przykład zwiększyć wydajność obliczeń kosztem czasu reakcji systemu na, powiedzmy, klikniecie myszki (mniej czasu traci się na ciągłe przełączanie kontekstów itp.). Podobno najlepsza jest tu metoda prób i błędów (ze względu na dużą liczbę różnych stałych) ;-)