Hlavní navigace

Přidělování procesoru procesům a vláknům v Linuxu

Michal Filka

Článek se zabývá problematikou plánování procesů a vláken procesů. Konkrétním cílem je popsat strategie, kterými se plánovač může řídit při přidělování procesoru procesu. Účelem článku je představit principy dostupné pro plánování procesů, konkrétní implementace některého z plánovačů je mimo rámec článku.

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_SYS­TEM) nebo v rozsahu procesu (PTHREAD_SCOPE_PRO­CESS).

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_setsched­param) 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_SYS­TEM). Volání pthread_setsched­param je mapováno přímo na sched_setsched­param. 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/~gre­gor/docs/pthre­ad-scheduling.html

[2] http://linuxpro­grams.wordpres­s.com/2007/12­/19/linux-kernel-support-for-threads-light-weight-processe/

[3] manualové stránky

[4] http://onlamp­.com/pub/a/on­lamp/2002/11/07­/linux_thread­s.html

[5] http://en.wiki­pedia.org/wiki/Na­tive_POSIX_Thre­ad_Library

[6] http://www.drdob­bs.com/open-source/18440620­4;jsessionid=4IT1QPQT­TRQNVQE1GHPSKHWAT­MY32JVN
Našli jste v článku chybu?

30. 6. 2010 10:51

ondra.novacisko.cz (neregistrovaný)

U rt61pci se projevuje ještě tato chyba:
 
http://www.google.cz/search?q=garbage+in+essid
 
Provozovat se tedy dá jen pomocí network-manageru, který to obchází, ovšem network-manager na servery není zrovna určen.





30. 6. 2010 10:45

ondra.novacisko.cz (neregistrovaný)

> je v pripade otvorenych ovladacoch aspon teoreticka sanca, ze ich raz niekto opravi
 
Ta šance je vskutku jen teoretická. Sám to dělat nebudu a nikdo na to nemá čas, řvát na bugreportu mohu do nekonečna, efekt nulový
 
> Btw. k tomu ralinku wireless, nie je to nahodou v staging vetve jadra? :D
 
rt61pci.ko – je součástí instalace ubuntu, netuším v jaké úrovni, nezkoumal jsem to. Je mizerný, umí jen základní veci a nedá se provozovat na kanálech 12–13.
 
rt61.ko – byl do nedávna alt…






DigiZone.cz: SES zajistí HD pro M7 Group

SES zajistí HD pro M7 Group

DigiZone.cz: V Plzni odstartovalo Radio 1

V Plzni odstartovalo Radio 1

Měšec.cz: Exekuční poradna: ptejte se online

Exekuční poradna: ptejte se online

Lupa.cz: Levný tarif pro Brno nebude, je to kartel

Levný tarif pro Brno nebude, je to kartel

DigiZone.cz: R2B2 a Hybrid uzavřely partnerství

R2B2 a Hybrid uzavřely partnerství

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

DigiZone.cz: Sat novinky: slovenská TV8 HD i ruský NTV Mir

Sat novinky: slovenská TV8 HD i ruský NTV Mir

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Vitalia.cz: Test na HIV je zdarma i za pět set

Test na HIV je zdarma i za pět set

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Podnikatel.cz: E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

DigiZone.cz: Ohrozí Freedom TV přechodové sítě?

Ohrozí Freedom TV přechodové sítě?