W Linuxie istnieją dwa rodzaje priorytetów:
W Linuxie wyższe priorytety przyznawane są zadaniom, które zostaną ocenione przez planistę jako zadania drugiego typu, ze względu na to, że wymagamy od systemu, aby możliwie szybko reagował na żądanie/zakończenie się operacji we/wy (najlepszy przykład to edytor tekstu - nawet jeżeli w tle wykonują się bardzo czasochłonne operacje oczekujemy, że system zareaguje możliwie szybko na naciśnięcie przez nas klawisza).
Kwant czasu - wartość liczbowa określająca ilość czasu procesora, jaką zadanie otrzymało w danej epoce. Domyślna wartość kwantu czasu jest określnona przez politykę planisty. Dobór odpowiedniego rozmiaru kwantu nie jest wcale łatwym zadaniem. Zbyt duże kwanty czasu spowodują, że system poważnie ucierpi na interaktywności. Jeżeli kwant czasu będzie za mały, znaczna część czasu procesora będzie marnowana na przełączanie kontekstu zadań. Poza tym pojawia się problem między wymaganiami zadań zorientowanych na korzystanie z procesora i zadaniami zlecającymi/oczekującymi na operacje we/wy. Zadania, które cały czas wykorzystują na wykonanie kodu potrzebują dużych kwantów. Zadania interaktywne znacznie mniejszych. W większości unixowych systemów domyślny kwant czasu przyznawany aplikacjom waha się w okolicach 20ms, podczas gdy w Linuxie domyślny czas jest znacznie dłuższy i wynosi 100ms.
Podstawową strukturą służącą do przechowywania zadań gotowych do
wykonania na danym procesorze jest zdefiniowana w pliku kernel/sched.c
struktura runqueue, zawierająca listę wszystkich gotowych
zadań
przypisanych danemu procesorowi. Każdy procesor posiada osobną listę
zadań. Każde zadanie może znajdować się w dokładnie jednej kolejce.
struct runqueue {
spinlock_t lock; /* do ochrony kolejki */
unsigned long nr_running; /* liczba zadań gotowych*/
unsigned long nr_switches; /* liczba przełączeń kontekstu */
unsigned long expired_timestamp; /* czas ostatniej zamiany wskaźników kolejki active i expired */
unsigned long nr_uninterruptible; /* liczba zadań śpiących z wyłączonymi przerwaniami */
struct task_struct *curr; /* wskaźnik do obecnie wykonywanego zadania */
struct task_struct *idle; /* wskaźnik do zadania bezczynności procesora */
struct mm_struct *prev_mm; /* mapa pamięci ostatnio wykonywanego zadania */
struct prio_array *active; /* wskaźnik do tablicy zadań aktywnych */
struct prio_array *expired; /* wskaźnik do tablicy zadań wyczerpanych */
struct prio_array arrays[2]; /* wskaźniki do powyższych tablic */
int prev_cpu_load[NR_CPUS]; /* ilość zadań na każdym z procesorów */
struct task_struct *migration_thread;
struct list_head migration_queue;
atomic_t nr_iowait; /* liczba zadań czekających na zakończenie operacji we/wy */
struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
Zadanie z kolejki active, które wyczerpie swój kwant czasu zostaje umieszczone w kolejce expired z nowo wyliczonym priorytetem i nowym kwantem czasu. Reguła ta nie dotyczy zadań wysoce interaktywnych. Zadania o bardzo wysokim priorytecie po wyczerpaniu swojego kwantu czasu mogą zostać z powrotem umieszczone w tablicy active. O wszystkim decyduje to, czy zadanie jest wystarczająco interaktywne oraz czy zadania w tablicy expired nie czekają za długo. Gdy wszystkie zadania z kolejki active wyczerpią swoje kwanty czasu następuje zamiana wskaźników między kolejkami active i expired. W kodzie schedule() przedstawia się to następująco:
struct prio_array array = rq->active;
if (!array->nr_active) {
rq->active = rq->expired;
rq->expired = array;
}
struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array array;
int idx;
prev = current;
array = rq->active;
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);
Każde zadanie jest uruchamiane z ustalonym priorytetem z przedziału
<-20,
19> (domyślnie 0) - jest to tak zwany priorytet statyczny zadania
(przechowywany w zmiennej static_prio struktury task_struct
opisującej
zadanie). Statyczny dlatego, że nie zmienia się w czasie wykonywania
zadania (chyba, że użytkownik zmieni tę wartość "ręcznie").
Do szeregowania zadań planista wykorzystuje wartość priorytetu
dynamicznego przechowywanego pod zmienną prio również
w task_struct. Do
obliczenia wartości zmiennej prio wykorzystywana jest funkcja
effective_prio():
static int effective_prio(task_t *p)
{
int bonus, prio;
if (rt_task(p)) /* jeśli zadanie p jest zadaniem czasu rzeczywistego nie zmieniamy priorytetu */
return p->prio;
bonus = CURRENT_BONUS(p) - MAX_BONUS / 2; /* obliczamy wartość o którą zmniejszymy priorytet zadania */
prio = p->static_prio - bonus; /* nowy priorytet = priorytet statyczny - bounus */
if (prio < MAX_RT_PRIO) /* zadanie nie może mieć priorytetu mniejszego niż -20 */
prio = MAX_RT_PRIO;
if (prio > MAX_PRIO-1) /* ani większego niż 19 */
prio = MAX_PRIO-1;
return prio;
}
#define CURRENT_BONUS(p) \
(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
MAX_SLEEP_AVG)
#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
Zmienna sleep_avg przechowywana w task_struct zadania określa stosunek czasu, jaki zadanie spędziło na spaniu do czasu, jaki wykorzystało na efektywne korzystanie z procesora. W momencie, gdy zadanie zostaje obudzone sleep_avg zwiększane jest o tyle, ile czasu zadanie spędziło w kolejce zadań uśpionych (ale sleep_avg nie może przekroczyć MAX_SLEEP_AVG). Każde tyknięcie zegara w czasie działania zadania powoduje zmniejszenie wartości sleep_avg aż osiągnie 0. Okazuje się, że ten sposób mierzenia interaktywności jest bardzo miarodajny, gdyż określa nie tylko czas spania zadania, ale stosunek tego czasu do czasu wykorzystania przez zadanie procesora.
Nowy kwant czasu obliczany jest na podstawie priorytetu dynamicznego. Służy do tego funkcja task_timeslice(), która dokonuje skalowania priorytetów na wielkość kwantu czasu (wyższa wartość priorytetu - większy kwant czasu). Do wyliczenia używane jest makro SCALE_PRIO, które jako parametry przyjmuje domyślną wartość kwantu czasu oraz aktywny priorytet zadania. Uwaga: zadanie powstałe w wyniku funkcji fork() dostaje połowę pozostałego czasu swojego ojca, drugą połowę bierze ojciec.
#define SCALE_PRIO(x, prio) \
max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)
static unsigned int task_timeslice(task_t *p)
{
if (p->static_prio < NICE_TO_PRIO(0))
return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);
else
return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
}
Zadanie, które zawiesiło się w oczekiwaniu na jakieś wydarzenie (naciśnięcie klawisza, transmisję danych z dysku, podniesienie semafora itd.) zaznacza swój stan na zadanie uśpione, umieszcza się w specjalnej kolejce zadań uśpionych i usuwa się z kolejki zadań aktywnych. Zadanie, które zasnęło nie jest brane pod uwagę przy szeregowaniu. Dopiero gdy zostanie spełniony warunek, na który czeka uśpione zadanie zostaje ono usunięte z kolejki zadań oczekujących i dodane z powrotem do kolejki zadań aktywnych. A teraz fragment z sched.c:
/* q to kolejka zadań oczekujących */
DECLARE_WAITQUEUE(wait, current);
add_wait_queue(q, &wait);
set_current_state(TASK_INTERRUPTIBLE); /* lub TASK_UNINTERRUPTIBLE */
while (!warunek) /* "warunek" to wydarzenie na które czeka zadanie */
schedule();
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);
Jak już było wspomniane w jądrze 2.6 dostarczone zostały
mechanizmy
wspomagające szeregowanie zadań dla architektur wieloprocesorowych.
Każdy procesor ma osobną kolejkę zadań do niego przypisanych. Co się
dzieje jeżeli w naszym wieloprocesorowym występuje zachwianie równowagi
w przydziale ilości zadań do poszczególnych procesorów. W Linuxie 2.6
zaiplementowana została efektywna metoda równoważenia obciążenia
procesorów dla architektury SMP.
Funkcją odpowiedzialną za utrzymywanie równowagi w obciążeniu
procesorów jest load_balance() zdefiniowana w sched.c
Wywoływana może być w dwóch przypadkach:
Jeżeli funkcja schedule byłaby wywoływana jedynie jawnie z kodu programu mogłoby to doprowadzić do sytuacji, w której program działa w nieskończoność (po prostu nie wywoływałby funcji schedule()). Na szczęście istnieje flaga need_resched, która jest informacją dla jądra, że trzeba wywołać funkcję schedule(). Flaga ta może zostać ustawiona przez"
We wszystkich wersjach Linuxa do 2.4 włącznie wywłaszczanie dotyczyło jedynie procesów użytkownika.
W Linuxie 2.6 po raz pierwszy wprowadzono możliwość wywłaszczania wątków jądra.
W przeciwieństwie do standardowego wywłaszczania w przypadku jądra należy być szczególnie ostrożnym.
Aby móc wywłaszczyć wątek jądra, należy najpierw sprawdzić, czy jądro znajduje się w bezpiecznym
stanie. Bezpieczny stan oznacza, że jądro nie ma założonych żadnych blokad. Warunku tego nie trzeba
było sprawdzać w przypadku wywłaszczania zadań użytkownika, ponieważ mieliśmy pewność, że zadanie jest
w stanie bezpiecznym (dlatego, że wywłaszczenie następowało tylko w określonych sytuacjach - patrz pkt.
tu).
Każdy wątek jądra posiada w strukturze thread_info zmienną preempt_count, której wartość odpowiada
ilości założonych przez wątek blokad. Jeżeli wartość preempt_count jest równa 0, oznacza to, że jądro
jest w stanie bezpiecznym i można wywłaszczyć bieżący wątek jądra.
Zatem żeby doszło do wywłaszczenia wątku jądra muszą być spełnione dwa warunki:
Linux dostarcza dwie polityki szeregowania zadań czasu rzeczywistego:
SCHED_FIFO