Redox OS po výměně plánovače dělí čas mezi stejné procesy s odchylkou 2,5 procenta

Operační systém Redox rozděluje procesorový čas mezi běžící úlohy jinak než dosud. Plánovač DWRR v něm nahradil EEVDF, návrh z roku 1995, podle kterého plánuje od verze 6.6 i linuxové jádro. Závěrečnou zprávu o té práci zveřejnil Akshit Gaur na blogu projektu 22. srpna 2026.

Redox je mikrojaderný operační systém psaný od nuly v Rustu, tedy podobná stavba jako LiberSystem. Plánovač vznikl v rámci Redox Summer of Code, obdoby Googlem pořádaného Summer of Code, kterou si projekt dělá sám. Krátké oznámení, že je EEVDF v jádře, vyšlo 30. května 2026, čísla ale přišla až po optimalizacích.

Lag a uzávěrka místo pořadníku

EEVDF si u každé úlohy vede dvě čísla. První je lag: rozdíl mezi časem, který úloze podle jejího podílu náležel, a časem, který opravdu dostala. Kdo je pozadu, má lag kladný a smí běžet; kdo si vzal víc, chvíli počká. Druhé číslo je virtuální uzávěrka. Bere se okamžik, kdy se úloha stane způsobilou, a přičte se k němu základní čekací doba dělená váhou úlohy, takže čím vyšší priorita, tím kratší uzávěrka.

Vlastní pravidlo se pak vejde do jedné věty: běží ta ze způsobilých úloh, která má nejbližší uzávěrku. Přesně to popisuje zkratka EEVDF, tedy Earliest Eligible Virtual Deadline First. Algoritmus pochází z práce Iona Stoicy a Husseina Abdel-Wahaba z roku 1995 a Linux ho převzal v jádře 6.6 náhradou za CFS.

Předchůdce v Redoxu, Deficit Weighted Round Robin, uměl dát víc času tomu, kdo má vyšší prioritu, ale neuměl ohlídat, že se dostane i na ostatní. Gaur to v textu popisuje na baru, kde obsluha nalévá VIP hostům tak pilně, že zbytek sálu zůstane suchý. Tomu se v plánovačích říká hladovění a Redox ho měl v tak silné podobě, že se na něm rozbilo i měření priorit: poměr mezi úlohou s prioritou -10 a +10 vycházel 1,4násobný proti teoretickým 86,8. S EEVDF vyšel 76,87, tedy zhruba 89 procent teoretické hodnoty.

Fronta běhu se rozpadla na jádra

Výměna algoritmu byla jen část práce a podle vlastního rozboru autora ne ta, které patří většina zrychlení. Seznam připravených úloh byl v Redoxu jedna globální struktura, takže dvě jádra nemohla přepnout kontext naráz a čekala na zámek. Teď má vlastní frontu každé jádro, a protože se tím může stát, že jedno jádro nemá co dělat a druhé je zahlcené, přibylo k tomu přebírání úloh z cizí fronty. Spustí se, když je místní fronta prázdná, nebo v pravidelném intervalu, pokud je rozdíl v počtu úloh proti jinému jádru dost velký; úlohy se pak berou obden, tedy první, třetí, pátá, a jejich virtuální čas se přepočte na hodiny nového jádra.

Uvnitř fronty vystřídal jednoduchý seznam typ BTreeMap. Klíč tvoří trojice virtuální uzávěrka, zbytek přiděleného úseku a číslo kontextu, takže se při shodě uzávěrek dostane na řadu úloha, která už rozdělaný úsek má. V hodnotách leží kromě odkazu na kontext i jeho virtuální čas a váha, a to schválně duplicitně: díky tomu se způsobilost dá ověřit bez zamykání. Původní práce z roku 1995 pro tenhle účel popisuje rozšířený strom. Gaur ho nepoužil a v textu vysvětluje proč: standardní BTreeMap je odladěný, vlastní strom by přinesl vlastní chyby a náskok by měl jen v nejhorším případě, kdy není způsobilá skoro žádná úloha.

Zmizel i lineární průchod spícími úlohami. Časovače se přesunuly do BTreeSet, ze kterého jde vytáhnout vše, co má vypršet teď. U ostatních zařizuje zařazení do fronty rovnou ten kód, který úlohu odblokuje, takže z průchodu celým seznamem zbyla jedna operace. A aby si úloha nemohla lag ohýbat tím, že se úseku vzdá dřív, dostane při předčasném vzdání penalizaci nepřímo úměrnou své váze.

Co ukázalo měření

Rovnoměrnost dělení času měřil Gaur šestnácti stejnými procesy, které nedělají nic než zvyšují čítač. Na jednom jádru se s DWRR lišily o 1 940,52 procenta, s EEVDF o 2,48 procenta. Z těchto dvou čísel plyne 782násobné zlepšení, které projekt uvádí v souhrnu. Na čtyřech jádrech byl rozptyl 389 až 617 procent proti 1,09 až 1,37 procenta.

Nejvíc si polepšila zátěž s mnoha spícími vlákny. Deset tisíc spících procesů a dva procesy, které si posílají zprávy a nutí tím přepnout kontext, zvládly na čtyřech jádrech 765 obrátek za sekundu se starým plánovačem a 109 386 s novým. Autor u toho sám píše, že zásluhu má z velké části odstranění lineárního průchodu, ne samotná matematika EEVDF.

Číslo, které převzaly zpravodajské servery, je 2,6násobná propustnost. Pochází z třicetisekundového testu se dvěma vlákny na zprávy a dvěma pracovními vlákny na jednom jádru: 123,50 operace za sekundu proti 323,50. Ve stejném měření klesl medián čekání na probuzení ze 4,48 sekundy na 1,54 sekundy.

Dobrovolné přepnutí kontextu spadlo z 2 µs na 350 ns, což je zmiňovaných 82 procent. U blokujícího přepnutí vypadá tabulka takhle:

sestava	průměrná latence
Linux, připnuto na jádro 0, na holém stroji	0,552 µs
Redox EEVDF, jedno jádro, QEMU	0,923 µs
Redox EEVDF, čtyři jádra, QEMU	0,931 µs
Linux, bez připnutí, na holém stroji	1,230 µs
Redox DWRR, jedno jádro, QEMU	1,367 µs
Redox DWRR, čtyři jádra, QEMU	4,253 µs

Kde zpráva sama couvá

Srovnání s Linuxem v té tabulce označuje Gaur za nesouměřitelné, protože Linux běžel na holém stroji a Redox v QEMU. U hodnot 2 µs a 350 ns dodává, že obsahují režii měřicího programu, takže skutečná čísla budou nižší. Řádek, ve kterém Redox předstihl nepřipnutý Linux, tedy neříká, že by byl Redox rychlejší; říká, že se dostal do stejného řádu.

Uvnitř zprávy je i měření, které vyzní skromně. Ukázka Pixelcannon běžela na jednom jádru se starým plánovačem kolem 1 600 snímků za sekundu, s novým kolem 1 700. Rozdíl se ukáže až pod zátěží: při pohybu myší spadla stará sestava na 150 snímků a rozhraní zamrzlo tak, že kurzor nebyl vidět, kdežto nová klesla na zhruba 190 a kurzor se hýbal dál.

Práci vedli podle poděkování v textu Jacob Lorentzon a Wildan Mubarok, samotné RSoC pak Ron Williams. Rozšířený strom z původní práce zůstává na stole pro chvíli, kdy budou fronty úloh delší, než jsou dnes.

Zdroje

• RSoC 2026: EEVDF for Redox – závěrečná zpráva Akshita Gaura, redox-os.org, 22. srpna 2026
• RSoC 2026: EEVDF Scheduler – oznámení z 30. května 2026
• Redox OS Switches To EEVDF-Based Scheduler For 2.6x Throughput – Phoronix, 22. srpna 2026
• Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation – Ion Stoica, Hussein Abdel-Wahab, 1995
• Linux 6.6 – přehled změn, kernelnewbies.org