Jedną z najważniejszych zmian o nowym jądrze Linuxa 2.6 jest wprowadzenie schedulera działającego w czasie stałym. Dzięki temu zdecydowanie poprawiona została współpraca Linuxa z komputerami wieloprocesorowymi, nowy algorytm działa znacznie lepiej pod dużymi obciążeniami. Zmiana została wprowadzona przez Ingo Molnara.
Na początek przypomnienie, czym jest scheduler.
W zwyczajnym komputerze jest jeden procesor, a wiele procesów. W systemach wieloprocesorowcych jest wiele procesów, ale i tak zazwyczas procesów jest więcej. Jeden procesor w danej chwili może obsługiwać tylko jeden proces, więc obsługiwane procesy muszą sie jakoś zmieniać. Właśnie proces szeregujący (ang. scheduler) jest odpowiedzialny za wybieranie procesu, któremu należy się procesor."
Przed schedulerem stawianych jest wiele wymagań.
Najważeniejsze z nich to
Przed analizą samego algorytmu warto przypomnieć sobie jeszcze jakie stany może mieć proces. W Linux-ie procesy gotowe do wykonania i aktualnie wykonywane znajdują sie w stanie TASK_RUNNING. Mianowicie:
Proces o najwyższych priorytecie dynamicznym będzie dostawał procesor
Są różne rodzaje procesów: procesy czasu rzeczywistego (SCHED_RR lub SCHED_FIFO), procesy zwykłe (SCHED_OTHER) oraz proces idle.
Procesy czasu rzeczywistego (RT-real time) zawsze będą się wykonywać przed procesami zwykłymi, z tego prostego powodu, że
będą miały większy priorytet dynamiczny.
Procesy RT mają również priorytet statyczny (rt_priority). Jest on z zakresu od 1 do 99.
Priorytet dynamiczny jest obliczany w funkcji goodness(), która oblicza priorytety dynamiczne dla wszystkich procesów.
W przypadku procesów klasy RT priorytet dynamiczny zostanie obliczony jako 1000 + priorytet statyczny (a więc będzie z zakresu
od 1001 do 1099).
Dla procesów zwykłych czas jest podzielony na epoki. W każdej epoce każdy proces ma przydzielony pewien kwant czasu. W tej epoce ten proces będzie mógł maksymalnie przez tyle czasu używać procesora. W momencie, gdy wszystkie procesy, które aktualnie mogą się wykonywać (czyli te w stanie TASK_RUNNING) wyczerpały już swój kwant czasu zaczyna się nowa epoka. W momencie rozpoczęcia nowej epoki obliczany są kwanty czasu dla wszystkich procesów
Procesy zwykłe mają również coś w rodzaju priorytetu statycznego. Jest nim parametr nice z zakresu od -19 do 20.
Priorytet dynamiczny jednak będzie wyliczany nie tylko na jego podstawie. Jest również pole counter, które oznacza
ilość niewykorzystanych przez proces jednostek czasu w danej epoce. Może się zdarzyć, że proces nie wykorzystał swoich jednostek,
gdyż np. spał i nie był w stanie TASK_RUNNING w czasie końca epoki.
Priorytet dynamiczny dla procesów zwykłych oblicza się sumując liczby counter i (20 - nice). Dodatkowo proces dostaje pewien
bonus, jeśli był wykonywany na tym samym procesorze.
Podsumujmy teraz stary algorytm, jego wady i zalety.
Jak widać scheduler spełnia swoje zadanie, ale jest jeszcze sporo rzeczy, które należałoby poprawić. Szczególny nacisk warto położyć na zmniejszenie narzutu samego schedulera i polepszenie współpracy z systemami wieloprocesorowymi.
Sam trzon algorytmu, podział na priorytet dynamiczny i statyczny, epoki, kwanty czasu pozostały te same. Wprowadzono jednak małe zmiany, które zdecydowanie usprawniły
Procesy klasy RT mają nadal priorytety od 0 do 99, jednak odwrotnie niż dawniej im mniejsza liczba tym większy priorytet.
Procesy zwykłe mają priorytety od 100 do 139. Priorytet dynamiczny obliczany jest na podstawie nice (jak dawniej od -19 do 20),
według wzoru 120 - nice. Dodatkowo - czego nie było w 2.4 priorytet dynamiczny uzależniony jest też od interaktywności procesu.
Interaktywność mierzy się patrząc ile czasu proces spędza na obliczeniach, a ile czasu na oczekiwaniu na użytkownika. Interaktywność
procesu może się zmieniać, tzn. jeżeli pewien proces najpierw miał dużą interaktywność, a później nagle zaczął wykonywać bardzo dużo
obliczeń korzystając ze swojego stosunkowo dużego priorytetu, to jego interaktywność spada. Współczynnik interaktywności waha się
z granicach -5 do 5.
Algorytm szeregowania korzysta z następujących struktur:
Nowy algorytm wyszukiwania najlepszego procesu działa następująco:
Podczas rozpoczęcia nowej epoki zamieniane są jedynie wskaźniki na tablice active i expired. Kwanty czasu potrzebne procesom w nowej epoce zostały obliczone już wcześniej, tuż po tym, jak proces wyczerpał swój kwant w starej epoce w funkcji scheduler_tick().
Nowy algorytm ma wiele zalet w porównanie do i tak niezłego algorytmu z jądra 2.4:
Dla zainteresowanych podaję tutaj parę struktur i kawałki kodu nowego jądra. Kod pochodzi konretnie z jądra 2.6.8.1. Wszystkie pokazane tu kawałki kodu są pobrane z pliku < linux/sched.c >
struct runqueue {
spinlock_t lock;
/*
* nr_running and cpu_load should be in the same cacheline because
* remote CPUs use both these fields when doing load calculation.
*/
unsigned long nr_running;
#ifdef CONFIG_SMP
unsigned long cpu_load;
#endif
unsigned long long nr_switches;
unsigned long expired_timestamp, nr_uninterruptible;
unsigned long long timestamp_last_tick;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];
int best_expired_prio;
atomic_t nr_iowait;
#ifdef CONFIG_SMP
struct sched_domain *sd;
/* For active balancing */
int active_balance;
int push_cpu;
task_t *migration_thread;
struct list_head migration_queue;
#endif
};
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
idx = sched_find_first_bit(array->bitmap); /* znalezienie najwyższego priorytetu */
queue = array->queue + idx; /* znalezienie odpowiedniej kolejki */
next = list_entry(queue->next, task_t, run_list); /* znalezienie procesu, który teraz będzie się wykonywał */
Korzystałem z następujących źródeł: