Systemy Operacyjne – semestr drugi

Wykład trzeci

Szeregowanie procesów w Linuksie

Istnieją dwa typy systemów wielozadaniowych: systemy wielozadaniowe z kooperacją (bez wywłaszczania) i systemy wielozadaniowe z wyw a ł szczaniem. W systemach

pierwszego typu proces zawsze dobrowolnie zrzeka się procesora i oddaje sterowanie do systemu operacyjnego. Drugi typ systemów kontroluje wykorzystanie procesora przez realizowane zadania i mo e

ż przerywać ich działanie. Zapobiega to sytuacji, w której pojedynczy proces mógłby zmonopolizować dostęp do procesora. Linux jak większoś

ć wspó c

ł zesnych systemów operacyjnych realizuje wielozadaniowość z wywłaszczaniem.

Schemat szeregowania jaki zastosowano w tym systemie opiera się na schemacie wielopoziomowych kolejek ze sprz en ęż iem zwrotnym. Podobnie, jak w innych

systemach uniksowych faworyzowane są procesy ograniczone wej c

ś iem-wyjściem, gdyż do tej kategorii procesów należą procesy interaktywne. Planista nie mo e ż jednak

ignorować procesów ograniczonych procesorem i nie powinien prowadzić do ich zagłodzenia. Kryterium decydującym o kolejno c ś i wykonania procesów jest ich priorytet.

W Linuksie zadania o wy s

ż zym priorytecie trafiają do kolejek o dłu s

ż zym kwancie czasu, podczas gdy procesy o ni s

ż zym priorytecie, odpowiednio do kolejek o krótszym

kwancie. W obr b

ę ie pojedynczej kolejki procesy są szeregowane według algorytmu rotacyjnego1, który każdemu z nich przydziela jednakowy kwant czasu. Ponadto zadania o wy s

ż zym priorytecie są uruchamiane przed procesami o ni s

ż zym priorytecie. Wartość priorytetu zadania jest ustalana zarówno przez system operacyjny, jak i mo e

ż być modyfikowana przez u y

ż tkownika. Może ona ulegać zmianie podczas istnienia procesu w systemie, a wi c ę jest to priorytet dynamiczny. Każdy nowy proces

otrzymuje domy l

ś ny priorytet, który z czasem mo e

ż ulec zmianie, zale n

ż ie od tego, czy ów proces cz c

ęś iej wykonuje operacje wej c

ś ia – wyj c

ś ia, czy cz c

ęś iej korzysta

z procesora. Warto c

ś i priorytetów rozdzielone są na dwa zakresy: pierwszy to poziom uprzejmo c ś i (ang. nice), do którego należą warto c

ś i od -20 do 19 (im mniejsza

wartoś ,

ć tym wi k

ę szy priorytet), drugi zakres, to warto c

ś i od 0 do 99. Są to priorytety dla zadań czasu rzeczywistego. Linux nie jest rygorystycznym systemem czasu rzeczywistego, ale istnieją odmiany jego j d

ą ra, które spełniają wymogi nakładane na takie systemy. Procesy czasu rzeczywistego podzielone są na dwie grupy. Te, które należą do pierwszej z nich szeregowane są wed u

ł g algorytmu FCFS, natomiast te należące do drugiej z u y

ż ciem algorytmu rotacyjnego. Dla procesów czasu

rzeczywistego priorytet jest priorytetem statycznym. Zwykłe procesy w Uniksie otrzymują domy l ś ny kwant czasu większy niż 20 ms (w Linuksie jest to 100 ms), który

w zale n

ż o c

ś i od ich „zachowania” mo e

ż si

ę zwi k

ę sza

ć lub zmniejsza .

ć Proces nie musi od razu wykorzystywa

ć całego dostępnego mu czasu, ale je l

ś i wyczerpie cały kwant

to ulega przeterminowaniu i nie mo e

ż zostać ponownie uruchomiony do czasu, aż pozosta e

ł procesy nie wyczerpią swoich kwantów czasu i nie zostanie uruchomiona

procedura ich przeliczania. Proces, który wyczerpie swój kwant czasu podlega jednocześnie wyw a ł szczaniu. Mo e

ż on również zostać wywłaszczony, je l

ś i w systemie

pojawi si

ę nowy proces o wy s

ż zym priorytecie. Mechanizm szeregujący w j d

ą rze 2.6 Linuksa posiada kilka godnych uwagi cech:

1.

implementuje szeregowanie w czasie O(1),

2.

implementuje idealne skalowanie SMP,

3.

implementuje powi z

ą ania wątków z procesorami w trybie SMP,

4.

daje dobrą wydajność procesów interaktywnych,

5.

równomiernie rozkłada czas procesora,

6.

stosuje optymalizację dla często spotykanego przypadku, kiedy w systemie jest kilka procesów gotowych do wykonania.

Planista wią e

ż z każdym procesorem w systemie kolejkę procesów gotowych do wykonania. Jest to struktura danych o nazwie struct runqueue, która została zdefiniowana w pliku kernel/sched.c Dodatkowo zostały zdefiniowane odpowiednie makrodefinicje pozwalaj c ą e na a

ł twy dostęp do tej struktury. Dost p

ę do kolejek

procesów gotowych jest synchronizowany przy pomocy semaforów z aktywnych oczekiwaniem, zwanych krócej ryglami pętlowymi. Jeśli istnieje konieczność modyfikacji kilku kolejek równocze n

ś ie, to muszą one by

ć zajmowane wed u

ł g c

ś i l

ś e okre l

ś onej kolejno c

ś i. Zapobiega to powstawaniu zakleszczeń.

Ka d

ż a z kolejek procesów gotowych zawiera dwa wska n

ź iki na tablice priorytetów: aktywną i przeterminowaną (struct prio_array). W strukturze opisuj c ą ej taką tablicę

znajduje się pole, okre l

ś ające liczbę gotowych do wykonania procesów w tej tablicy oraz tablica wska n ź ików do list procesów. Indeksy w tej tablicy są warto c

ś iami

priorytetów zadań. W obr b

ę ie listy procesy są szeregowane według algorytmu rotacyjnego z wyjątkiem niektórych procesów czasu rzeczywistego. Dodatkowo ka d ż a

tablica priorytetów wyposa on

ż a jest w map

ę bitową, której poszczególne bity okre l

ś ają, czy są w tablicy zadania o danym priorytecie do wykonania. Aby znaleźć zadanie o najwy s

ż zym priorytecie gotowe do wykonania nale y

ż jedynie znaleźć pierwszy ustawiony bit w tej mapie.

Kwanty czasu zadań są przeliczane zaraz po ich wyczerpaniu przez zadanie i zanim zadanie trafi do tablicy przeterminowanej. Wymiana „starych” priorytetów na

„nowe” sprowadza się wyłącznie do wymiany wska n

ź ików na tablicę aktywną i przeterminowaną.

Wyboru następnego do wykonania zadania dokonuje funkcja schedule(), wywoływana zawsze kiedy trzeba zawiesić w t ą ek jądra lub wywłaszczyć zdanie. Oprócz wyboru

zadania do uruchomienia dokonuje ona również przełączenia kontekstu za pomocą funkcji context_switch(). Kod funkcji schedule() jest bardzo prosty i jego wykonanie nie zale y

ż od liczby procesów w systemie. Najbardziej krytyczną pod względem czasu wykonania jest więc funkcja context_switch, której implementacja jest zale n ż a od

architektury platformy na której działa system.

Priorytet ka d

ż ego „zwyk eg

ł o” zadania jest ustalany na podstawie priorytetu statycznego, jakim jest poziom uprzejmo c ś i oraz na podstawie stopnia interaktywności

procesu. Interaktywność jest wyznaczana heurystycznie jako stosunek długo c ś i okresów zawieszenia i aktywno c

ś i. W zależno c

ś i od tak wyliczonego stopnia

interaktywno c

ś i priorytet dynamiczny jest zwi k

ę szany lub zmniejszany o 5. Każdy nowo powstały proces w systemie otrzymuje połowę kwantu czasu jaki w chwili jego tworzenia miał proces macierzysty. Po wyczerpaniu kwant jest na nowo wyliczany dla tego procesu. Zadania o najwy s ż zym priorytecie otrzymują kwanty o wielko c

ś i

200 ms, zdania o najni s

ż zym priorytecie kwanty o warto c

ś i około 10 ms. r

Ś ednia długość kwantu czasu wynosi 100 ms. Jądro Linuksa promuje zadania o du y ż m

stopniu interaktywno c

ś i. Takie zadania po wykorzystaniu swojego kwantu czasu nie trafiają od razu do tablicy przeterminowanej, ale otrzymują drugą szansę i są umieszczane w tablicy aktywnej, na ko c

ń u tej samej listy, na której były poprzednio (dostają ten sam kwant czasu, co przed wykonaniem). Aby nie doszło do g od ł zenia

procesów jądro wykonuje makrodefinicję EXPIRED_STARVING(), która sprawdza, czy w tablicy przeterminowanej są procesy, które zbyt d u ł go czekają na realizacj .

ę

Proces mo e

ż zostać zawieszony w oczekiwaniu na jakieś zdarzenie, np.: realizację operacji wej c ś ia–wyj c

ś ia lub w oczekiwaniu na sygnał. Taki proces nie mo e

ż

znajdować się w kolejce procesów gotowych do wykonania. Najcz c

ęś iej dochodzi do tego po wywołaniu przez zadanie któregoś z wywołań systemowych, np.: read(), co powoduje jego dodanie do kolejki procesów oczekujących (zdefiniowanej strukturą wait_queue_head_t) i wywołanie funkcji schedule(), celem wyznaczenia innego procesu do wykonania. Budzenie zadań należących do okre l

ś onej kolejki oczekiwania odbywa się za pomocą wywołania wake_up(). Jeśli obudzone zadanie ma wy s ż zy

priorytet niż zadanie bieżąco wykonywane, ustawiane jest pole need_resched.

Wyw a

ł szczenie procesu nast p

ę uje wtedy, kiedy jest ustawiony znacznik need_resched, który ze względu na szybkość dostępu jest przechowywany w strukturze 1

Poza jednym wyj t

ą kiem, który zostanie opisany pó n

ź iej.

1

Systemy Operacyjne – semestr drugi

thread_info zadania. Celem ustalenia nowego procesu do wykonania jądro wywo u ł je funkcję schedule(), która z kolej wykonuje context_switch(). Ta ostatnia dokonuje zmiany kontekstu, wykonując zamianę odwzorowania pami c

ę i wirtualnej (za pomocą wywołania funkcji switch_mm()) oraz zmieniając stan procesora dla nowego zadania (za pomocą wywo a

ł nia funkcji switch_to()) zachowując przy tym stos i warto c

ś i rejestrów dla poprzedniego zadania. Wywłaszczenie procesu u y

ż tkownika może

zajść w ramach powrotu do przestrzeni użytkownika z wywołania systemowego, bądź z procedury obs u ł gi przerwania. Wywłaszczenie j d

ą ra natomiast mo e

ż nast p

ą ić

w ramach powrotu do przestrzeni jądra z procedury obsługi przerwania, kiedy istnieje mo l ż iwość jego wywłaszczenia, kiedy zadanie wykonywane w przestrzeni jądra

jawnie wywoła funkcję schedule() lub kiedy zadanie wykonujące kod jądra ulegnie zablokowaniu.

W systemach wieloprocesorowych zadania są kojarzone z poszczególnymi procesorami, ale czasem mo e ż zajść potrzeba zrównowa en

ż ia pracy systemu, wówczas część

zadań z kolejki procesów gotowych procesora mo e

ż zostać przeniesiona do kolejek innych procesorów lub odwrotnie. Mogą być dwie przyczyny takiego zdarzenia.

Pierwsza zachodzi wtedy, kiedy w kolejce któregoś z procesorów nie ma a

ż dnych zda ,

ń wówczas mogą one być przeniesione z kolejek innych procesorów. Druga to

wywo a

ł nie load_balance() za pomocą przerwania zegarowego. W tym przypadku zadanie równowa en ż ia obcią en

ż ia jest bardziej skomplikowane. W skrócie polega ono

na znalezieniu najbardziej obcią on

ż ej kolejki (ponad 25% obcią en

ż ia wszystkich kolejek w systemie) i rozło en

ż iu tego obciążenia na pozosta e

ł procesory.

Istnieje szereg wywołań dost p

ę nych dla aplikacji u y

ż tkownika, które mogą wp y

ł wać na sposób szeregowania zadań, oto niektóre z nich:

1.

nice() - okre l

ś a poziom uprzejmo c

ś i procesu,

2.

sched_setscheduler() - okre l

ś a strategię szeregowania procesów,

3.

sched_getscheduler() - pobiera strategię szeregowania procesów,

4.

sched_setparam() - ustala parametry szeregowania procesu zgodne ze okre l

ś oną dla niego strategią,

5.

sched_getparam() - pobiera parametry szeregowania procesu jakie okre l

ś a jego strategia szeregowania,

6.

sched_get_priority_max() - pobiera maksymalny priorytet dla okre l

ś onej strategii szeregowania,

7.

sched_get_priority_min() - pobiera minimalny priorytet dla okre l

ś onej strategii szeregowania,

8.

sched_rr_get_interval() - okre l

ś a wartoś

ć kwantu czasu procesu,

9.

sched_setaffinity() - kojarzy proces z procesorem,

10.

sched_getaffinity() - pobiera maskę procesorów, na których zadanie mo e

ż się wykonywa ,

ć

11.

sched_yield() - pozwala procesowi dobrowolnie zrzec się czasu procesora.

Ostatnie wywołanie jest w jądrach serii 2.6 zaimplementowane inaczej niż miało to miejsce w poprzednich wersjach. Dokonuje ono umieszczenia zrzekającego się zdania nie na końcu listy, ale w tablicy przeterminowanej. Z tego wywołania bezpośrednio powinny korzystać procesy użytkownika, natomiast j d ą ro powinno korzystać

z yeild(), które wywołuje sched_yield().

W wersji jądra 2.6.23 planista O(1) został zast p

ą iony planistą CFS (ang. Completely Fair Scheduler), który realizuje strategię sprawiedliwego szeregowania. W tej metodzie czas procesora dzielony jest między u y

ż tkowników i grupy u y

ż tkowników, a nie bezpośrednio między procesy. Je l

ś i w systemie pracuje czterech u y

ż tkowników

i ka d

ż y z nich ma uruchomiony jeden proces, to ka d

ż emu z tych procesów przysługuje 25% czasu procesora. Je l

ś i który

ś z u y

ż tkowników uruchomi dodatkowy proces, to

ka d

ż e z jego zadań otrzyma 12,5% czasu procesora. Sprawiedliwe szeregowanie uwzględnia jeszcze dodatkowo grupy u y ż tkowników. W plani c

ś ie CFS tablice

priorytetów zosta y

ł zastąpione drzewem czerwono-czarnym. Sposób umiejscowienia procesów w tym drzewie decyduje o kolejno c ś i ich uruchamiania. Ponieważ planista

CFS stosuje pomiar czasu z dokładno c

ś ią do nanosekund, to stosowanie heurystyk określających poziom interaktywno c ś i procesów staje się zbędne. Również kwanty

czasu nie są przydatne. Zasada dzia a

ł nia CFS opiera się na za o

ł en

ż iu, e

ż na idealnym procesorze ka d

ż y z procesów miałby przydzielany czas procesora według zasady

opisanej wy ej

ż . W fizycznym procesorze ka d

ż e zadanie oczywi c

ś ie musi czekać na przydział procesora, a czas jego oczekiwania w nanosekundach jest odnotowywany w polu wait_runtime umieszczonym w strukturze typu struct sched_entity wskazywanej przez deskryptor procesu. Wartość tego czasu zwi k ę szana jest w zale n

ż o c

ś i od

liczby procesów w systemie i priorytetu zadania. Kiedy proces otrzyma procesor to ta wartość okre l ś a czas przez jaki to zadanie mo e

ż korzystać z procesora. Nowo c

ś ią

w plani c

ś ie CFS jest to, e

ż z każdą strategią szeregowania skojarzona jest zmienna typu struct sched_class zawierająca głównie wska n ź iki na funkcje związane

z szeregowaniem wedle okre l

ś onej strategii. Pojawi y

ł się dwie nowe strategie, dla „zwyk y

ł ch” procesów: SCHED_BATCH i SCHED_IDLE. Struktura struct prio_array

została zastąpiona strukturą struct cfs_rq. Ze wzgl d

ę u na czas umieszczania zadania w drzewie czerwono-czarnym algorytm CFS ma zło on ż oś

ć obliczeniową wynoszącą

O(log2n), mimo to daje lepsze efekty, je l

ś i chodzi o wybór zadań do uruchomienia niż planista O(1).

W ramce na następnej stronie znajduje się kod modułu tworzącego dwa w t

ą ki. Pierwszy wątek jest realizowany za pomocą funkcji smiple_thread(). W tej funkcji, poprzez wywołanie makrodefinicji DECLARE_WAITQUEUE() tworzony jest wpis (element) kolejki oczekiwania. W przypadku opisywanego modułu tak kolejka nazywa się wq i jest tworzona dynamicznie przez wywołanie funkcji init_waitqueue_head() w funkcji inicjalizującej modu .ł Po wywo a ł niu wspomnianego makra w funkcji

simple_thread() realizowana jest „nieskończona p t

ę la”. W tej p t

ę li wykonywanych jest kilka czynno c

ś i. Najpierw wywo y

ł wana jest funkcja kthread_should_stop(). Je l

ś i

zwróci ona wartość wi k

ę szą od zera, to oznacza to, e

ż wątek powinien zakończyć swoją pracę. W przeciwnym przypadku w t

ą ek wypisuje komunikat przy pomocy

wywo a

ł nia funkcji printk(), dodaje się do kolejki oczekiwania za pomocą wywołania funkcji add_wait_queue() i zmienia swój stan na TASK_INTERRUPTIBLE, wywo u

ł jąc set_current_state(). Nast p

ę nie wywo u

ł je funkcję schedule(). Je l

ś i nastąpi powrót z tej funkcji, to oznacza to e

ż w t

ą ek otrzymał od planisty procesor, wi c

ę

w związku z tym zmienia swój stan na TASK_RUNNING i usuwa się z kolejki oczekiwania za pomocą wywołania funkcji remove_wait_queue(). Drugi w t ą ek

realizowany jest przez funkcję wakeit(). W tej funkcji znajduje się „nieko c ń ząca się pętla” o konstrukcji podobnej do tej z funkcji simple_thread(). W tej p t ę li wątek

sprawdza, czy powinien zakończyć działanie. Jeśli nie to usypia się na okre l ś oną liczbę mikrosekund, a następnie wywołuje funkcję wake_up() dla wątku simple_thread2. Po wykonaniu tych czynno c

ś i wywołuje funkcję schedule(). Oba w t

ą ki są tworzone przez wywołanie w funkcji inicjalizującej moduł funkcji kthread_run (), która zwraca wska n

ź ik na deskryptor utworzonego wątku, a przyjmuje co najmniej trzy parametry: wska n ź ik na funkcję realizuj c

ą ą wątek, wska n

ź ik (typu void *)

na dane dla w t

ą ku oraz ci g

ą znaków w standardzie języka C, który okre l

ś a nazwę wątku. W t

ą ki są zatrzymywane w funkcji „deinicjalizującej” modu ,ł przez wywołanie

funkcji kthread_stop(). Nale y

ż zauwa y

ż ,

ć e

ż w t

ą ki jądra niekoniecznie muszą podlegać wywłaszczaniu (je l

ś i jądro nie zostało skompilowane z odpowiednią opcją

wł c

ą zoną). Stąd bierze się konieczność badania warunku zakończenia ich działania oraz wywołania funkcji schedule(). Dodatkowo funkcje realizujące w t ą ki powinny

mieć zaimplementowaną obs u

ł gę sygna ó

ł w (w poni s

ż zym przyk a

ł dzie jej nie ma). W t

ą ki z przykładowego modułu mogą obcią a

ż ć dosyć znacznie system. Je l

ś i tak się

dzieje, to nale y

ż zmienić liczbę mikrosekund na które usypia wątek wakeit, ale nale y

ż uwa a

ż ,

ć aby nie doprowadzić do zawieszenia systemu.

2

Wła c

ś iwie dla wątku czekaj c

ą ego w kolejce wq, ale ponieważ jedynie wątek simple_thread z niej korzysta, wi c ę rezultat jest ten sam.

2

Systemy Operacyjne – semestr drugi

#include<linux/init.h>

#include<linux/module.h>

#include<linux/kthread.h>

#include<linux/wait.h>

#include<linux/delay.h>

static struct threadst

{

struct task_struct *thread, *thread2;

} ts;

static wait_queue_head_t wq;

static int simple_thread(void *data)

{

DECLARE_WAITQUEUE(wait,current);

for(;;) {

if(kthread_should_stop())

return 0;

printk(KERN_INFO "[simple_thread]: awake\n");

add_wait_queue(&wq,&wait);

set_current_state(TASK_INTERRUPTIBLE);

schedule();

set_current_state(TASK_RUNNING);

remove_wait_queue(&wq,&wait);

}

}

static int wakeit(void *data)

{

for(;;) {

if(kthread_should_stop())

return 0;

udelay(10000);

wake_up(&wq);

schedule();

}

}

static int __init thread_init(void)

{

init_waitqueue_head(&wq);

3

Systemy Operacyjne – semestr drugi

ts.thread = kthread_run(simple_thread,NULL,"simple_thread");

ts.thread2 = kthread_run(wakeit,NULL,"wakeit");

return 0;

}

static void __exit thread_exit(void)

{

kthread_stop(ts.thread2);

kthread_stop(ts.thread);

}

module_init(thread_init);

module_exit(thread_exit);

MODULE_LICENSE("GPL");

MODULE_DESCRIPTION("An example of using the linux kernel threads."); MODULE_AUTHOR("Arkadiusz Chrobot <[e-mail]>");

4