Redox OS nomaina plānotāju uz EEVDF: taisnīguma novirze krīt no 1940 % uz 2,48 %

Redox OS kodolā nomainīts procesu plānotājs. 16 vienādi procesoru noslogojoši procesi uz viena kodola tagad saņem procesora laiku ar 2,48 % novirzi. Ar iepriekšējo plānotāju novirze bija 1940,52 %: daži procesi rēķināja pilnā ātrumā, kamēr citi rindā gaidīja gandrīz bez darba. Izmaiņas Redox Summer of Code programmā izstrādāja Akshit Gaur, kurš 22. augusta atskaitē šo starpību sauc par 782 reizes labāku taisnīgumu.

Redox ir no nulles Rust valodā rakstīta mikrokodola operētājsistēma, kurā draiveri un servisi darbojas lietotāja telpā. Plānotājs šogad mainīts divreiz. Aprīlī vienkāršo Round Robin nomainīja Deficit Weighted Round Robin, kas pirmoreiz ļāva procesiem piešķirt dažādas prioritātes. Augustā DWRR vietā stājās EEVDF.

Kāpēc DWRR nepietika

Gaur salīdzināja augstas un zemas prioritātes procesa saņemto procesora laiku. Teorētiskā attiecība ir 86,8. Ar DWRR mērījums deva 1,4, jo zemās prioritātes procesu badošanās mērījumu izkropļoja tik stipri, ka prioritāšu ievērošanu vispār bija grūti novērtēt. Ar EEVDF tā pati attiecība ir 76,87 jeb ap 89 % no teorētiskās vērtības.

Otrs iebildums bija par to, kas DWRR gaidīja nākotnē. Lai augstās prioritātes process pārējos neatstātu pilnīgi bez procesora, plānotājam būtu vajadzējis minēt, kurā mirklī tam laiku atņemt. Linux šo ceļu jau nogāja ar CFS, kas gadu gaitā uzkrāja tieši tādas minēšanas heiristikas. 2023. gadā Linux tās nomainīja ar EEVDF. Gaur atzīmē, ka Redox to īsteno pēc tam, kad Linux algoritmu jau pierādījis praksē.

Pāreja no DWRR mums devusi ļoti būtisku ieguvumu gandrīz katrā mērījumā: 782 reizes labāku taisnīgumu, par 82 % mazāku konteksta pārslēgšanas laiku un 2,6 reizes lielāku caurlaidspēju.

Kā EEVDF izvēlas nākamo procesu

EEVDF pilnais nosaukums ir Earliest Eligible Virtual Deadline First. Algoritmu 1995. gadā aprakstīja Ion Stoica un Hussein Abdel-Wahab. Katram procesam ir svars, kas nosaka tā daļu no procesora. Papildus tam ir divi laiki. Pirmais ir lag: cik daudz procesora laika procesam pienācās mīnus cik tas reāli saņēma. Ja pienācās vairāk, lag ir pozitīvs un process ir tiesīgs rēķināt. Otrais ir virtuālais termiņš, ko rēķina kā tiesīguma laiku plus pieprasīto laiku, dalītu ar svaru. Jo lielāks svars, jo tuvāks termiņš. Plānotājs ņem to procesu, kuram lag nav negatīvs un kuram ir agrākais termiņš.

Redox kodolā to dara funkcija select_next_context. Lag atsevišķi netiek glabāts. Katram procesam glabā tā lokālo virtuālo laiku. Lag ir starpība starp kodola globālo virtuālo laiku un šo lokālo vērtību. Aktīvie procesi katram kodolam glabājas BTreeMap struktūrā, kur atslēga ir termiņš, atlikušais kvants un procesa numurs. Plānotājs iet pa koku no sākuma un pārslēdzas uz pirmo procesu, kura virtuālais laiks nepārsniedz globālo. Ja tiesīga procesa nav neviena, globālo virtuālo laiku pavirza uz priekšu līdz mazākajai vērtībai kokā, lai procesors nestāvētu dīkā.

Viena detaļa aizver acīmredzamu ļaunprātības ceļu. Process, kas savu kvantu atdod pāragri, saņem sodu, kas ir apgriezti proporcionāls tā svaram. Bez soda process varētu atkārtoti atdot laiku, uzkrāt pozitīvu lag un pēc tam procesoru monopolizēt.

Kur pazuda konteksta pārslēgšanas laiks

Trīs datu struktūru izmaiņas deva lielāku ieguvumu par pašu algoritma matemātiku. Gaidošo procesu saraksts agrāk bija globāls, tāpēc divi kodoli nevarēja pārslēgt kontekstu vienlaikus: abiem vajadzēja to pašu slēdzeni. Attiecīgā izmaiņa katram kodolam iedeva savu rindu. Brīvprātīga pārslēgšanās ar yield_now saīsinājās no 2 mikrosekundēm līdz 350 nanosekundēm. Gaur piebilst, ka daļa no šī skaitļa nāk no testa ietvara.

Otrā izmaiņa aizvāca lineāro skenēšanu. Katrā konteksta pārslēgšanā kodols izgāja cauri visiem bloķētajiem procesiem, lai atrastu tos, kas kļuvuši gatavi. Taimeri tagad glabājas BTreeSet struktūrā, no kuras var izvilkt tikai tos, kas nostrādā šajā mirklī. Pārējos gadījumos procesu rindā ieliek jau tas kods, kas to atbloķē. Sarežģītība nokrita no O(N) uz O(log N) un O(1).

Trešā izmaiņa ir darba zagšana, kas kļuva vajadzīga tāpēc, ka rindas vairs nav kopīgas. Ja kodola rinda ir tukša vai ja starpība procesu skaitā pārsniedz slieksni, kodols no noslogotākā kaimiņa paņem pusi no starpības un ņem katru otro procesu rindā. Paņemtajiem procesiem virtuālo laiku pārrēķina attiecībā pret jaunā kodola pulksteni.

Skaitļi zem noslogojuma

Pamošanās tests palaida 10 000 miegā gaidošu procesu un divus procesus, kas viens otram sūta ziņojumus un bloķējas līdz atbildei. Viens aplis šeit ir ceļš no A uz B un atpakaļ uz A.

• DWRR, viens kodols: 2197 apļi sekundē
• DWRR, četri kodoli: 765
• EEVDF, viens kodols: 107 945
• EEVDF, četri kodoli: 109 386

Starpība ir ap 143 reizēm. Ar DWRR četri kodoli deva gandrīz trīs reizes sliktāku rezultātu par vienu kodolu. Ar EEVDF rezultāts uz četriem kodoliem paliek tāds pats.

Etalons schedrs 30 sekundēs ar DWRR paveica 123,50 operācijas sekundē, ar EEVDF 323,50. No šī nāk 2,6 reizes lielākā caurlaidspēja. Pamošanās aizture mediānā nokrita no 4,48 līdz 1,54 sekundēm.

Bloķējošas konteksta pārslēgšanās vidējā aizture QEMU vidē ar EEVDF vienam kodolam ir 0,923 mikrosekundes un četriem kodoliem 0,931. Ar DWRR tie bija 1,367 un 4,253 mikrosekundes. Tajā pašā tabulā Gaur rāda Linux uz reālas dzelzs: 0,552 mikrosekundes ar procesu piesaistītu nulles kodolam un 1,230 bez piesaistes. Salīdzinājums nav godīgs, jo Redox mērīts virtuālajā mašīnā.

Grafiskajā demo pixelcannon uz viena kodola DWRR deva ap 1600 kadriem sekundē, kas peles kustības laikā nokrita līdz 150 un saskarne iesala tik stipri, ka kursoru nemaz nevarēja redzēt kustamies. Ar EEVDF bāze ir ap 1700 kadriem, peles kustības laikā ap 190. Kursors kustas.

Kas palicis vienkāršots

Oriģinālais 1995. gada raksts EEVDF īstenošanai iesaka papildinātu koku. Redox lieto standarta BTreeMap. Gaur izvēli skaidro ar to, ka papildinātais koks dod priekšrocību tikai sliktākajā gadījumā, kad tiesīgu procesu ir maz vai nav nemaz: O(log N) pret O(N). Reālos koka izmēros standarta struktūra strādā līdzīgi un ir draudzīgāka kešatmiņai, turklāt pašrakstītā kokā būtu vairāk vietas kļūdām.

Kodā palīdzēja Jacob Lorentzon un Wildan Mubarok. Redox jūlija atskaitē Ribbon un Ron Williams to pašu konteksta pārslēgšanas mērījumu min citos skaitļos: no aptuveni 1,150 mikrosekundēm līdz aptuveni 250 nanosekundēm.

Avoti

• RSoC 2026: EEVDF for Redox, Akshit Gaur, redox-os.org, 22.08.2026.
• RSoC 2026: A new CPU scheduler for Redox, redox-os.org, 02.04.2026.
• This Month in Redox, July 2026, redox-os.org
• Redox OS Switches To EEVDF-Based Scheduler For 2.6x Throughput, phoronix.com
• Earliest Eligible Virtual Deadline First, Stoica un Abdel-Wahab, 1995