Real-time modifikace Linuxu - 2 (Realtime preempt, aplikace)

3. 2. 2006 | Vít Pelčák | Systém | 5950×

Analýza vlivů několika variant preemptivního jádra na časové odezvy procesů reálného času. Srovnání hard real-time linuxových modifikací (RTLinux, RTAI). Praktická aplikace.

Obsah

První díl

1. ÚVOD
  1.1 Co je to Linux
  1.2 Probírané linuxové real-time modifikace
    1.2.1 RTLinux
    1.2.2 RTAI/fusion
    1.2.3 Realtime preempt patch
2. RTLINUX
  2.1 Úvod
  2.2 POSIX
    2.2.1 Základní pojmy
    2.2.2 Plánování
    2.2.3 Posixio
    2.2.4 Signály
  2.3 Shrnutí
3. RTAI
  3.1 Úvod
    3.1.1 Úvod do RTAI/fusion
  3.2 Časovače a přerušení
  3.3 Základní koncepty
  3.4 Software
  3.5 Podporované architektury

Druhý díl

4. REALTIME PREEMPT MODIFIKACE JÁDRA
  4.1 Souběžnost v jednoprocesorovém jádře
    4.1.1 Kritické úseky a jejich správa
  4.2 Souběžnost na SMP jádře a správa kritických úseků
    4.2.1 Ochrana před jinými vlákny
  4.3 Analýza prodlev preemptivního jádra
    4.3.1 Prodlevy přerušení
    4.3.2 Prodlevy závislé na úlohách
    4.3.3 Shrnutí
  4.4 Plně preemptivní real-time jádro
    4.4.1 Vylepšení real-time zpracování úloh
    4.4.2 Nezávislost kritických úseků
    4.4.3 Nahrazování Spinlocku
    4.4.4 Shrnutí
    4.4.5 Vlastnosti Real-Time jádra
  4.5 Real-time mutex
    4.5.1 Dědičnost priorit
  4.6 Benchmarky
    4.6.1 Interbench
  4.7 Shrnutí
5. APLIKACE
  5.1 Embedded systémy a jiné aplikace pro řízení
  5.2 Multimediální aplikace - JACK
6. ZÁVĚR

4. REALTIME PREEMPT MODIFIKACE JÁDRA

V nových jádrech řady 2.6 se objevilo mnoho vylepšení reagujících na požadavky embedded systémů, včetně nového plánovače a preemptivního jádra.

Od jader této řady se toho, na základě pokroků v technologii plánování, očekávalo hodně.

Nový plánovač sice dosahoval dobrých výkonů, ale odezva byla trvale znehodnocována prodlevami, když úlohy přistupovaly ke sdíleným systémovým datům uvnitř kritického úseku.

Počáteční měření ukázala, že jádra řady 2.6 v preemptivním výkonu zaostávala za řadou 2.4. Taky ve zpracování audia překonávala jádra 2.4 některé rané verze 2.6.

4.1 Souběžnost v jednoprocesorovém jádře

4.1.1 Kritické úseky a jejich správa

Během operací prováděných jádrem jsou sdílená data, porty a jiné hardwarové registry předmětem současného přístupu mnoha vlákny a rutinami obsluhujícími přerušení.

Kritický úsek je část chráněného kódu, se kterým může operovat pouze jedna úloha, aby se zajistila integrita sdílených dat. Každý proces běžící v kritickém úseku musí tento opustit. Teprve pak je povolen přístup jinému procesu.

Souběžné přístupy do sdílených objektů jsou seřazovány podle hranic kritických úseků, a tak je za všech okolností zajištěna stabilita sdílených dat a operací s hardwarovými registry.

V jádře existují dva základní typy kritických úseků:

1. Kritické úseky chránící vlákna před současnými přístupy jinými vlákny (preempt disable).
2. Kritické úseky chránící vlákna před současnými přístupy přerušeními (interrupt disable).

První a nejjednodušší druh kritického úseku potlačuje přepínání úloh pokud vlákno provádí operace uvnitř kritického úseku. Tato vlastnost zajišťuje, že vlákno může tento úsek opustit před tím, než je povolen přístup jinému vláknu.

Před tím, než vlákno přistoupí k datům sdíleným s rutinou obsluhující přerušení, jsou přerušení vypnuta a znovu jsou zapnuta až po dokončení aktualizace těchto dat. To chrání data před souběžným přístupem rutinou obsluhující přerušení poté, co vykonávající vlákno vstoupilo do kritického úseku.

Pro základní správu kritických úseků v jednoprocesorovém prostředí jsou mechanismy preempt disable a interrupt disable postačující.

V jednoprocesorovém prostředí na CPU vykonává operace pouze jedno vlákno, a to tak dlouho, dokud neopustí CPU samo, nebo je k tomu donuceno výjimkou procesoru jako třeba přerušením.

4.2 Souběžnost na SMP jádře a správa kritických úseků

Správa souběžnosti na SMP (symetric multiprocessing) jádře je výrazně komplexnější záležitost než je tomu u jednoprocesorového jádra, protože pouhé vypnutí preemptivity a přerušení už na ochranu dat sdílených procesory nestačí. To proto, že úlohy běžící na jiných procesorech nebudou vědět, jestli jsou tyto volby na CPU vypnuty, a mohou tak vstoupit do stejného kritického úseku zároveň. Z tohoto důvodu je nutné fyzicky alokovat sdílené zámky, které řídí přístup k jednotlivým kritickým úsekům. Tyto zámky, které chrání přístup do kritických úseků, se nazývají spinlock. Jsou alokovány v paměti a identifikují kritické úseky asociované se specifickými sdílenými daty. Tato architektura odděluje uzamykání pro nezávislá data. To dovoluje, aby mnoho vláken najednou mohlo pracovat v mnoha kritických úsecích jádra.

Když úloha získá spinlock, je jí umožněn vstup do kritického úseku a je také zabráněno přepínání úloh v procesoru, dokud neproběhne spin unlock. Během držení spinlocku mohou být vypnuta přerušení (Gerum, P.).

4.2.1 Ochrana před jinými vlákny

Ochrana před vlákny a přerušeními je, až na několik rozdílů, obdobná jako u jednoprocesorové implementace.

Pokud vlákno v jádře SMP systému narazí na spinlock, vyvstane situace, kdy bude úloha usilovat o uzamčení a přístup do kritického úseku, který již bude blokován jinou úlohou. Vlákno usilující o přístup bude aktivně čekat (točit se na místě - spin) na uvolnění uzamčení (lock). Odtud plyne anglický název "spinlock".

Pokud tedy bude vlákno na daném CPU aktivně čekat, nebude to CPU provádět žádnou práci.

SMP implementace má vztah k plně preemptivnímu real-time jádru, protože jakýkoliv SMP kód je v principu plně preemptivní.

4.3 Analýza prodlev preemptivního jádra

Prodlevy preemptivity linuxového jádra řady 2.6 jsou složeny ze dvou hlavních prvků:

1. Prodlevy způsobené zpracováním přerušení.
2. Prodlevy způsobené zpracováním kritických úseků.

4.3.1 Prodlevy přerušení

Zpracováním přerušení může být vlákno pozdrženo tak dlouho, dokud se tato operace nedokončí. Také procesy se po tuto dobu nemohou přepínat.

Prodlevy způsobené zpracováním přerušení mají 3 podskupiny:

1. Úseky s vypnutým přerušením. Tyto mají na prodlevu jen minimální vliv.
2. Přednost zpracování přerušení před úlohami. To má velký vliv na prodlevu přepínání procesů obzvláště pokud dojde k velkému I/O zatížení.
3. softIRQ^* zpracování také velmi ovlivňuje prodlevu preemptivity. Zvláště softIRQ zpracování vztahující se k sítím je specifický zdroj výrazného zatížení preemptivní prodlevy.

* Rutina obsluhující přerušení by měla být vykonána co nejrychleji a zároveň musí vykonat mnoho práce. Kvůli tomu se zpracování přerušení dělí na dvě části, tzv. poloviny. Samotná rutina obsluhující přerušení tvoří horní polovinu. Ta se spustí hned po přijetí přerušení a představuje jenom práci, která je časově kritická, jako je např. poslání potvrzení o přijetí přerušení nebo reset hardware. To, co se může vykonat později, je zahrnuto v dolní polovině. Ta proběhne později, když jsou všechna přerušení povolena.

4.3.2 Prodlevy závislé na úlohách

• Linuxové jádro během operace v kritickém úseku vypíná preemptivitu. Proto může být úloha s vysokou prioritou blokována jakoukoliv úlohou s nižší prioritou, která pracuje v kritickém úseku, a musí čekat dokud tato úloha daný kritický úsek neopustí.
• V SMP jádře může aktivita přerušení prodloužit čas potřebný k získání spinlocku. Přerušení prodlužují dobu, po kterou vlákno drží spinlock, a tak brání jeho předání jinému vláknu.
• Swapování může způsobit obrácení priorit, protože procesy s vysokou prioritou mohou být swapováním blokovány.
• Na jednoprocesorovém jádře je uzamčení jakéhokoliv kritického úseku ekvivalentní uzamčení všech úseků (Gerum, P.).

4.3.3 Shrnutí

V linuxovém jádře je přes 10000 nezávislých kritických úseků. Jejich identifikace je časově náročná a vyžaduje důkladné testování a analýzu.

Omezování nejdelších kritických úseků je náchylné na chyby.

Podstatné zvýšení výkonu zpracování přerušení týkající se prodlevy preemptivity není dost dobře možné.

Je nerozumné optimalizovat nepreemptivní kritické úseky jeden po druhém pro zlepšení preemptivity úloh.

Pro výrazné zvýšení preemptivního výkonu linuxového jádra je potřeba prozkoumat původní principy návrhu, jelikož se týkají zpracování přerušení a správy kritických úseků.

4.4 Plně preemptivní real-time jádro

U přerušovacího real-time subsystému je požadováno, aby vykonávání přerušení bylo upřednostnitelné (preemptible), aby dodržovalo priority, aby tyto priority přerušení byly alokovatelné na úlohové úrovni (tasklevel) v prostoru priorit a musí být možné povýšit prioritu real-time úloh nad zpracování přerušení.

4.4.1 Vylepšení real-time zpracování úloh

Nepředvídatelná zpoždění způsobená zpracováním přerušení jsou vyřešena přesunutím zpracování přerušení do kontextu k tomu vyhrazených úloh. Těmto úlohám lze pak přiřadit libovolné priority.

Pouhým přesunutím softIRQ přerušovací aktivity a hardIRQ zpracování signálů do prostoru úloh (task space) nemůže být dosaženo žádných velkých zlepšení prodlev preemptivity na úlohové úrovni (tasklevel). K tomu je nutné snížit celkovou velikost a počet nepreemptivních kritických úseků.

Principy návrhu plně preemptivního real-time linuxového jádra jsou založeny na rozšíření konceptů zpracování a zamykání, které již byly použity u SMP jádra (Gerum, P.).

4.4.2 Nezávislost kritických úseků

Kritické úseky jsou označeny unikátními jmény, a tak mohou v SMP za jistých podmínek CPU souběžně používat různé nezávislé kritické úseky. Tyto úseky mohou být chráněny alternativním uzamykacím mechanismem známým pod jménem mutex. To zajistí integritu dat a zároveň rozšíří spinlock operace v některých klíčových aspektech:

1. Pokud se narazí na uzamčený úsek, úlohy jsou pozastaveny a zařazeny do fronty v pořadí podle své priority. Po odemčení úseku jsou úlohy opět aktivovány.
2. Po obdržení mutex jádro asociuje uzamčený kritický úsek s úlohou uložením identity úlohy do zámku.
3. Kritické úseky mohou být ochráněny bez vypnutí upřednostňování (preemption).
4. Na úlohy operující v kritických úsecích je možno aplikovat dědičnost priorit.

4.4.3 Nahrazování Spinlocku

Pokud úlohy operují mimo kritické úseky, je linuxové jádro řady 2.6 už preemptivní. Nahrazení nepreemptivních spinlocků mutexy dovolí upřednostňování úloh uvnitř kritických úseků s real-time charakteristikami:

• Vlastnictví vláknem je v real-time jádře asociováno s každým uzamčeným mutexem.
• RT mutex poskytuje detekci zablokování a dědičnost priorit.
• O všech zámcích se předpokládá, že jsou preemptivní, včetně zámků deklarovaných v kódu ovladačů. To vylučuje možnost neefektivní implementace uzamykání, která může do systému zavést nedetekovanou prodlevu upřednostnění (preemptivity).
• Pouze malá kontrolovatelná množina zámků zůstane nepreemptivní.

4.4.4 Shrnutí

Odkládání zpracování přerušení do prostoru úloh a náhrada nepreemptivní implementace spinlocku mutexem více zatěžují CPU, ale to je cena za přizpůsobení preemptivního plánování úloh a přeměnu univerzálního linuxového jádra ve vysoce preemptivní, protože plánovač zde může dát přednost kterémukoliv vláknu, i když se toto nachází přímo v kritickém úseku.

4.4.5 Vlastnosti Real-Time jádra

Návrh plně preemptivního linuxového jádra je založen na funkčním rozšíření nepreemptivních uzamykacích vlastností SMP jádra. Následně uvedený datový typ RT-Mutex poskytuje základ kompletní preemptivity, dědičnost priorit a detekci blokování.

Robustností implementace SMP v linuxovém jádře, které již garantuje časovou nezávislost a správný chod v prostředí souběžných operací, se výrazně zjednodušuje real-time problém.

Real-time mutex

Real-time mutex na jednoprocesorovém jádře umožňuje běh mnoha vláken v mnoha různých kritických úsecích.

4.5.1 Dědičnost priorit

Aby byla zredukována zpoždění způsobená aplikacím s vysokou prioritou, které se pokoušejí přistupovat ke kritickým úsekům a které již byly uzamčeny úlohou s nižší prioritou, byl původní real-time mutex vylepšen o dědění priorit.

Dědičnost priorit zvyšuje prioritu úlohy, která byla během práce v kritickém úseku předběhnuta na nejvyšší úroveň ze všech úloh čekajících na přístup do téhož kritického úseku.

Tranzitivní dědičnost priorit dovoluje vláknu s nejvyšší prioritou uplatnit prioritu přes více úrovní závislostí kritických úseků.

4.6 Benchmarky

Realtime preempt - patch vytvořený Ingo Molnarem nabízí 4 úrovně preemptivity:

1. No Forced Preempt - využívá pouze základní preemptivní linuxový model (toto je vhodné pro servery, kde není tolik třeba rychlá odezva ale především vysoká propustnost).
2. Voluntary Preemption - zde bylo přidáno několik explicitních preemptivních bodů. To redukuje prodlevu za cenu mírně nižšího výkonu.
3. Low-Latency - jádro je, kromě kódu pracujícího v kritickém úseku, plně preemptivní (vhodné pro desktop s rychlou odezvou).
4. Real-Time - od předchozí varianty se liší tím, že díky využití mutexu je preemptivní i kód provádějící operace v kritickém úseku. Je to na výkon nejnáročnější varianta a je zaměřena na Real-Time systémy.

Pro testování byla zkompilována 4 jádra verze 2.6.14. Pro každou úroveň preemptivity jedno. Tato jádra byla zkompilována ze stejnými parametry vyjma již zmíněné úrovně preemptivity.

4.6.1 Interbench

Na testování prodlev byl použit pro tento účel vyvinutý program Interbench (volně ke stažení na http://members.optusnet.com.au/ckolivas/interbench/), který simuluje různé druhy zátěže v reálném čase a měří prodlevu při jejich vykonávání. Testování bylo provedeno v runlevelu 1, kdy běžely pouze nutné procesy, a počítač tak nebyl zatěžován dalšími úlohami, jež by znehodnocovaly výsledky testů.

Pro testování v režimu reálného času byl program spuštěn s parametrem -r. Během této sady testů se prováděl i Hack test, který byl ale natolik náročný, že způsobil pád programu. Aby se tento test neprováděl, byl vypnut parametrem -x Hack. Výsledný příkaz, kterým byl program spuštěn, tedy byl ./intebench -r -x Hack.

Typy zátěží simulované programem interbench:

Write:

Opakovaný streamovaný zápis souboru o velikosti fyzické paměti nadisk.

Read:

Opakované čtení souboru o velikosti fyzické paměti z disku.

Compile:

Simulace náročné kompilace na čtyřprocesorovém počítači prováděním testu Read, Write a zatížením CPU souběžně.

Memload:

Simulace velkého zatížení paměti a swapu opakovaným přístupem ke 110 % fyzické paměti, přesunování swapu do paměti a zpět a uvolňováním paměti.

Audio:

Audio je simulováno jako vlákno, které se pokouší běžet v 50 ms intervalech a pak vyžaduje 5 % výkonu CPU.

Video:

Video je simulováno jako vlákno, které se pokouší využívat CPU 60krát za sekundu a využívá při tom 40 % výkonu CPU.

Byla testována schopnost všech 4 variant jádra reagovat na požadavek o vykonávání úlohy za současného běhu jiné zátěže. Pro real-time benchmark se hodí zátěž zpracováním multimédií, protože se dá dobře nasimulovat a testovat. Třeba zatížení při softwarovém renderingu by v real-time oblasti nedávalo příliš smysl a neotestovalo by požadované vlastnosti jádra.

Z testů je patrno, že průměrná prodleva (světle šedé hodnoty) i maximální prodleva (tmavě šedé hodnoty) Real-Time varianty je překvapivě nejvyšší. Dá se to vysvětlit tak, že jak již bylo zmíněno, úpravy jádra jsou postupně přejímány do původního kódu jádra. Tím jsou výrazně omezeny jeho dřívější nedostatky. Zároveň se u této varianty projevila vyšší náročnost na výkon, což se negativně projevilo na výsledné prodlevě. Na druhou stranu by Real-Time varianta měla lépe garantovat splnění úlohy běžící v real-time režimu bez ohledu na to, jak je CPU zatíženo, a měla by být lépe předvídatelná.

4.7 Shrnutí

Vývoj této úpravy linuxového jádra dosáhl takové úrovně, že může konkurovat předcházejícím dvěma řešením a to jak nekomerčnímu RTAI, tak komerčnímu řešení RTLinux.

Navíc byla nedávno přidána vylepšená implementace časovačů jádra (Ktimers). To umožňuje real-time úlohám vzájemně spolupracovat s velmi nízkou prodlevou s vysoce výkonnými časovacími zařízeními s jemným rozlišením. Ty umožňují implementaci řídících smyček v reálném čase s nebývalou přesností. Taky je umožněno použití RT mutexu v uživatelském prostoru přes standardní kernel API. Také úlohy v uživatelském prostoru jsou schopny využít efektivní dědičnosti priorit, detekce uváznutí a robustních protokolů pro jejich odblokování.

5. APLIKACE

Z výše zmíněných informací je zřejmé, že takto koncipované řídicí systémy najdou uplatnění v různých aplikacích. Jsou to zejména zapouzdřená (embedded) zařízení a taky zpracování zvuku a videa. Mimo to parametry real-timové verze Linuxu dovolují používat tento operační systém jako prostředek pro modelování a simulaci různých jevů.

5.1 Embedded systémy a jiné aplikace pro řízení

Real-time modifikace Linuxu je možno využít pro ovládání různých elektronických zařízení a jako Embedded zařízení.

Embedded systémy jsou takové systémy, které jsou vestavěné do různých zařízení. Mezi vlastnosti, které může Linux nabídnout těmto kategoriím, patří:

• Podpora pro různé síťové, zvukové a grafické karty, různé typy sběrnic jako např. ISA, PCMCIA, PCI, AGP, PCI-E atd. Taktéž podporuje různé porty pro datovou komunikaci jako je USB, Bluetooth, LPT, IEEE 1394/ atd.
• Podpora různých platforem jako je AMD, Intel, Motorola, PPC, Alpha, Sparc, Crusoe atd. Je použitelný na uniprocesorových počítačích, ale také nabízí podporu pro SMP.
• Plně podporuje protokol TCP/IP, tedy je možné na něm provozovat WWW servery, firewally a další aplikace vyžadující tento protokol.
• Významnou vlastností pro embedded systémy je modularita, tzn. je možné za běhu připojovat moduly do jádra a tím i rozšiřovat možnosti jádra. Tato vlastnost také zajišťuje přístup téměř ke všem zařízením připojeným k systému.
• Existuje mnoho nástrojů a možnost výběru z několika programovacích jazyků, které byly na platformu Linux portovány jako např. Assembler, Perl, Python a Fortran.
• Běžně je Linux vybaven překladačem jazyka GNU C (obsahuje kompletní překladač pro C, C++ a objektové C).
• minimální nároky pro systém jsou:
  • procesor i386 (běží v 32bitovém chráněném režimu)
  • 4 MB paměti
  • zařízení pro zavedení systému - jakékoliv zařízení, které umí obsloužit BIOS případně flash paměť
  • minimální systém je možné umístit na 1.44 MB disketu i s dostatkem nástrojů pro formátování a inicializaci souborového systému na pevném disku a k přenesení systému na pevný disk.
• Jádro samotné sice není plně preemptivní, ale výše zmíněné varianty úprav linuxového jádra tento problém velmi úspěšně řeší.
• Systém je volně šířený pod licencí GPL - neplatí se žádné licenční poplatky a je tedy možné jej volně stáhnout z internetu.
• Systém Linux je vysoce stabilní a prověřený operační systém.

5.2 Multimediální aplikace - JACK

JACK je audio server s nízkou prodlevou běžící na Linuxu a jiných systémech vyhovujícím normě POSIX. Může propojit několik různých audio aplikací a taky jim umožnit vzájemné sdílení audio dat. Tyto aplikace (klienty) mohou běžet ve vlastních procesech jako normální aplikace nebo jako plugin uvnitř serveru JACK. JACK byl od základu navržen pro profesionální práci s audiem a jeho design se zaměřuje na dvě klíčové oblasti: synchronní běh všech klientů a operace s nízkou prodlevou.

6. Závěr

Všechny tři varianty podávají obdobný výkon. Je jenom na tvůrci systému, které variantě dá přednost (pouze realtime preempt ještě není úplně dokončená a vyladěná úprava). Nejzásadnější rozdíly jsou ve způsobu implementace real-time úpravy a ceně produktu.

RTLinux je komerční řešení a všechny real-time úlohy běží jako moduly v real-time jádře a používají jeho API. Proto se pro něj jinak programují aplikace. Naproti tomu pro Realtime preempt se úlohy programují jako pro původní Linux, protože tyto volají standardní linuxové API.

RTLinux a RTAI se navíc, na rozdíl od realtime preempt, který se stále ještě vyvíjí, už nasazují na real-time zařízeních.

Linux samotný má řadu výhod. Mezi nejvýznamnější patří:

• Cena
  Linux je šířen pod licencí GNU/GPL a je zdarma.
• Dostupnost
  Software je možné stáhnout z internetu a nebo si jej nechat nainstalovat a nakonfigurovat organizací, která se zabývá jeho distribucí a podporou pro uživatele.
• Modularita
  Za běhu je možné připojovat další moduly do jádra a tím rozšiřovat možnosti systému.
• Optimalizovatelnost
  Systém je možné zkompilovat pouze s požadovanými vlastnostmi na daný hardware, a tak efektivně zmenšit jeho velikost a zvýšit výkon.
• Otevřenost
  Linux je šířen jako tzv. open source, což znamená, že je dodáván se zdrojovými kódy. Do nich je možno nahlédnout a případně je i upravit podle potřeby.
• Přenositelnost
  Systém je možné přenést i na jiné hardwarové platformy s různými typy procesorů.
• Stabilita
  Linux je stabilní a prověřený operační systém, který dokáže běžet i na podprůměrném hardwaru.
• Velikost
  Minimální systém s potřebnými nástroji je možné nahrát na standardní disketu o velikosti 1.44 MB.

Celá oblast se nadále rozvíjí a výše zmíněné systémy jsou dále vyvíjeny a zdokonalovány. Samozřejmě také narůstá počet aplikací, kde je možné využít takto koncipované real-timové operační systémy.

       

Komentáře

[Semo]

Nie je prostredny odsek sekcie 4.5.1 napisany naopak?

[belisarivs]

Jak jste to myslel? Chybi tam cislo 4.5, co?

[Robert Krátký]

Opraveno.

[Semo]

Myslel som to tak, ze veta:

Dědičnost priorit zvyšuje prioritu úlohy, která byla během práce v kritickém úseku předběhnuta na nejvyšší úroveň ze všech úloh čekajících na přístup do téhož kritického úseku.

by mala byt nahradena vetou:

Dědičnost priorit zvyšuje prioritu úlohy, která je v kritickém úseku na nejvyšší úroveň ze všech úloh čekajících na přístup do téhož kritického úseku.

Teda aspon podla toho, co si ja pamatam o dedicnosti priorit v krit. sekciach. Ale kludne sa mozem aj mylit.

[Xerces]

Perfektní článek. Díky.