Porovnání systémů Linux a FreeBSD (5)

Oprava k předchozímu článku — nejnovější FreeBSD 4.9 již také má PAE a je schopno adresovat více než 4G paměti. Nicméně velké množství ovladačů toto nepodporuje. Pokud se v ovladači počítá adresa pro DMA pomocí vtophys, pak ovladač není schopen pracovat s více než 4G paměti. Pokud se k výpočtu adresy používá funkce bus_dmamap_load, pak ovladač s PAE funguje.

Scheduler

Scheduler je plánovač procesů — rozhoduje, který proces na kterém procesoru poběží. Na přepínání procesů jsou kladeny požadavky, do určité míry protichůdné:

• Nesmí docházet k příliš častému přepínání procesů. Přepnutí procesu je poměrně náročná operace, která nějakou dobu trvá, proto je nežádoucí, aby procesor trávil mnoho času přepínáním procesů místo vykonávání užitečného kódu.
• Nesmí docházet k málo častému přepínání procesů, pak by uživatel získal dojem, že systém reaguje pomalu.
• Pokud nějaký proces čeká na diskové I/O, klávesu na terminálu, data ze sítě nebo jinou událost, musí být probuzen a spuštěn okamžitě, jakmile tato událost nastane. Kdyby například proces četl data z disku a byl spouštěn pozdě, vedlo by to ke značnému poklesu přenosové rychlosti disku.
• Na víceprocesorových systémech je žádoucí, aby proces nestřídal procesory a běžel pokud možno pouze na jednom procesoru. Každý procesor má svoji vlastní cache. Pokud je proces přehozen na jiný procesor, budou jeho data přelévána z cache původního procesoru do cache nového procesoru. Toto přelévání po sběrnici je velmi pomalé.
• Uživatel musí mít možnost nastavit prioritu procesu. U určitých procesů (typicky se jedná o nějaké dlouhodobé výpočty) je požadováno, aby běžely jen, když žádný jiný proces nepožaduje procesor.

Každý proces se může nacházet v několika stavech:

• Proces je zablokován, pokud čeká na nějakou událost. Proces čeká na nějaké čekací frontě, semaforu nebo jiném synchronizačním primitivu. Takový proces není možno spustit. Zablokování máme dvojího druhu: přerušitelné signálem (procesy v tomto stavu jsou označeny písmenem „ S” ve výpisech z příkazů ps nebo top) a nepřerušitelné signálem (jsou označeny písmenem „ D”). Pokud proces dostane signál a je v přerušitelném čekání, aktuální syscall se zruší, proces se vrátí do userspace a provede se obsluha signálu. Pokud to bylo při registraci signálu požadováno (příznak SA_RESTART), pak po skončení obsluhy signálu libc zavolá znovu přerušený syscall. Nepřerušitelné zablokování se používá například při operacích s diskem. Při nich máme zaručeno, že operace skončí v krátkém čase, takže proces nebude příliš dlouho zablokován. Nepřerušitelné zablokování výrazně zjednodušuje implementaci filesystému. Přerušitelné zablokování se používá, pokud čekání může trvat hodně dlouho — při čtení z terminálu a při operacích s pipami a sockety. Scheduler mezi těmito dvěma způsoby zablokování nerozlišuje.
• Proces je připraven, pokud je možno jej spustit, ale neběží (neboť běží jiný proces). Do připraveného stavu se dostane buď tak, že běží a je preemptivně přepnut, nebo pokud byl zablokován, probuzen, ale ještě nespuštěn.
• Proces je ve stavu běžící, pokud je jeho kód právě na procesoru vykonáván. Pokud proces běží, může se buď zablokovat, nebo může být preemptivně přepnut, čímž se dostane do stavu připraven.

Scheduler na Linuxu 2.4 a nižších

Algoritmus plánování procesů na Linuxu je stejný již od první verze 0.01 až po současnou 2.4­. Každý proces je popsán velikou strukturou task_struct. Položka state této struktury určuje stav procesu — může nabývat hodnot TASK_INTERRUPTIBLE (přerušitelné zablokování),

TASK_UNINTERRUPTIBLE (nepřerušitelné zablokování) a TASK_RUNNING (proces je připraven nebo běží). Existují dva obousměrně linkované seznamy procesů — seznam všech procesů (položky next_task a prev_task) a seznam procesů ve stavu TASK_RUNNING (položky next_run  a

prev_run). Pro účely scheduleru má task_struct položky nice a counter. nice je priorita, kterou uživatel nastavil pomocí systémového příkazu nice. V příkazu nice se nastavuje číslo v rozsahu -20 (nejvyšší priorita) až 19 (nejnižší priorita); pro potřeby scheduleru je toto přepočítáno na rozsah 1 (nejnižší priorita) až 40 (nejvyšší priorita). counter je počet tiků, které procesu ještě zbývají. Při vzniku procesu se  nice

zkopíruje do counter.

Jádro scheduleru se nachází ve funkci void schedule(void). Tato funkce odstaví aktuální proces ze seznamu připravených procesů, pokud jeho stav není TASK_RUNNING. Pak vybere ze seznamu připravených procesů proces s největší hodnotou counter a ten spustí. Při běhu procesu se counter zmenšuje o jedničku při každém tiku. Proces běží, dokud counter nedosáhne nuly nebo dokud se sám nezablokuje. Pak se opět zavolá schedule a ta vybere další proces. Pokud funkce schedule zjistí, že všechny připravené procesy mají counter roven nule, provede pro všechny (připravené i zablokované) procesy operaci counter = counter / 2 + nice. Pro připravené procesy tato operace pouze přiřadí

nice do counter, pro zablokované procesy způsobí, že counter bude pomalu růst až k hodnotě 2 * nice. Tím je zajištěno, že proces, který je delší dobu zablokovaný, bude mít vyšší prioritu než všechny běžící procesy a po probuzení bude spuštěn okamžitě. Na starších jádrech byla hodnota nice používána rovnou (což znamenalo, že při tiku 100Hz dostal proces s implicitní prioritou časové kvantum 200ms), v novějších 2.4 je lineárně přepočítávána tak, aby proces s implicitní prioritou měl přibližně 50ms časové kvantum. Ač je tento algoritmus velmi jednoduchý, splňuje většinu požadavků na scheduler kladených: pokud běží několik procesů, střídají se a dostávají časová kvanta úměrná jejich prioritě. Pokud je nějaký proces delší dobu zablokován, naroste mu counter na větší hodnotu než všem ostatním procesům, je po probuzení spuštěn okamžitě a má až dvakrát větší časové kvantum. Pokud je proces zablokován jen na velmi krátkou dobu,

counter mu příliš nenaroste.

Horší je to už s víceprocesorovými systémy. Byla snaha zabránit přehazování procesů mezi procesory tak, že při výběru procesu s největším counter je k této hodnotě přičteno 5, pokud proces běžel naposledy na procesoru, na kterém se schedulování provádí. Rovněž je přičteno 1, pokud proces má stejnou virtuální paměť jako proces, který na procesoru právě běžel — neboli pokud se jedná o thready. Přepínání mezi thready je méně náročné než přepínání mezi procesy. Toto nám zajišťuje, že pokud budeme mít dvouprocesorový systém a na něm nám poběží sudé množství procesů, bude mít každý proces svůj procesor a procesy nebudou mezi procesory přehazovány. Nicméně pokud nám na dvouprocesorovém systému poběží tři procesy, tak k cyklickému přehazování jednoho nebo všech procesů mezi procesory dojde. Optimální strategie v takovém případě by byla nechat na jednom procesoru běžet dva procesy, na druhém procesoru jeden proces a přehození procesu provádět pouze za dlouhou dobu, aby všechny procesy dostaly stejné procento výpočetní síly.

Další nevýhodou tohoto scheduleru je jeho značná časová složitost. Každé přepnutí procesu má složitost lineární vzhledem k počtu připravených procesů. To není ještě tak zlé — připravených procesů je v systému jen pár; systém s více než dvaceti připravenými procesy je stejně nepoužitelný (neboť tam každý proces dostane pouze dvacetinu výpočetního času), takže uživatelé tak velké zátěže na systém nedávají. Nicméně pokud všem dojde counter na 0, musí se projít všechny procesy v systému, a to je značně náročná operace, neboť procesů může být až několik stovek. Složitost jednoho přepnutí procesu je tedy O(počet připravených procesů + počet všech procesů / počet připravených procesů).

Linux má realtimové procesy. Pokud v systému existuje nějaký připravený realtimový proces, je spuštěn přednostně před všemi ostatními procesy. K nastavení realtimové priority procesu je potřeba právo superuživatele, neboť tyto procesy jsou poměrně nebezpečné; pokud se v realtimovém procesu vyskytne nekonečná smyčka, celý systém zatuhne. Realtimové procesy mají uživatelsky nastavené priority, spuštěn je vždy realtimový proces s nejvyšší prioritou, pokud má více realtimových procesů stejnou prioritu, cyklicky se mezi nimi přepíná. Realtimové procesy nejsou realtimové v pravém slova smyslu — je sice garantováno, že realtimový proces bude spuštěn před všemi ostatními procesy, nicméně doba spuštění garantována není. Pokud například nějaký nerealtimový proces stráví příliš mnoho času v jádře, aniž by se zablokoval nebo zavolal funkci podmíněného přepnutí cond_resched, tak realtimový proces spuštěn být nemůže. K vylepšení doby odezvy je třeba použít low-latency patch nebo preemptivní přepínání procesů uvnitř jádra.

Scheduler na Linuxu 2.5 a 2.6

V experimentálním Linuxu 2.5 byl scheduler zcela přepsán, aby měl složitost O(1) a aby lépe fungoval na SMP. Scheduler pracuje zvlášť na každém procesoru a má frontu zvlášť pro každý procesor. Každý proces má proměnnou sleep_avg, která se zvětšuje o 1 každý tik, kdy proces spí, a zmenšuje se o 1 každý tik, kdy proces běží. Má určitou maximální velikost, kterou nesmí překročit. Efektivní priorita procesu je určena jako statická priorita nastavená uživatelem +/- bonus, kde bonus je sleep_avg lineárně zobrazený do intervalu –5 – +5. Připravené a běžící procesy jsou uloženy ve frontách příslušejících jejich efektivním prioritám. K frontám existuje bitová maska neprázdných front, aby se mohla snadno najít neprázdná fronta s nejvyšší prioritou. Pro každou prioritu existují dvě fronty: aktivní a záložní. Každý proces dostane time_slice, což je uživatelem nastavená priorita lineárně zobrazená do intervalu 10ms – 300ms. Systém vybere z aktivních front proces s nejvyšší efektivní prioritou a pustí ho. Proces běží a ubírá svůj time_slice. Až time_slice dojde, proces je přeřazen z aktivní fronty do záložní fronty příslušející jeho prioritě. Pak je vybrán další proces s nejvyšší prioritou z aktivních front. Když už v aktivních frontách žádné procesy nejsou, tak se záložní a aktivní fronty vymění a provede se znovu výběr procesu.

Pokud je úloha interaktivní (což je rozhodnuto lineárně na základě sleep_avg a uživatelské priority), je při ztrátě time_slice opět vložena do aktivní fronty. V takovém případě by mohlo docházet k hladovění procesů v záložní frontě— pokud k tomu dojde (což se pozná tak, že proces v záložní frontě s nejvyšší prioritou neběžel po určitou dobu), tak se interaktivní procesy budou dávat do záložní fronty jako obyčejné procesy.

Aby scheduler dobře fungoval na SMP, celý tento mechanismus funguje zvlášť na každém procesoru. Jednou za 250ms, nebo pokud je nějaký procesor volný, je prováděn load-ballancing, při kterém se systém snaží vyrovnat velikost front. Procesor, na kterém se load-ballancing provádí, najde nejvytíženější procesor. Pokud je tento procesor vytížen více jak na 4/3 zátěže procesoru provádějícího load-ballancing, je mu nějaký proces odebrán.

Tento scheduler je určitě výrazně lepší než ve starších verzích Linuxu: všechny operace zde mají složitost O(1); procházení seznamu všech procesů nebo seznamu všech připravených procesů se zde nedělá nikde. Rovněž je zajištěna dobrá funkce na SMP, neboť procesy nejsou svévolně přehazovány mezi procesory. Procesy jsou přehazovány jen při operaci load-ballancingu.

Scheduler na FreeBSD 4 a nižších

Scheduler na FreeBSD funguje následovně — máme 32 front příslušejících prioritám. Scheduler vybírá procesy z fronty s nejvyšší prioritou a mezi nimi cyklicky přepíná. Každý proces běží 100ms. Každý proces má proměnnou p_estcpu. Tato proměnná roste lineárně, když proces běží, a klesá exponenciálně, když proces neběží. Rychlost klesání je ovlivněna systémovou zátěží (load average, vypsáno příkazem uptime). Za 5* load_average sekund p_estcpu klesne na 10%. Skutečná priorita je určena lineárně z uživatelské priority a p_estcpu. Scheduler jednou za sekundu prochází všechny procesy a snižuje p_estcpu, čímž zvyšuje prioritu neběžícím procesům. Tím je zajištěno, že procesy nehladoví. Pokud proces čeká na nějakou událost pomocí funkce tsleep nebo asleep, může v parametru funkce určit, s jakou prioritou bude probuzen. Scheduler přepíná procesy se složitostí O(1), ovšem jednou za sekundu prochází všechny procesy.

Scheduler na starších FreeBSD 4 na SMP obsahoval naprosto neuvěřitelný bug, který způsobil, že pokud jsou všechny procesory obsazeny, mají interaktivní procesy až několikasekundovou odezvu. V sočasném FreeBSD 4.9 už naštěstí není.

Kernel schedulable entities na FreeBSD 5

Na FreeBSD 5 byl scheduler zcela přepsán, aby lépe umožňoval použití threadů. Nebyl změněn jen algoritmus, ale i význam datových struktur.

Existují dvě základní metody, jak implementovat thready:

• Kernel thready — thready přepínané v jádře. Jádro se ke threadům chová stejně jako k samostatným procesům, které mají společnou virtuální paměť, a přepíná je. Takto jsou thready implementovány na Linuxu a na starších FreeBSD.
• User thready — jádro vidí jeden proces, přepínání mezi thready provádí samotná threadová knihovna běžící v userspace. Takto funguje FreeBSD 4 nebo dnes již zapomenutá knihovna NSPR na Linuxu, kterou používal Netscape.

User thready mají nevýhodu, že pokud se jeden thread dostane do nepřerušitelného zablokování, žádné další thready nemohou běžet, protože nemůže být doručen časovací signál knihovně, která thready přepíná. Implementace přerušení přerušitelného čekání je značně problematická. Navíc user thready nemohou efektivně využívat víceprocesorový stroj, neboť pro jádro se celý mnohothreadový program jeví jako jeden proces, který je spuštěn na jednom procesoru.

Naproti tomu kernel thready mají tu nevýhodu, že pokud thready čekají na sebe navzájem, musí se přitom provádět volání jádra, což se při user threadech nemusí. User thready také narozdíl od kernel threadů nekonzumují žádné zdroje jádra.

Na FreeBSD byla snaha napsat hybridní thready, které by měly výhody jak kernel, tak user threadů. Idea je taková, že se thready budou chovat jako thready userspacové, ale pokud se nějaký thread zablokuje v jádře, bude vyrobena nová struktura popisující kontext jádra a ostatní thready procesu poběží s touto novou strukturou, zatímco stará struktura zůstane zablokovaná v jádře. Proto byl zcela změněn význam některých struktur jádra a přibyly struktury nové. struct proc popisuje proces stejně jako v předchozích verzích. Nicméně tato struktura již neobsahuje informace pro scheduler a neobsahuje kontext jádra (t.j. zásobník jádra a příznaky související se zablokováním a odblokováním). Kontext jádra byl přesunut do struktury struct thread. Proces má několik struktur struct kse (kernel schedulable entity) — pro každý procesor jednu. Ty se z hlediska schedulování chovají jako samostatné procesy. Každá tato struktura má jednu struct thread obsahující kontext jádra. Pokud se tento kontext zablokuje někde v jádře, je alokována nová struct thread, ta se vrátí do userspacu ve speciálním upcallu a s ní daná KSE dále poběží (upcall provede výběr dalšího připraveného threadu a jeho spuštění). KSE jsou sdruženy v  struct ksegrp, která obsahuje obecné informace pro scheduler, jako například p_estcpu. Uvnitř jednotlivých KSE pak běží samotné userspacové thready, přepínané schedulerem v userspace. To zajistí výhody rychlého přepínání mezi user thready bez vzniku problémů s blokováním threadů v jádře a s víceprocesorovými stroji.

Výhoda tohoto modelu je v tom, že uživatel má možnost pouštět velké množství threadů, aniž by tím zatěžoval paměť jádra, a že když thready na sebe budou navzájem čekat, bude jejich probouzení výrazně rychlejší. Pokud je pouštěno velké množství threadů, které budou zablokovány v jádře (například u serveru thready čekající na socketech, posílající nebo čtoucí data od klientů), tak tenhle threadový model oproti ryzím kernel threadům žádné zrychlení nepřinese — thready budou stejně potřebovat kontext jádra (a s ním struct thread), a protože na sebe thready nebudou čekat, tak se výhody threadů v userspace neprojeví.

Pro přepínání procesů umožňuje FreeBSD 5 použít dva algoritmy — původní scheduler z předchozích verzí BSD nebo nový ULE scheduler, který je velmi podobný scheduleru z Linuxu 2.6 (je možno mezi nimi přepnout pomocí options SCHED_4BSD a options SCHED_ULE při kompilaci jádra). ULE scheduler má rovněž fronty pro jednotlivé priority, dvě skupiny front, jednu, ze které se vybírá, a druhou, do které se ukládají procesy, jimž vypršel time slice. Má určování „interaktivních” procesů a jejich ukládání do aktivní fronty. Podobně jako na Linuxu provádí load-ballancing mezi procesory.