Struktura jader systémů
Linux i FreeBSD používají dvě úrovně privilegovanosti procesoru. Tyto úrovně nazvěme USER a KERNEL mód (Existují i systémy, které používají více úrovní privilegovanosti — například VMS má čtyři: KERNEL, EXECUTIVE, SUPERVISOR a USER. Multics měl dokonce osm úrovní). V USER módu procesor nedovolí vykonávání privilegovaných instrukcí, které by mohly způsobit pád systému, taktéž je v něm omezen přístup do paměti a zpravidla je úplně zakázána komunikace na IO portech. V KERNEL módu naproti tomu přístup není nijak omezen. Z KERNEL módu do USER módu se procesor přepne pomocí speciální instrukce (tato instrukce je privilegovaná — nejde ji tedy provádět v USER módu). Z USER módu do KERNEL módu se procesor přepne buď přes výjimku (vykonání nedovolené instrukce, přístup na nedovolenou adresu), nebo při příchodu přerušení od nějakého zařízení. Při přístupu k paměti používají procesory mechanismus stránkování. Když se v programu vyskytne přístup na nějakou adresu (nazývá se virtuální adresa), je k této adrese v tabulce stránek nalezena odpovídající fyzická adresa, a na tuto fyzickou adresu je pak přistoupeno do paměti. Pokud mapování virtuální na fyzickou adresu není v tabulce nalezeno, vyvolá se výjimka. V tabulce stránek se taktéž nalézají práva přístupu — čili úroveň privilegovanosti, od které je možno na danou adresu přistoupit, a druh přístupu (čtení, zápis, někde i pouštění kódu). Aby se nemusela při každém přístupu do paměti procházet tabulka, má procesor cache na několik posledních mapování. Tato cache se nazývá TLB (translation lookaside buffer). Tabulka stránek má většinou strukturu stromu tabulek o pevné výšce (například procesory IA32 mají dvouúrovňové tabulky, Pentium PRO, Pentium 2 a vyšší je možno přepnout do speciálního režimu, kde jsou tabulky trojúrovňové). Tabulka nejvyšší úrovně se nazývá adresář stránek a ukazuje na ni speciální registr procesoru (instrukce přístupu k tomuto registru jsou privilegované, takže kód běžící v USER módu nemůže s mapováním paměti manipulovat). Některé architektury, jako například Sparc64, nemají vůbec tabulku stránek a mají pouze TLB, která je plněna pomocí speciálních instrukcí.
Linux i FreeBSD byly navrženy tak, že všechny procesy běží v USER módu a celé jádro běží v KERNEL módu. Každý proces má svoji vlastní tabulku stránek, která určuje jeho adresový prostor. Jádro se nachází na virtuálních adresách pro ně rezervovaných (a přístupných pouze z KERNEL módu). Kód i data celého jádra jsou sdíleny mezi všemi procesy a jsou z KERNEL módu vždy přístupné. Taková struktura jádra se nazývá monolitické jádro.
Linux ani FreeBSD nepoužívají segmentaci, pracují v lineárním adresním prostoru. Segmentace (tak, jak je například implementována na procesorech IA32) je velmi těžkopádně použitelná — použití segmentace by znamenalo zvětšení pointerů ze čtyř na šest bytů a s tím související veliké množství práce s pointery a se segmentovými registry. V podstatě žádný 32bitový operační systém na IA32 segmentaci nepoužívá.
Synchronizační mechanismy v jádrech
Přepínání procesů
Nyní se zaměřím na funkci jader na jednoprocesorových systémech — rozšíření pro víceprocesorové systémy bude popsáno v dalším článku.
Každý proces může běžet v USER módu, při obsluze syscallu nebo zpracování výjimky se dostane do KERNEL módu. V USER módu existuje preemptivní multitasking — t.j. k přepnutí procesu dojde kdykoli, kdy to scheduler uzná za vhodné. Naproti tomu při běhu procesu v KERNEL módu se používá kooperativní multitasking — t.j. proces je možno přepnout pouze tehdy, když o to sám požádá nebo když čeká na nějakou událost (například data z disku, ze sítě, stisk klávesy a podobně). Takové čekání na nějakou událost se nazývázablokování procesu. Při zablokování dojde k přepnutí procesu a na procesoru může běžet jiný proces, který není zablokovaný. Existují speciální procesy zvané kernel thready, které nemají vlastní tabulku stránek ani uživatelský adresový prostor a běží po celou dobu v jádře. Kernel thready se používají k vykonávání nějakých činností na pozadí, které nesouvisejí s žádným uživatelským procesem (například zapisování modifikovaných bufferů na disk nebo swapování). V Linuxu se možné přepnutí procesu v jádře dělá funkcí void cond_resched() nebo schedule(), na FreeBSD funkcí void mi_switch(). Výhodou kooperativního multitaskingu je, že zjednodušuje návrh jádra, nevýhodou jsou občasné pomalejší reakce systému. Při běžném provozu se to téměř nepozná, ale realtimové aplikace vyžadující garantované probuzení a spuštění procesu do určitého času na Linuxu ani FreeBSD běžet nemohou. V Linuxu byla snaha tento problém řešit a byly použity dvě metody:
- Byla snaha nalézt v jádře všechny déletrvající cykly a do nich bylo vloženo podmíněné přepnutí procesu pomocí
cond_resched. Toto řešení se nazývá low-latency patch. Patch je možno stáhnout pro jádra 2.2 a 2.4, v 2.6 nemá význam. - Druhou metodou je preemptivní kernel — čili možnost libovolného přepínání procesů i při běhu v jádře. Značně to souvisí s implementací podpory pro víceprocesorové systémy, a proto způsob implementace popíšu až v následujícím článku. Preemtivní kernel je možno zapnout při kompilaci jádra 2.6.
Přerušení
Různá zařízení generují přerušení. Přerušení se obsluhují při běhu v USER i KERNEL módu. Po skončení obsluhy přerušení se řízení vrací na místo, kde přerušení nastalo. Často se stává, že přerušení způsobí probuzení nějakého procesu — pokud takové přerušení nastalo v USER módu, nový proces se spustí okamžitě po skončení obsluhy přerušení. Pokud nastalo v KERNEL módu, proces se přepne při nejbližším přechodu do USER módu nebo při zavolání výše popsané funkce pro kooperativní schedulování.
Obsluha přerušení s sebou přináší problém: přerušení mohou chodit současně, nebo může jedno přerušení přijít v průběhu jiného. Některá přerušení mohou trvat déle. Existují zařízení, která potřebují přerušení obsloužit rychle, jinak dochází k chybám nebo degradaci výkonu (jedná se zejména o méně kvalitní zařízení: zvuková karta s malými buffery, nedostane-li včas data, začne vydávat praskavé zvuky; síťová karta, jejíž přerušení není dostatečně rychle obslouženo, začne ztrácet packety; bude-li přerušení od disku příliš dlouho čekat, poklesne přenosová rychlost disku). Kvalitnější zařízení na latenci přerušení moc závislá nejsou: kvalitní zvukové karty mají velikou vyrovnávací paměť, kvalitní síťové karty mají velikou paměť pro odchozí i příchozí packety, kvalitní SCSI disky mají tagovanou frontu a jsou schopny přijmout a vykonávat několik požadavků současně bez jakékoli účasti procesoru.
Pro jakýkoli kód, který je volán z obsluhy přerušení, platí omezení: kód nesmí provést zablokování (ani volat jakoukoli funkci, která by zablokování mohla provést). Vzhledem k tomu, že obslužná rutina přerušení běží na zásobníku nějakého procesu, který zrovna běžel, když se přerušení vyskytlo, a který s tímto přerušením vůbec nesouvisí, nemělo by blokování tohoto procesu žádný smysl. Nyní popíšu způsoby, jakými oba systémy přerušení zpracovávají:
Linux zpracovává přerušení následovně: když se vyskytne přerušení, je na řadiči zamaskováno, pak se povolí všechna přerušení na procesoru a vykoná se obslužná rutina přerušení. Obslužná rutina tedy může být přerušena jinými přerušeními. Ovladač může při registraci přerušení vynutit, aby při volání obslužné rutiny tohoto přerušení byla přerušení na procesoru zamaskovaná. Registrace přerušení se provádí funkcí
int request_irq(unsigned int irq, void (*handler)(int, void *, struct pt_regs *), unsigned long irqflags, const char *devname, void *dev_id)
Pokud ovladač zařízení pracuje se strukturami, které mohou být přerušením modifikované, musí toto přerušení zakázat. Linux vynucuje v takovém případě zakázání všech přerušení (zakázání jednoho přerušení na řadiči je moc pomalé a softwarové maskování daného přerušení Linux neumí). Přerušení je možno zakázat pomocí maker local_irq_disable() a local_irq_enable(). Makro local_save_flags(x) uloží aktuální stav zakázání/povolení do proměnné x, která musí být typu unsigned long. Makro local_irq_restore(x) tento stav zase obnoví. Poslední dvě makra se používají ve funkcích, které potřebují zakázat přerušení, ale není jasné, jestli už přerušení nejsou zakázána. Přerušení jsou zakázána a povolována pouze na tom procesoru, na kterém kód právě běží. Pokud jsou přerušení zamaskována, proces se v Linuxu nesmí zablokovat.
Časté zakazování všech přerušení a nemožnost selektivního zakázání několika přerušení je problém Linuxu. Na Linuxu se přerušení zakazují, v podstatě kdykoli je potřeba provádět nějakou operaci se strukturami, které mohou být nějakým přerušením modifikovány. Bohužel se zakazují například i při psaní na konzoli (neboť kód z přerušení může na konzoli zapisovat), posílání požadavků na IDE disk a spoustě jiných příležitostí. To vede k veliké latenci přerušení a důsledek je například takový, že se ztrácejí packety na paralelní lince nebo chrochtá zvuková karta, pokud uživatel například přepne konzoli.
Ve FreeBSD 4 je problém přerušení řešen lépe. FreeBSD téměř nikdy nezakazuje přerušení na procesoru, ale používá softwarové maskování jednotlivých přerušení. Přerušení je registrováno pomocí funkce int bus_setup_intr(device_t dev, struct resource *r, int flags, driver_intr_t handler, void *arg, void **cookiep) (předtím muselo být ještě alokováno pomocí bus_alloc_resource). Třetí parametr jsou příznaky, které určují, kdy bude přerušení zamaskováno: INTR_TYPE_BIO (přerušení bude maskováno při operacích s diskovými buffery), INTR_TYPE_CAM (přerušení bude maskováno při operacích se SCSI zařízeními), INTR_TYPE_NET (maskování při operacích se sítí), INTR_TYPE_TTY (maskování při operacích s terminálem nebo jinými znakovými zařízeními), INTR_TYPE_MISC (žádné maskování), INTR_TYPE_FAST (rychlá obsluha přerušení — při vyvolání přerušení se neprovádí maskování na řadiči, které je pomalé. Nicméně za běhu obslužné rutiny pak nemohou být zpracovávána jiná přerušení).
Mechanismus obsluhy přerušení funguje následovně: Systém má proměnné cpl a ipending. cpl obsahuje bitovou masku zamaskovaných přerušení. ipending obsahuje bitovou masku přerušení, která se vyskytla, ale nemohla být provedena, protože byla zamaskována. Při výskytu přerušení systém zamaskuje přerušení na řadiči. Pak zkontroluje, zda přerušení není zamaskováno příslušným bitem v cpl. Pokud není, vykoná se obslužná rutina. Pokud je, nastaví se příslušný bit v ipending a ihned se vrátí.
Kód jádra může maskovat přerušení pomocí funkcí unsigned splXXX(). Funkce vrátí předchozí masku a novou masku omezí. XXX je třeba nahradit příslušným omezením — například splbio() zamaskuje všechna přerušení typu INTR_TYPE_BIO,
splnet() zamaskuje všechna přerušení typu INTR_TYPE_NET a podobně. void splx(unsigned x) vrátí masku na původní hodnotu ( x je hodnota, kterou vrátila příslušná funkce splXXX) a zkontroluje, zda některé nově odmaskované přerušení není nastaveno v proměnné ipending. Pokud ano, je obslužná rutina tohoto přerušení ihned zavolána. Ve FreeBSD se proces může zablokovat i se zamaskovanými přerušeními, nicméně po dobu zablokování procesu toto maskování neplatí. Při odblokování je obnovena maska přerušení, jaká byla ve stavu zablokování.
Systém maskování přerušení ve FreeBSD je lepší než v Linuxu — kód jádra maskuje pouze skupinu přerušení, která by mohla modifikovat struktury, k nimž přistupuje, nikoli všechna přerušení tak, jak je tomu na Linuxu. To přispívá k tomu, že FreeBSD má menší latenci přerušení a umí lépe komunikovat se zařízeními, která potřebují okamžitou obsluhu.
V experimentálním FreeBSD 5 byl tento systém maskování přerušení odstraněn (Tohle odstranění bylo dle mého názoru provedeno dost nešťastným způsobem — funkce spl byly prostě nahrazeny prázdnými funkcemi (viz soubor sys/systm.h) — to nejspíš povede k velkému množství race-conditions v ovladačích). Ve FreeBSD 5 jsou přerušení zpracovávána přes interrupt thready — každé přerušení dostane kernel thread a při jeho výskytu se na tento kernel thread přepne (tohle vyvrací obecný princip o nepřepínání procesů uvnitř jádra). Interrupt thready mají i priority, což určuje priority jednotlivých přerušení. Interrupt thready se taktéž mohou zablokovat. Na druhou stranu, přepínání threadů je jistě pomalejší než přímé zavolání obslužné rutiny na zásobníku procesu, kde se vyskytla. FreeBSD 5 má i fast interrupty, které nemají kernel thread a jejichž obslužná rutina se volá přímo. Fast interrupty se maskují na procesoru, zamaskováním všech přerušení.
Pro úplnost zde ještě popíšu systém přerušení, jaký používají Windows NT (a nejspíš i 2000 a XP). Procesor má proměnnou IRQL — ta určuje, jaká přerušení se mohou zpracovávat. Při registraci přerušení ovladač určí, na jaké IRQL toto přerušení bude běžet. Když se vyskytne přerušení, zjistí se, zda je IRQL přerušení větší než aktuální IRQL, na kterém daný procesor běží. Pokud ano, IRQL procesoru se zvětší, provede se obslužná rutina přerušení, a pak se IRQL zase zmenší na původní hodnotu. Pokud ne, obslužná rutina se odloží. Až bude IRQL procesoru sníženo, provedou se obslužné rutiny odložených přerušení s vyšší hodnotou IRQL. Maskování a odmaskování přerušení se provádí zvýšením a snížením IRQL na příslušnou hodnotu. Přerušení, která jsou krátká a potřebují být obsloužena v krátkém časovém intervalu, mají vysoká IRQL; přerušení, která trvají dlouho a na jejichž latenci tolik nezáleží, mají nízká IRQL.
Mechanismus maskování přerušení na NT je lepší než na FreeBSD 4. NT při maskování určitého přerušení maskují i všechna pomalejší přerušení. Naproti tomu FreeBSD 4 maskuje pouze přerušení (nebo skupinu přerušení), které zamaskovat má. Představme si, že máme pomalé přerušení od disku, jehož obsluha trvá dlouho, a rychlé přerušení od zvukové karty, které musí být obslouženo okamžitě, jinak karta začne vydávat praskavé zvuky. Na FreeBSD 4 například může nastat situace: zamaskujeme přerušení od zvukové karty, přijde přerušení od disku, bude se vykonávat obslužná rutina přerušení od disku, přijde přerušení od zvukové karty, to však musí čekat, než skončí dlouhé přerušení od disku, a je obslouženo pozdě. Na NT tahle situace nastat nemůže, neboť při zvednutí IRQL na vysokou hodnotu, kterou má přerušení od zvukové karty, se zamaskují i všechna přerušení s nízkým IRQL. Mechanismus IRQL může garantovat určitou dobu odezvy pro realtimová zařízení.
Softwarové přerušení
Softwarová přerušení fungují podobně jako hardwarová — s jediným rozdílem. Přerušení není vyvoláno hardwarovou událostí, ale samotným jádrem systému. Typickým použitím softwarových přerušení je zpracovávání síťových packetů — hardwarové přerušení přijme packet ze síťové karty. Kdyby zpracovávání packetu bylo prováděno rovnou v obsluze tohoto hardwarového přerušení, tak by po dobu zpracovávání bylo přerušení zamaskované. Zpracování packetu však může trvat dlouho a během této doby by nebylo možno přijímat další packety.
Proto je síťový subsystém dělán následovně — hardwarové přerušení přijme packet, uloží ho do fronty, vyvolá softwarové přerušení síťového stacku a skončí. Packet je dále zpracováván v softwarovém přerušení. Během obsluhy softwarového přerušení mohou přicházet další hardwarová přerušení a mohou být přijímány další packety.
Linux ve verzi 2.2 a nižší volal obsluhy softwarových přerušení po ukončení hardwarového přerušení. Ve verzi Linuxu 2.4 a 2.6 jsou softwarová přerušení obsluhována speciálním kernel threadem ksoftirqd. Nalezneme ho v souboru kernel/softirq.c. Ve víceprocesorovém systému běží několik těchto threadů — pro každý procesor jeden. U softwarových přerušení je třeba zajistit, aby nezahltila celý systém a nedošlo k zatuhnutí (například, když ze sítě chodí packety rychleji, než trvá jejich zpracování). V Linuxu 2.2 se to řešilo tak, že pokud bylo vyvoláno softwarové přerušení v době jeho vykonávání, systém obsluhu nového přerušení nevyvolal okamžitě, ale odložil ji až do dalšího hardwarového přerušení. V Linuxu 2.4 je ochrana proti zahlcení jednoduchá — kernel thread má v sobě funkci pro podmíněné schedulování.
Na FreeBSD 4 jsou softwarová přerušení zpracovávána stejně jako hardwarová (pomocí masek cpl a ipending). Na FreeBSD 5 jsou softwarová přerušení zpracovávána pomocí kernel threadů — opět stejně jako hardwarová přerušení.
Čekací fronty
Pokud chce proces čekat na nějakou událost, používá k tomu čekací fronty. V Linuxu čekací fronty nalezneme v souboru include/linux/wait.h. Čekací fronta je typu wait_queue_head_t. Když chce proces čekat na nějakou událost, zařadí se do příslušné fronty pomocí funkce void sleep_on(wait_queue_head_t *queue). Po zavolání této funkce se proces zablokuje. Funkce void wake_up(wait_queue_head_t *queue) probudí všechny procesy, které na dané frontě čekají. Při čekání je též možno použít funkce void sleep_on_interruptible(wait_queue_head_t *queue), která zajistí, že proces bude probuzen nejen funkcí wake_up, ale také příchodem signálu. Funkci wake_up je možno volat z kontextu přerušení; funkci sleep_on pochopitelně ne, protože způsobuje zablokování.
Používání funkce sleep_on je ve většině případů nevhodné. Pokud kód vypadá jako if (nenastala_podmínka) sleep_on(čekací_fronta_na_podmínku), nastane problém v případě, kdy ona podmínka (podmínkami, na které se čeká ve frontách, jsou například natažení bloku dat z disku, stisk klávesy na terminálu, příchod dat na socket ze sítě, odswapování paměti a spousta dalších) nastane po if, ale před sleep_on. Pak bude proces čekat věčně ve frontě, ačkoli podmínka, na kterou čeká, je splněna. Aby se tomuto nežádoucímu tuhnutí zabránilo, proces se nejdřív umístí na frontu pomocí add_wait_queue, pak nastaví svůj stav na neběžící proces, pak otestuje platnost podmínky, a pokud podmínka neplatí, proces zavolá schedule. Tento způsob čekání je korektní; pokud podmínka začala platit po jejím otestování, funkce wake_up prošla všechny procesy na frontě a nastavila jejich stav na běžící, takže následující schedule proces neuspí. Vidět to můžeme například v souboru linux/fs/inode.c ve funkci __wait_on_inode.
Ve FreeBSD se k čekání používá funkce tsleep a k probuzení wakeup. Jejich funkce je stejná jako linuxové sleep_on( _interruptible) a wake_up. FreeBSD má i funkce asleep, která přidá proces do fronty, ale nechá ho běžet, a await, která čeká na událost registrovanou dříve pomocí asleep. Použití je zcela analogické jako na Linuxu — nejdřív zavolat asleep, pak otestovat podmínku a pak zavolat await, aby nedocházelo k nekonečnému čekání, pokud podmínka nastane rovnou po jejím otestování.
Nicméně implementace těchto funkcí je velmi mizerná — nevytváří se žádná fronta procesů jako na Linuxu a funkce
wakeup prochází všechny procesy v systému, aby zjistila, který na danou událost čeká. Procházení všech procesů je celkem náročná operace a v tomto případě je to zcela zbytečné. Docela se divím, že to tak mohl nějaký programátor vůbec napsat. Ve FreeBSD 5 byla konečně napsána lepší implementace pomocí struktury struct cv a operací cv_wait, cv_wait_sig (čekání přerušitelné signálem), cv_signal (vzbudí jednoho) a
cv_broadcast (vzbudí všechny). Tato implementace je ekvivalentní linuxovým wait queue. Bohužel se zatím používá pouze na několika málo místech — ve většině jádra je zatím neefektivní tsleep/ asleep/ wakeup.
Zamykání
Zamykání slouží k zajištění, aby se do kritické sekce nedostal více než jeden proces současně (pokud se tam nemají dostat ani obsluhy přerušení, je třeba kromě zamykání používat i maskování přerušení z předchozí kapitoly). Funkce na zamykání mohou způsobit zablokování procesu, a proto je není možno volat z obsluhy přerušení (výjimkou je FreeBSD 5 se svými interrupt thready).
Na Linuxu se k zamykání používají obyčejné semafory. Nalezneme je v souboru include/asm/semaphore.h. Na struct semaphore je možno provádět operace up a down. Existuje ještě operace down_interruptible, kdy čekání může být přerušeno signálem. Tyto funkce používají čekací fronty popsané v předchozí kapitole.
Na FreeBSD je implementace zámků výrazně komplikovanější. Zámek je popsán objemnou strukturou struct lock v souboru sys_lock.h. Na zámku se provádějí operace pomocí funkce int lockmgr(struct lock *lock, unsigned int flags, struct simplelock *spinlock, struct proc *process). Lockmgr umožňuje dělat zamykání pro čtení i zápis a má i podporu pro rekurzivní zámky (mohou být tímtéž procesem zamčeny několikrát).
Implementace zámků ve FreeBSD poskytuje více možností než na Linuxu, ale není to výhoda. Zatímco na Linuxu má operace zamčení i odemčení dvě instrukce procesoru (na IA32), na FreeBSD se kvůli tomu volá celá komplikovaná funkce lockmgr, která z parametrů testuje, o jakou operaci se vlastně jedná, jaké má příznaky, zda daný proces zámek skutečně drží a kolikrát ho drží. Taková funkce je velmi pomalá. Kdyby měla být několikrát volána například při každém syscallu read pro zamykání a odemykání souboru a inody, bylo by to znát. Výsledek je ten, že se v jádře FreeBSD lockmgr příliš nepoužívá (používá se jen na místech, kde nejde o rychlost) a většina kódu si zamykání dělá sama, pomocí čekacích front. Taková komplikovaná implementace zámků má i další nevýhodu— umožňuje to lidem psát nečistý kód. Pokud někdo při navrhování nějakého subsystému potřebuje rekurzivní zamykání téhož zámku, svědčí to o tom, že kód a data špatně navrhl a měl by místo používání komplikovaných zámků svůj návrh zjednodušit.
Ve FreeBSD 5 existují i rychlé funkce mtx_lock a mtx_unlock, které jsou podobné jako linuxové funkce up a down.
