Spis treści
Systemy wieloprogramowe wymagają isnienia mechanizmów zapewniających współbieżne działanie procesów. Przełączanie się między jednym procesem a drugim powinno następować tak szybko, aby wydawało się, że oba działają jednocześnie. Od algorytmu szeregowania, decydującego kiedy zmienić wykonujący się proces i na jaki, zależy szybkość i wydajność systemu operacyjnego. Algorytm szeregujący jest wykonywany bardzo często. Musi zatem być szybki i zajmować mało pamięci operacyjnej.
Istotnym parametrem jest kwant czasu, na jaki proces uzyskuje dostęp do procesora. Jeśli jest on za mały, przełączanie między procesami staje się zbyt drogie. Gdyby np. kwant czasu był porównywalnie duży z narzutem systemowym związanym z wyborem następnego procesu i zmianą kontekstu, procesor połowę czasu spędzałby nad ''formalnościami''. Jeśli natomiast kwant czasu jest za duży, znika wrażenie jednoczesności.
Wybór nowego procesu musi nastąpić wtedy, gdy:
Strategia szeregowania to zasady, zgodnie z którymi zapada decyzja kiedy i jak wybrać następny proces do wykonywania się. W Linuksie proces może być szeregowany zgodnie z jedną z następujących polityk:
Proces czasu rzeczywistego szeregowany zgodnie ze strategią SCHED_FIFO będzie działał dopóki:
Strategia SCHED_RR różni się od SCHED_FIFO tym, że procesowi przyznaje się kwant czasu, po którego minięciu, proces jest przenoszony na koniec kolejki procesów gotowych z odnowionym kwantem. Następnym wybranym do wykonywania się będzie ten sam proces tylko wtedy, gdy nie ma procesu czasu rzeczywistego o priorytecie równym bądź większym od jego priorytetu. Polityka SCHED_RR zapewnia więc sprawiedliwy podział dostępu do procesora między tak samo ważnymi procesami.
Strategia SCHED_OTHER jest podobna do SCHED_RR z tym, że tutaj, gdy procesowi skończy się kwant czasu, będzie on musiał czekać na jego odnowienie do czasu, aż w kolejce procesów gotowych nie będzie procesu z niezerowym kwantem (mogą być procesy, które oddały procesor dobrowolnie).
Przykład
W systemie działają procesy RR_1, OTHER_2, FIFO_3, OTHER_4 i RR_5 szeregowane odpowiednio według strategii SCHED_RR , SCHED_OTHER , SCHED_FIFO , SCHED_OTHER i SCHED_RR , wszystkie procesy czasu rzeczywistego mają ten sam priorytet, OTHER_4 jest ważniejszy niż OTHER_2. Przyjmijmy, że procesy nie oddają procesora i nie muszą na nic czekać. W takiej sytuacji:
Algorytm szeregowania ( scheduler ) dzieli czas procesora na epoki. Epoka zaczyna się wtedy, gdy w kolejce procesów gotowych jest jakiś proces (oprócz idle_task) i nie ma takiego, którego kwant czasu jest dodatni (jeśli kolejka jest pusta, to wykonuje się idle_task). Wówczas algorytm szeregowania oblicza na nowo kwanty dla wszystkich procesów. Procesy, którym nie skończył się czas przyznany w poprzedniej epoce (tak może być w przypadku procesów oczekujących w kolejkach na jakieś zdarzenia), otrzymują nowy kwant zwiększony o połowę z tego, co im zostalo.
Algorytm szeregowania wybiera z procesów w stanie TASK_RUNNING ten, dla którego funkcja goodness(), okreslająca ''ważność'' procesu, zwróci najwyższą wartość. Każdy proces może być wybrany wiele razy w jednej epoce, np. wtedy, gdy nie wyczerpie swojego kwantu czasu i zawiesi sie w oczekiwaniu na operację wejścia/wyjścia.
Funkcja schedule() jest wywoływana:
Scheduler korzysta z następujących danych:
if (current->pid) {
current->counter--;
if (current->counter < 0) {
current->counter = 0;
current->need_resched = 1;
}
}
( idle_task - proces, który wykonuje się tylko wtedy, gdy nie ma innych w stanie TASK_RUNNING, tylko on ma pid 0; dla niego zmniejszanie kwantu czasu nie ma sensu)
zmienne lokalne:
struct task_struct *prev; /* poprzednio wykonujący się proces */
struct task_struct *next; /* proces, który będzie się wykonywał jako następny */
struct task_struct *p; /* zmienna pomocnicza */
struct list_head *tmp; /* ----- || --------- */
int c; /* wartość najwyższego znalezionego priorytetu */
Funkcja schedule() działa według następującego algorytmu:
prev = current;
if (prev->policy == SCHED_RR)
if (!prev->counter) {
prev->counter = 1 + ((20 - prev->nice) >> 2);
move_last_runqueue(prev);
}
switch (prev->state) {
case TASK_INTERRUPTIBLE:
if (signal_pending(prev)) {
prev->state = TASK_RUNNING;
break;
}
default:
del_from_runqueue(prev);
case TASK_RUNNING:;
}
prev->need_resched = 0;
next = &init_task; c = -1000;
if (prev->state == TASK_RUNNING) {
c = goodness(prev, prev->active_mm);
next = prev;
}
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
{
int weight = goodness(p, prev->active_mm);
if (weight > c)
c = weight, next = p;
}
}
if (!c) {
struct task_struct *p;
for_each_task(p)
p->counter = (p->counter >> 1) + (1 + ((20 - p->nice) >> 2));
}
Procesy, które nie wykorzystały swojego kwantu w poprzedniej epoce, mają teraz większy kwant - połowa z czasu, jaki pozostał jest dodawana do nowo obliczonego. Wartość pola nice może wynosić od -19 do 20, więc liczba (1 + ((20 - p->nice) >> 2)) należy do przedziału <1, 10>.
Następnie ponownie wybierany jest proces, dla którego goodness() zwraca najwyższa wartość - wracamy do punktu nr 5.
if (prev == next) {
prev->policy &= ~SCHED_YIELD;
if (current->need_resched)
"goto punkt 1." ;
return;
switch_to(prev, next, prev);Jeśli kolejka procesów gotowych jest pusta, wybrany zostanie init_task.
prev->policy &= ~SCHED_YIELD;
if (current->need_resched)
"goto punkt 1.";
return;
Funkcja goodness() ocenia ''ważność'' procesu. Działa według następującego algorytmu:
Ta funkcja jest wywoływana, gdy pewien proces przejdzie do stanu TASK_RUNNING. Nowy proces wywłaszczy aktualny (ustawi mu flage need_resched), jeśli funkcja goodness() dla nowego zwróci wartość większą niż ( goodness() dla aktualnego + 1).
W Linuksie jest jeden algorytm szeregowania procesów, realizowany przez funkcję schedule(). Pewne jej fragmenty umieszczone są pomiędzy dyrektywami #ifdef CONFIG_SMP i #endif, i dotyczą tylko przypadku wielu procesorów, pozostała część kodu jest wspólna (chociaż z tego wspólnego kodu pewne fragmenty istotne są tylko przy wielu procesorach). Tutaj będą omówione te czynności, które scheduler musi dodatkowo zrobić przy wielu procesorach względem opisywanego wcześniej algorytmu.
W przypadku wielu procesorów potrzebne są dodatkowe informacje dla schedulera. Istotne pola ze struktury task_struct to:
Z każdym procesorem związany jest jeden proces idle_task, wykonujący się, kiedy nie ma żadnego w stanie TASK_RUNNING.
Przy wyborze procesu, który ma się wykonywać, trzeba sprawdzić, czy nie wykonuje się on już na innym procesorze oraz czy może się wykonywać na tym, który się zwolnił - sluży do tego funkcja can_schedule(). W deskryptorze nowo wybranego procesu, ustawiane są pola has_cpu na 1 oraz processor na ten procesor, który zostaje mu przyznany.
Po przełączeniu kontekstu wywoływana jest funkcja __schedule_tail(prev), w której wykonywane są następujące czyności:
Działanie funkcji goodness() w systemie wieloprocesorowym różni sie od wcześniej omawianej wersji tylko tym, że proces szeregowany zgodnie ze strategią SCHED_OTHER może dostać dodatkowe punkty za korzystanie poprzednio z procesora, który teraz jest wolny. Jest to spowodowane tym, że sprzętowa pamieć podręczna może nadal zawierać potrzebne dane dla tego procesu. Wartość tych dodatkowych punktów to wartość stalej PROC_CHANGE_PENALTY, która w architekturze i386 wynosi 15 (w przypadku innych architektur: 15 albo 20).
Ta funkcja szuka dla procesu procesora, na którym najdłużej wykonywało się idle_task lub takiego, na którym wykonuje się proces najmniej ważny i mniej ważny o przynajniej 2 punkty przyznawane przez funkcję goodness() od procesu, dla którego szukamy procesora.
Jeśli chcemy zmodyfikować priorytety procesów lub strategie ich szeregowania, mamy do dyspozycji kilka wywołań systemowych. Wszyscy użytkownicy mogą zmniejszać priorytety swoich procesów, natomiast zwiększać priorytety i modyfikować priorytety procesów dowolnych użytkowników może tylko superużytkownik.
Funkcja modyfikuje priorytet procesu, w którym jest wywoływana. increment ma należeć do przedziału <-40, 40>. Jeśli jest za mały, jego wartość ustawiana jest na -40, jeśli za duży - na 40. Następnie do pola nice aktualnie wykonującego się procesu dodawana jest wartość increment. Jeśli wynik jest mniejszy niż -20, to jest ustawiany na -20, jeśli jest większy niż 19, to jest ustawiany na 19. Ujemny increment oznacza podwyższenie priorytetu, dodatni - obniżenie. nice() jest zwykle używane do obniżenia priorytetu procesu, a użytkownik, który tą funkcję wywołuje jest miły (ang. nice) dla innych użytkowników.
getpriority(int which, int who)
Funkcja zwraca liczbę 20 + priorytet procesu o najwyższym priorytecie spośród wszystkich w grupie, którą określają parametry which i who. Dodanie 20 do najwyższego priorytetu jest spowodowane tym, że priorytet może być ujemny, a ujemna wartość zwracana oznacza błąd. which może przyjmować jedną z poniższych wartości:
setpriority(int which, int who, int niceval)
Funkcja ustawia pole nice deskryptorów procesów należących do odpowiedniej grupy (znaczenie which i who - tak jak w poprzedniej funkcji) na niceval.
sched_getscheduler(pid_t pid)
Funkcja zwraca politykę szeregowania procesu o podanym pidzie.
sched_setscheduler(pid_t pid, int policy, struct sched_param *param)
Funkcja zmienia strategię szeregowania na policy i priorytet rt_priority procesu o pidzie pid na param.sched_priority (struktura sched_param ma tylko jedno pole o nazwie sched_priority). Dla strategii SCHED_OTHER rt_priority musi wynosić 0, dla SHED_FIFO i SCHED_OTHER musi być dodatnie i mniejsze od 100.
sched_getparam(pid_t pid, struct sched_param *param)
Funkcja zwraca w parametrze param strukrutę sched_param zawierającą priorytet rt_priority procesu o pidzie pid.
sched_setparam(pid_t pid, struct sched_param *param)
Funkcja działa podobnie do sched_setscheduler() z tym, że tutaj można zmienić tylko priorytet procesu, strategia szeregowania pozostaje ta sama. Nie ma więc sensu stosowanie tego wywołania dla procesów zwykłych, których rt_priority może być tylko zerem.
sched_yield(void)
Tą funkcję proces wywołuje wtedy, gdy chce dobrowolnie oddać procesor. Zanim to się stanie, sprawdzane jest, czy są procesy w stanie TASK_RUNNING, które nie mają przydzielonego procesora (jeśli jest tylko jeden procesor, to ta liczba to (ilość_procesów_gotowych - 1). Jeśli takich nie ma, to nie ma rezygnacji z procesora. W przeciwnym przypadku, jeśli proces jest szeregowany zgodnie ze strategią SCHED_OTHER , ustawiana jest mu flaga SCHED_YIELD. Następnie, niezależnie od polityki szeregowania, ustawiana jest flaga need_resched.
Przykład (błędnego działania tej funkcji):
Kolejka procesów gotowych w systemie jednoprocesorowym zawiera procesy: FIFO_1 i RR_2. Strategie szeregowania tych procesów są takie, jak sugerują ich nazwy. Procesy FIFO_1 i RR_2 mają taki sam priorytet. Aktualnie wykonuje się proces FIFO_1 i wywołuje on sched_yield(). Co się teraz stanie? System sprawdzi, że są procesy gotowe i czekające na procesor i zostanie ustawiona flaga need_resched w deskryptorze procesu FIFO_1. Kogo wybierze scheduler? Wybierze znowu FIFO_1, gdyż nie została ustawiona flaga SCHED_YIELD ani też proces nie zmienił swojej pozycji w kolejce - jest pierwszym o najwyższym priorytecie.
Czy zatem wywoływanie sched_yield() przez procesy czasu rzeczywistego ma sens? Wydaje się, że nie, gdyż albo nie ma procesu o wyższym priorytecie i wtedy wykonujący się proces pozostaje ten sam, albo jest proces o wyższym priorytecie i wtedy on wywłaszcza aktualnie wykonujący sie proces (ale za to można sobie obniżyć priorytet...). W przypadku procesów zwykłych ustawiana jest flaga SCHED_YIELD i wtedy funkcja goodness() zwraca -1. Następnie procesor może dostać jakiś inny proces od razu lub będzie przeszeregowanie.
(We wcześniejszej wersji sched_yield() proces wykonujący tą funkcję był przestawiany na koniec kolejki procesów gotowych. Takie rozwiązanie tutaj nic nie zmienia, gdyż scheduler najpierw liczy priorytet procesu, który ostatnio się wykonywał i wybierze inny tylko wtedy, gdy ten ma wyższy priorytet - więcej na ten temat w ostatnim rozdziale)
sched_get_priority_min(int policy)
sched_get_priority_max(int policy)
Funkcje zwracają odpowiednio wartość najniższego i najwyższego możliwego priorytetu rt_priority dla procesu szeregowanego zgodnie ze strategią policy.
sched_rr_get_interval(pid_t pid, struct timespec *interval)
Dla procesu o pidzie pid funkcja zwraca w strukturze interval (ta struktura ma pola: tv_sec okreslające liczbę sekund, tv_nsec - nanosekund):
strategia SCHED_FIFO
Mamy w systemie proces P czasu rzeczywistego szeregowany zgodnie ze strategią SCHED_FIFO. Nie ma procesu rzeczywistego o priorytecie wyższym niż priorytet P. W takiej sytuacji procesowi P nikt nie powinien przeszkadzać. Załóżmy, że P ma za zadanie sprawdzać wartość swojego pola counter i, jeśli się zmniejszyło, wypisać informację, ile jeszcze czasu zostało do przeszeregowania. Chcemy zobaczyć 40 takich informacji. Wynik wywołania takiego program może być następujący:
pozostalo: 0 sec, 60000000 nsec
pozostalo: 0 sec, 50000000 nsec
pozostalo: 0 sec, 40000000 nsec
pozostalo: 0 sec, 30000000 nsec
pozostalo: 0 sec, 20000000 nsec
pozostalo: 0 sec, 10000000 nsec
pozostalo: 0 sec, 0 nsec
I więcej informacji od procesu P już nie widzimy, wykonuje się tak jakby się nie wykonywał. Taka sytuacja ma miejsce, gdyż proces P po wyczerpaniu swojego kwantu czasu, nie może się dalej wykonywać, gdyż scheduler nie odnawia mu tego kwantu, a funkcja update_process_times() zmniejsza pole counter aktualnemu procesowi niezależnie od polityki szeregowania.
Poprawa tego może wygądać np. tak:
if ((prev->policy & SCHED_FIFO) && (!prev->counter))
prev->counter = 1 + ((20 - prev->nice) >> 2);
i być umieszczona przed tą częścią funkcji schedule(), która jest odpowiedzialna za wybór nowego procesu.
strategia SCHED_RR
W systemie mamy dwa procesy szeregowane zgodnie ze strategią SCHED_RR o tym samym priorytecie. Zadaniem tych procesów jest dziesięciokrotne poinformowanie, że został im przydzielony nowy kwant czasu (wtedy, kiedy to następuje). Procesy powinny wymieniać się procesorem, jednak tak sie nie dzieje. Oto wynik przykładowego takiego programu:
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 714) Mam odnowiony counter (*********).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
(proces nr: 713) Mam odnowiony counter (+++++++++).
Dzieje się tak dlatego, że funkcja schedule() najpierw bierze pod uwagę ostatnio wykonujący się proces, a inny niż on jest wybierany tylko wtedy, gdy ma wyższy priorytet.
Jak to poprawić? Można byłoby nie wyróżniać poprzednio działającego procesu, tylko wywoływać goodness() po kolei dla każdego procesu z listy runqueue. W takiej sytuacji procesy RR1 i RR2 z powyższego przykładu wymieniałyby sie procesorem. Ale co by było w sytuacji, kiedy w stanie TASK_RUNNING byłyby dwa procesy FIFO1 i FIFO2, szeregowane zgodnie ze strategią SCHED_FIFO, a działającym aktualnie byłby FIFO2? (procesy wstawiamy do kolejki runqueue zawsze na początek, więc taka sytuacja jest możliwa) W tym przypadku FIFO2 oddałby procesor FIFO1 (gdyż ten jest wcześniej w kolejce), co jest z kolei sprzeczne z założeniami strategii SCHED_FIFO. Można więc wywoływać funkcję goodness() dla procesu, który ostatnio się wykonywał tylko wówczas, gdy jest to proces z polityką SCHED_FIFO.
Przykład podany przy opisie tej funkcji pokazuje, że działa ona inaczej niż można byłoby się spodziewać. Zakładając, że mamy już dobrze działającego schedulera, poprawienie tego może wyglądać tak:
Marta Lis