Jaderné noviny – 16. 3. 2017: Aktualizace plánovače deadline

30. 3. 2017 | Redakce

Články - Jaderné noviny – 16. 3. 2017: Aktualizace plánovače deadline  

Stav vývoje jádra. Citáty týdne: James Bottomley a Daniel Vetter. Jaderný podcast. Aktualizace plánovače deadline.

Stav vývoje jádra

Současné vývojové jádro je 4.11-rc2, vydané 12. března. Linus k tomu řekl: „Myslím, že na tuto fázi jsme na tom s vývojovým jádrem dobře. Nemělo by být nijak zvlášť děsivé říct: ‚Budu trochu podnikavější a vyzkouším rc2 jádra.' Ano, je to stále ještě jeden z prvních kandidátů na vydání, ale nebojte se pomoct nám ujistit se, že nám to jde dobře.“

Seznam regresí v cyklu 4.11 ze 14. března obsahuje devět známých problémů.

Stabilní aktualizace: 4.10.2, 4.9.14 a 4.4.53 byly vydány 12. března. Následovaly je 4.10.3, 4.9.15 a 4.4.54 dne 15. března.

Citáty týdne

Když je špatně cizí e-mailová adresa, může to být jenom chyba při kopírování. Když je špatně vaše vlastní e-mailová adresa, může jít o raný příznak krize identity.

—James Bottomley

To je přesně ten důvod, proč _musíte_ všechno, co děláte, nejprve prodiskutovat v upstreamu. Vaše vnitřní týmy prostě nemají autoritu něco navrhovat.

—Daniel Vetter (dostupné také v podobě trička)

Jaderný podcast

Jaderný podcast ze 13. března Jona Masterse je venku. „V jaderném podcastu z tohoto týdne: Linus Torvalds oznamuje vydání 4.11-rc2 (včetně předběžného zprovoznění pětiúrovňového stránkování Intelu), readahead odkládacího prostoru založený na VMA a probíhající vývoj v dalším cyklu.“

Aktualizace plánovače deadline

CPU plánovač deadline za sebou má dlouhou cestu, řekl na Linaro Connest 2017 Juri Lelli, ale stále zbývá hodně práce, kterou je třeba udělat. Ačkoliv byl tento plánovač původně určen pro realtime nasazení, máme důvod věřit, že se hodí i do jiných podmínek, včetně embedded a mobilních zařízení. Ve své přednášce Lelli shrnul, co všechno plánovač deadline aktuálně umí a co za změny se plánuje do blízké (a ne až tak blízké) budoucnosti.

Plánovač deadline byl začleněn ve vývojovém cyklu 3.14. Přidává možnosti plánování v reálném čase, které jsou v mnoha ohledech mocnější než tradiční prioritní plánování. Umožňuje specifikaci explicitních omezení latencí a umí se z principu vyhnout hladovění procesů. Má také lepší informace o omezeních při aktuálním vytížení, a tak může činit lepší rozhodnutí.

Plánovač jádra je postaven na algoritmu earliest deadline first (EDF), podle kterého dojde ke spuštění toho procesu, jehož deadline („mezní termín splnění“) nastane nejdříve. EDF je vylepšený o algoritmus constant bandwidth server (CBS, blíže popsaný v tomto článku), který brání procesu, který nemůže běžet po většinu svého času, aby překážel ostatním procesům. CBS v podstatě říká procesům, že musí svůj procesorový čas využít v době, kdy je tak naplánováno, a nikoli otálet a očekávat jeho přidělení v plném rozsahu těsně před deadline. Výsledkem je plánovač, který poskytuje silnou časovou izolaci úloh, při kterých nemůže jeden proces zabránit dalšímu ve splnění jeho deadline.

V současné době komunita, která vyvíjí mobilní a embedded systémy, vkládá mnoho úsilí do plánování, při němž se zohledňují energetické nároky. Tato práce má cenný cíl – plánovat tak, aby spotřeba energie systému byla co nejmenší – ovšem ukázalo se, že je těžké dostat ji do upstreamu, i když byla začleněna do běžného jádra Androidu. V mnoha případech může nakonec být plánovač deadline vhodnější, když je potřeba šetřit energií, řekl Lelli.

Novinkou ve vývoji je funkce zpětného získání šířky pásma (bandwidth reclaiming). Jedním z hlavních rysů plánování deadline je, že v okamžiku, když proces překročí svůj rezervovaný procesorový čas (svou „šířku pásma“ procesoru), plánovač ho prostě přiškrtí až do dalšího úseku plánování. Toto přiškrcení je nezbytné k tomu, aby probíhající proces nemohl kolidovat s ostatními procesy v systému, ale může představovat problém ve chvíli, kdy je požadavek procesu na víc času, než mu bylo přiděleno, legitimní. Funkce zpětného získání šířky pásma tedy udělá, co se nabízí: dá procesu k dispozici více času, pokud ho nepotřebuje žádný jiný proces v systému.

Co je možná méně zřejmé, je určení množství procesorového času, který není doopravdy zapotřebí. To se provádí pomocí algoritmu GRUB („greedy utilization of unused bandwidth“), který je popsaný v tomto článku (PDF). Stručně řečeno, GRUB sleduje, kolik dostupného procesorového času běžící úlohy s deadline skutečně využívají, a na základě toho odhadne objem procesorového času, který nebude využit. Díky tomuto odhadu je uvolnění času navíc pro účely procesu, který ho potřebuje, relativně přímočaré.

Škálování frekvence procesoru je důležitým nástrojem v portfoliu řízení spotřeby, ale tradičně moc nespolupracuje s algoritmy pro plánování v reálném čase, včetně deadline. V současných jádrech se předpokládá, že úlohy v reálném čase potřebují plný výkon CPU, tudíž jejich přítomnost způsobí, že CPU poběží naplno. To může vést k plýtvání v případě, že běžící procesy [deadline] tolik procesorového času nepotřebují.

Řešení tohoto problému vyžaduje celou řadu změn – počínajíc skutečností, že samotný plánovač deadline počítá s tím, že procesor poběží naplno. Plánovač je nutné opravit, aby bylo možné škálovat rezervace časů tak, aby se rovnaly aktuální rychlosti procesoru. Dále je potřeba tuto změnu rozšířit na heterogenní víceprocesorové systémy (např. big.LITTLE, kde nejsou všechny procesory systému stejně rychlé).

Jakmile to bude hotové, hodilo by se mít možnost řídit výběr frekvence procesoru přímo z plánovače deadline. Plánovač CFS, který se používá pro běžné úlohy, používá k výběru frekvence mechanismus sledování zátěže dílčích entit, ale plánovač deadline v současné době pouze tlačí frekvenci procesoru na maximum. Jakmile bude kód pro získávání šířky pásma začleněn, bude možné měřit skutečnou zátěž, kterou přidají úlohy s deadline. Pak bude možné zvolit takovou frekvenci procesoru, která zvládne všechny požadované úlohy efektivně.

Samozřejmě bude vždy potřeba se vypořádat se spoustou maličkostí. Například na systémech ARM se frekvence procesoru mění v samostatném pracovním vlákně. Aby byla možná spolupráce škálování procesoru a plánování deadline, bude třeba umožnit preempci úloh s deadline (u nichž preempce obvykle není možná) v tomto vlákně.

Plánovač deadline v současné době pracuje na úrovni samostatných procesů, nefunguje s řídícími skupinami. Nastávají ale situace, kdy je rozumné dát rezervaci deadline skupině procesů. Lelli uvedl vlákna virtuálních strojů a vykreslovací řetězce jako příklady zátěží, které by skupinové plánování deadline využily. Představa implementace spočívá v podstatě v dvouúrovňové hybridní hierarchii. Na nejvyšší úrovni by algoritmus EDF vybral další skupinu k vykonání, ale uvnitř této skupiny by se použilo běžné realtime plánování (FIFO nebo round-robin). Jakmile bude tato funkce fungovat, mohla by vytlačit stávající realtime škrtící mechanismus.

V ještě vzdálenější budoucnosti je podle Lelliho plán na rozšíření mechanismu pro opětovné využití šířky pásma, aby bylo možné snižovat prioritu. Když by proces překročil svůj rezervovaný čas, běžel by i nadále, ale pouze jako obyčejný proces bez realtime priority. Priorita by mu byla navrácena v dalším plánovacím období. Je také velký zájem o plánování orientovaném na šetření energie v rámci plánovače deadline.

Další kýžená vlastnost spočívá v podpoře afinity procesu k procesoru. Mechanismus dědění priority by také snesl nějaká vylepšení. Aktuálně je to tak, že úloha, která blokuje úlohu s deadline, tuto deadline podědí. Bylo by žádoucí přejít na algoritmus, jako je multiprocesor bandwidth inheritance protocol (PDF). Existuje také poptávka po mechanismu dynamické zpětné vazby, který by mohl upravovat rezervace procesu na základě pozorovaných potřeb. Zatím ale na těchto záležitostech nikdo nepracuje.

Video z přednášky je dostupné zde.

Diskuse k tomuto článku

[Petr Tomášek]

plánovače deadline

ty už raději nechlastej - a nepřekládej!

[citanus]

15.3.

[Petr Tomášek]

A? Mění to něco na skutečnosti, že ten překlad je mizerný?

[citanus]

nemyslim si

[JZD]

Ten kdo neumí anglicky (já) vůbec, je aspoň rád za mizerný překlad než žádný.

[salam]

Co konkrétně je tam mizerné?

[Petr Tomášek]

Neumíš číst? „Plánovač deadline“ je hnus a je to navíc jazykově velmi nejednoznačné. Zní to skoro jako „spalovač mrtvol“ (⇒ „plánovač plánující deadliny“) nebo „strýček Hugo“ (→ plánovač se jménem „deadline“). Daleko „češtější“ a hlavně jasnější by bylo něco jako „deadlinový plánovač“.

Další věci hned v 1. ostavci:

• „Myslím, že na tuto fázi jsme na tom s vývojovým jádrem dobře.“ - recte buď „v této fázi“, nebo celou větou: „na to, že se nacházíme v této fázi, ...“.
• „Nemělo by být nijak zvlášť děsivé říct“ - moc kostrbaté, lepší např.: „Měli bychom být s to bez obav říci:“
• „Budu trochu podnikavější a vyzkouším rc2 jádra.“ - recte „odvážnější“. Opravdu se zde nejedná o to, že by se někdo rozhodl vyzkoušet podomní prodej nebo si založil vlastní firmu, jen proto, aby si zkusil rc2.
• „ale nebojte se pomoct nám ujistit se, že nám to jde dobře.“ („but go on, help us make sure we're doing ok.“) - příliš kostrabaté, navíc překlad „že nám to jde dobře“ je vyloženě špatně. ⇒ Lépe např.: „ale jistě, pomozte nám zajistit, že jsme na správné cestě“ ⇒⇒ volněji: „ale velmi uvítáme, když nám pomůžete zkontrolovat, že tam nemáme chyby.“

Čili první odstavec a ani jedna věta, která by byla uspokojivě přeložena (tak, aby se to četlo plynule, bez zbytečných kostrbatostí a bez toho, aniž by člověk sáhodlouze musel hádat, co že to stálo v anglickém originále a co „překladatel“ zase nepochopil). Mám pokračovat dal?

Takže za mě ten překlad stojí naprosto za hovno a lepší by bylo to vůbec nepřekládat...

[ed]

Ono by tam v originale to "deadline" nesmelo figurovat ako nazov planovaca. V tom vyzname je preklad spravny a pouzitie anglickeho slova pripustne, ba priam ziadane. V opacnom pripade by sa v tomto kontexte "CFQ scheduler" malo prekladat ako "kompletne ferovo frontovy planovac" a to je volovina.