Rozvrhování procesů – Linux
Základní plánovač Linuxu používá pro plánování procesů čtyři strategie. Jedná se o strategie SCHED_OTHER, SCHED_BATCH, SCHED_FIFO a SCHED_RR. Poslední dvě jmenované strategie jsou označovány jako realtimové. Zmíněné strategie jsou konfigurovatelné per proces, a to buď pomocí nástroje schedtool a nebo přímo v rámci procesu voláním sched_setscheduler. Nastavení strategie SCHED_FIFO nebo SCHED_RR vyžaduje práva roota.
Základní metrika, se kterou plánovač pracuje, je priorita procesu. Hlavní priorita, se kterou plánovač pracuje vždy, je tzv. statická priorita s rozsahem 0 až 99. Vždy platí, že k běhu je vybrán proces s nejvyšší statickou prioritou. V případě, kdy je k běhu připraveno více procesů se stejnou statickou prioritou, rozhoduje plánovač na základě některé z dále uvedených strategií.
1) strategie SCHED_OTHER
Tato strategie pracuje s konceptem časového kvanta. Tj. procesor je po nějakou dobu přidělen vybranému procesu. Po uplynutí dané doby je procesor přidělen (obecně) jinému procesu. Procesy, pro které se použije tato strategie, mají vždy statickou prioritu rovnou 0.
Při použití této strategie se Linux snaží přidělovat procesor maximálně spravedlivě. Což znamená, že se snaží aby všechny spuštěné procesy měly dostatek prostředků k dokončení své práce. Plánovač tedy zohledňuje nakolik efektivně proces využívá přidělené časové kvantum a na základě toho procesu mění dynamickou prioritu (hodnota nice), kterou používá jako sekundární kritérium při volbě procesu. Dynamická priorita se pohybuje v rozsahu –20 až 19 (na některých systémech 20) – platí, že čím nižší číslo tím vyšší priorita. Je možné ji nastavit voláním nice popř. setpriority, přičemž běžný uživatel může hodnotu nice pouze zvýšit (znevýhodnit proces).
2) strategie SCHED_FIFO
Tato strategie může být použita pouze pro procesy se statickou prioritou vyšší než 0.
Při použití této strategie je procesor vždy přidělen takovému procesu připravenému k běhu, který má nejvyšší statickou prioritu. Proces má procesor přidělen tak dlouho dokud neskončí, dokud není připraven proces s vyšší statickou prioritou nebo dokud se proces sám nevzdá dalšího běhu voláním sched_yield.
Při nevhodné konfiguraci nebo při chybě v procesu (např. nekonečné zacyklení, zablokování atd.) může vést až k zablokování systému.
3) strategie SCHED_RR
Tato strategie je obdobou SCHED_FIFO. Způsob práce je podobný s tím rozdílem, že procesům je přidělováno časové kvantum a o procesor se tak střídají všechny procesy se stejnou statickou prioritou.
4) strategie SCHED_BATCH
Jedná se o strategii vhodnou pro typicky dlouhodobě běžící neinteraktivní procesy. Strategie pracuje podobně jako SCHED_OTHER s tím rozdílem, že plánovač považuje tento proces za velmi vytěžující a mírně ho penalizuje. Procesy využívající tuto strategii musí mít statickou prioritu rovnou 0. Procesům s touto strategií není snižována nice hodnota.
Rozvrhování vláken – teorie
Proces je program, který je nahrán do paměti počítače, a který je vykonáván instrukci za instrukcí počínaje nějakým definovaným vstupním bodem. V některých případech se může hodit mít možnost vykonávat více částí programu současně. Vykonávaná část programu se označuje jako vlákno. Proces tedy může být jedno nebo více vláknový. V případě více vláknového procesu je zde opět problém jak zvolit vlákno, kterému bude v daném okamžiku přidělen procesor.
S problematikou vícevláknového procesu souvisí i způsob implementace vláken. Vlákna mohou být implementována buď plně v uživatelském prostoru, např. jako součást nějaké knihovny. Tato implementace má ale nevýhodu na víceprocesorových systémech – v daný okamžik může běžet jen jedno vlákno jednoho procesu (operační systém vidí jen procesy, ne jednotlivá vlákna). Navíc pokud se některé vlákno zablokuje na nějakém IO volání je zbytek přiděleného času procesu odebrán (zbývající vlákna procesu ho nemohou využít). Výhodou naopak je typicky rychlejší přepínání vláken. Druhou možností je implementace vláken s podporou kernelu – tj. přímé mapování uživatelských vláken na úkoly kernelu (kernel task). Obecně je možné mapování M:N. Tento typ implementace odbourává dříve zmíněné nevýhody. Cenou je o něco větší režie při přepínání vláken způsobená přepínáním mezi kernelem a uživatelským prostorem.
Při rozvrhování vláken přichází do úvahy teoreticky dvě strategie. Vlákna mohou být rozvrhována v rozsahu celého systému (PTHREAD_SCOPE_SYSTEM) nebo v rozsahu procesu (PTHREAD_SCOPE_PROCESS).
1) Rozvrhování v rozsahu systému
Tento způsob rozvrhování neznamená nic jiného než že operační systém vidí jednotlivá vlákna (tj. všechna vlákna všech procesů) a přiděluje jim časové kvantum (timeslice) podle používané politiky. V tomto případě je možné proces chápat jen jako označení skupiny vláken, které ale z pohledu rozvrhování nemá žádný vliv.
2) Rozvrhování v rozsahu procesu
V tomto režimu operační systém nerozlišuje jednotlivá vlákna. Všechna vlákna procesu jsou spojena do jedné množiny, té je pak přidělováno časové kvantum jako celku. Přidělené kvantum se následně dělí v závislosti na nastavené prioritě vláken (pthread_setschedparam) a rozvrhovací strategii, která se použije pro výběr vlákna procesu. K dispozici jsou typicky dvě rozvrhovací strategie – SCHED_FIFO a SCHED_RR. Naplánováno je vždy vlákno s nejvyšší prioritou, které je spustitelné. Vlákno zůstane naplánované dokud není k dispozici vlákno s vyšší prioritou (SCHED_FIFO i SCHED_RR), případně neomezeně dlouho dokud je schopné běhu (SCHED_FIFO) nebo dokud nevyčerpá přidělené časové kvantum (SCHED_RR).
Rozvrhování vláken – Linux
Poznámka: V následujících odstavcích jsou zmínky o výkonnosti jednotlivých implementací vláken. Tato výkonnost byla měřena jako čas potřebný na vytvoření a zrušení vlákna v závislosti na počtu vláken v systému.
V Linuxu jsou nejznámější tři implementace vláken. Nejstarší jsou tzv. LinuxThreads. V době, ze které pochází tato implementace (tj. před uvedením kernelu 2.6) neobsahoval kernel Linuxu žádnou podporu pro uživatelská vlákna – pracoval pouze s procesy. Tato implementace vláken má problémy s výkonností, rozšiřitelností (klesající výkonnost v závislosti na počtu vytvořených vláken), zpracováním signálů i kompatibilitou s POSIX standardem (pouze částečná kompatibilita).
Tato implementace využívá light-weight procesy a mapuje na ně uživatelská vlákna 1:1. Implementace používá syscall clone. Jedná se o syscall podobný syscallu fork. Liší se tím, že volání fork vytváří vlastní kopii dat pro potomka (metodou copy-on-write). Volání clone umožňuje provést vytvoření potomka tak, že data jsou sdílena s rodičovským procesem – což je očekávaná vlastnost u implementace vláken. Z použitého způsobui mapování vláken už je patrné, že jediná možnost pro rozvrhování vláken je rozvrhování v rámci systému (PTHREAD_SCOPE_SYSTEM). Volání pthread_setschedparam je mapováno přímo na sched_setschedparam. Vlákna jsou tedy rozvrhována podle jedné ze strategií zmíněných v odstavci „Plánování procesů – Linux“.
Implementace vláken s označením NGPT (New Generation POSIX Threads) z dílny IBM problémy s kompatibilitou odstranila a je přibližně dvakrát výkonnější než předchozí implementace. Tato implementace je založena na mapování M:1. Implementace je značně komplikovaná. Mmj. zahrnuje dva plánovače (pro procesy a pro vlákna v rámci procesu). Tato implementace byla v době svého uvedení přibližně dvakrát výkonnější než předchozí implementace. Změny v kernelu nutné pro tuto implementaci byly akceptovány do kernelu 2.5.4 a následně backportovány do 2.4.19. V současnosti (cca od roku 2003) již nicméně není tato implementace dále rozvíjena.
Poslední implementací je implementace NPTL (Native POSIX Thread Library). Tato implementace se opět vrací k mapování 1:1. Díky tomu odstraňuje nutnost použití dvou plánovačů. Implementace používá podobné techniky jako LinuxThreads (použití syscallu clone). Díky změnám v kernelu – např. přepracování syscallu clone, zavedení mapy alokovaných pid, O(1) plánovače, futexů a dalším – odstraňuje i výkonnostní problémy původní implementace LinuxThreads. Navíc je plně kompatibilní s normou POSIX. Tato implementace byla v době svého uvedení cca dvakrát výkonnější než NGPT. Uvedena byla přibližně ve stejné době jako NGPT – tj. v letech 2002/2003. Je součástí kernelu 2.6 a je plně integrována se současnou GNU C Library.
Závěr
Jak je vidět, implementace vláken v Linuxu prodělala složitý vývoj. Od jednoduché implementace v podobě LinuxThreads postoupila ke komplexní implementaci NGPT, aby se následně – díky prosazení změn v jádře – vrátila k původnímu jednoduchému konceptu v podobě implementace NPTL. Výsledkem tohoto koloběhu je cca čtyřnásobné zrychlení implementace i odstranění nekompatibilit s POSIX normou.
Linux používá pro implementaci vláken podporu kernelu. Díky tomu nehrozí, že by si některé vlákno uzurpovalo procesor jen pro svou potřebu jako v případě některých implementací v uživatelském prostoru. Navíc současná implementace vláken v Linuxu je natolik výkonná, že hlavní výhoda uživatelské implementace vláken – rychlé přepínání – je zanedbatelná.
Zdroje
[1] http://www2.net.in.tum.de/~gregor/docs/pthread-scheduling.html
[4] http://onlamp.com/pub/a/onlamp/2002/11/07/linux_threads.html
[5] http://en.wikipedia.org/wiki/Native_POSIX_Thread_Library
ČLÁNKY DO MAILU