Kernel Scheduler Entities - Scheduler Activations

28.07.2002 14:02 | blackhole

Během několika dní vyjde druhé Developers Preview FreeBSD 5.0 a za několik týdnů ho bude následovat NetBSD 1.6. Oba tyto operační systémy implementují zajímavý přístup k problematice threadů. OpenBSD (afaik!) takové zbytečnosti jako je kvalitní podpora SMP, threading a UBC nepodporuje.

Unix je velmi starý operační systém. Jeho principy (inode-based FS, vse monolitické, nepreemptivnost apod.) byly vymýšleny v době, kdy bylo hlavním úkolem nahradit dávkové zpracování interaktivním, proto nemá přirozenou podporu pro moderní způsoby computingu.

Thready
V unixu (tradičním) je jen jeden typ procesu. Ten bývá obvykle popsán v něčem jako je \"struct proc\", kde jsou veškeré informace o procesu - paměť, práva, otevřené soubory, příbuzné procesy apod. Nad touto strukturou se poté
vykonávají známe procedury fork a exec. Postupem času se ovšem přišlo na to, že je docela výhodné jeden program rozdělit na několik tzv. threadů, které poběží \"zárověň\". Programátor může například chtít, aby program četl data ze socketu, zpracovával je a zároveň bavil uživatele vypisováním nějakých statistik. Není to sice moc unixové, ale co.

Z principu se dá říct, že existují dva možné přístupy k řešení tohoto problému. Buďto použijete user-space thready, nebo kernel-space thready. Bohužel ani jedno toto řešení není ideální. (porovnejte např. Solaris a Linux!)

User-space thready
Pokud se rozhodnete řešit problematiku threadů v user-space budete čelit několika poměrně závažným problémům. V situaci kdy jeden thread aplikace stojí (např. zavolal blokující syscall, nebo čeká na mutex apod.) stojí vlastně i ostatní thready, protože kernel nemá potuchy o tom, že uvnitř procesu je více threadů. A i kdyby to věděl stejně s tím nic neudělá, protože proces je monoliticky popsán jen jednou strukturou. V reálu se to řešilo nahrazováním blokujících volání jádra neblokujícími variantami a následným voláním user-space scheduleru. Ale rozhodně to nebylo ideální. Další problém byla nemožnost běhu jednotlivých threadů na více procesorech. Kernel prostě viděl jeden proces a tak se podle choval. Toto řešení je použito např. v BSD.

Kernel-space thready
Evidentním řešením všech výše popsaných problémů je použít pro každý thread jeden \"skoro-proces\". Prostě použít normální \"struct proc\" a do položky \"*vm_space\" u všech threadů zapsat tu samou adresu. Takhle to řeší mimojiné Linux, IRIX a Windows NT. Zdálo by se to ideální až na jeden problém. Přepínání procesů je extrémně pomalé. Musí se zneplatnit caches, TLB, context procesu se musí zavést, potom veškeré načítání. Je to o několik řádů pomalejší (az 10 tisíckrát) než user-space přepínání, kde zjednodušeně rečeno stačí přepsat pár registrů. (btw: proto se ted implementují do 2.5 linuxu tzv. futexy - tj. user-space mutexy - jsou rychlé)

KSE - SA
Jak už to tak v demokracii bývá ( :-) ) nejlepším řešením bývá kompromis. Chytří výzkumnící vykoumali jak tyto dva přístupy zkombinovat. Vytvoří se virtuální procesory (representované v podstatě něčím jako onou strukturou proc), které bude schedulovat kernel (tj. pomalu ale \"kvalitně\") a uvnitř těchto virtuálních procesorů bude pracova user-space scheduler, který zabezpečí rychlé přepínání threadů. Tyto virtuální procesory se nazývají KSE.

Na začátku tedy aplikace (voláním funkcí threadové knihovny) určí kolik virt. procesorů chce mít a který thread bude kde. Poté vše běží jako normálně. Co se ale stane pokud se thread zablokuje? Pokud je to použitím nekernelové
události (čekání na mutex) pak vše obslouží us-scheduler a je to ok. Ale když se zavolá blokující syscall? V tom případě se okamžitě vrátí řízení virtuálnímu procesoru (což je vlastně proces) za pomoci tzv. upcallu. Ten uvědomí
us-scheduler který thread a proč je blokován a schedulne další thread. Thread jež je blokován mezitím běží asynchroně na svém původním virtuálním procesoru. Při návratu se preemptne právě běžící thread a znova se zavolá upcall. Ten
dostane informace o tom který thread je blokován/odblokován a sdělí to us-scheduleru. Vlastně se dá říct, že všechy \"servisní\" služby jsou obsluhovány upcallem (pridani virt. procesoru, migrace threadu apod).

Implementace v NetBSD
Pro zavedení těchto, pro unix, revolučních změn si vyžádala rozdělení struktury proc na dvě části - process context a execution context. Execution context byl pojmenován LWP (light-weight process) a obsahuje informace vztahující se k stavu běhu procesu - informace scheduleru, priority, kernel stack a \"execution context\" (část paměti a registry). Process context obsahuje informace o celém procesu. Takto rozsáhlé změny zasáhly celé jádro a obzvláště scheduler (+fork a exit) musel být silně modifikován. Také část kernelu zajišťující obsluhu signálůdoznala jistých změn.

Benchmarks
Viděl jsem několik čísel popisujících KSE implementaci v NetBSD. V některých syscallech byl rychlejší systém s KSE v některých bez. To ovšem neznamená, že by implementace byla neužitečná! Test byl totiž proveden bez použití threadů. Šlo o to demonstrovat, že takovéto zesložitění nepovede k citelnému snížení výkonu při běžných (bez threadů na UP) operací. Při jednoduchém testu threadů se ukázalo, že dramaticky poklesla doba nutná k vytvoření threadu, obsluha mutexu, stejně jako context switch nyní zabere více času (o cca 30%) - to je ovšem daň za možnost běhu threadů na více procesorech současně a za lepší interaktivnost. Podotýkam, že čísla jsou vztažena vůči čistému user-space schedulingu. Linux vykazuje při vytváření threadů a obsluze mutexů daleko nižší výkon (což je pochopitelné), naopak je překvapující jak rychlé má context switche. Nicméně implementace je teprve na začátku a dost neoptimalizovaná. Časem se jistě o hodně zlepší.

Závěr
Spojení kvalitní implementace UBC (jakou NetBSD bezpochyby má), zero-copy (což se chystá) a KSE (zároveň s fine-grained SMP) umožňuje systému obejít tradiční omezení unixu a dosáhnout nových met ve výkonnosti. Systémy tak kvalitní jako BSD si to určitě zaslouží.neologism