CFS:Naprosto spravedlivé plánování procesů v Linuxu

Linux využívá modulární přístup k plánování procesorů tím, že k plánování různých typů procesů lze použít různé algoritmy. Třída plánování určuje, která politika plánování platí pro který typ procesu. Kompletně spravedlivé plánování (CFS), které se stalo součástí linuxového jádra 2.6.23 v roce 2007, je třída plánování pro normální (na rozdíl od procesů v reálném čase), a proto se jmenuje SCHED_NORMAL .

CFS je určeno pro interaktivní aplikace typické pro desktopové prostředí, ale lze jej nakonfigurovat jako SCHED_BATCH upřednostňovat dávkové zatížení běžné například na velkoobjemovém webovém serveru. V každém případě se CFS dramaticky rozchází s tím, co by se dalo nazvat „klasickým preventivním plánováním“. Také „zcela spravedlivé“ tvrzení je třeba vnímat technickým okem; jinak by toto tvrzení mohlo vypadat jako prázdné vychloubání.

Pojďme se ponořit do detailů toho, co odlišuje CFS od – vlastně výše uvedených – jiných plánovačů procesů. Začněme rychlým přehledem některých základních technických termínů.

Některé základní koncepty

Linux zdědí unixový pohled na proces jako spuštěný program. Proces jako takový musí bojovat s jinými procesy o sdílené systémové prostředky:paměť pro uložení pokynů a dat alespoň jeden procesor k provádění instrukcí a I/O zařízení k interakci s vnějším světem. Plánování procesů je způsob, jakým operační systém (OS) přiděluje úlohy (např. drcení některých čísel, zkopírování souboru) procesorům – běžící proces pak provádí úlohu. Proces má jedno nebo více vláken provádění , což jsou sekvence instrukcí na úrovni stroje. Naplánovat proces znamená naplánovat jedno z jeho vláken na procesoru.

Linuxový terminál

• 7 nejlepších emulátorů terminálu pro Linux
• 10 nástrojů příkazového řádku pro analýzu dat v systému Linux
• Stáhnout nyní:SSH cheat sheet
• Cheat sheet pro pokročilé příkazy systému Linux
• Výukové programy příkazového řádku systému Linux

V rámci zjednodušení Linux přemění plánování procesů na plánování vláken tím, že s naplánovaným procesem zachází, jako by byl jednovláknový. Pokud je proces vícevláknový s N vlákna a poté N K pokrytí vláken by byly nutné akce plánování. Vlákna v rámci vícevláknového procesu zůstávají související v tom, že sdílejí zdroje, jako je paměťový adresní prostor. Linuxová vlákna jsou někdy popisována jako odlehčené procesy s lehkou zdůraznění sdílení zdrojů mezi vlákny v rámci procesu.

Ačkoli proces může být v různých stavech, dva jsou zvláště zajímavé při plánování. A blokováno proces čeká na dokončení nějaké události, jako je I/O událost. Proces lze obnovit až po dokončení události. spustitelné proces je ten, který není aktuálně blokován.

Proces je vázán na procesor (také znám jako výpočetní ) pokud spotřebovává většinou procesor na rozdíl od I/O zdrojů a I/O-bound v opačném případě; proces vázaný na procesor je tedy většinou spustitelný, zatímco proces vázaný na I/O je většinou blokován. Například, crunching numbers je vázán na procesor a přístup k souborům je vázán na I/O. Ačkoli celý proces může být charakterizován buď jako vázaný na procesor nebo na I/O, daný proces může být jeden nebo druhý během různých fází jeho provádění. Interaktivní desktopové aplikace, jako jsou prohlížeče, bývají I/O vázány.

Dobrý plánovač procesů musí vyvážit potřeby úloh vázaných na procesor a na I/O, zejména v operačním systému, jako je Linux, kterému se daří na tolika hardwarových platformách:stolní počítače, vestavěná zařízení, mobilní zařízení, serverové clustery, superpočítače. a další.

Klasické preventivní plánování versus CFS

Unix popularizoval klasické preemptivní plánování, které později přijaly další operační systémy včetně VAX/VMS, Windows NT a Linux. Středem tohoto modelu plánování je pevný časový úsek , množství času (např. 50 ms), po které může úloha držet procesor, dokud není vyloučena ve prospěch nějaké jiné úlohy. Pokud preemptovaný proces nedokončil svou práci, musí být proces přeplánován. Tento model je výkonný v tom, že podporuje multitasking (souběžnost) prostřednictvím sdílení času procesoru, a to i na strojích s jedním CPU v minulosti.

Klasický model obvykle zahrnuje více plánovacích front, jednu na každý proces s prioritou:Každý proces ve frontě s vyšší prioritou je naplánován před jakýmkoli procesem ve frontě s nižší prioritou. Například VAX/VMS používá pro plánování 32 prioritních front.

CFS se obejde bez pevných časových intervalů a explicitních priorit. Množství času pro danou úlohu na procesoru se vypočítává dynamicky, jak se kontext plánování mění v průběhu životnosti systému. Zde je náčrt motivujících nápadů a technických detailů:

• Představte si procesor P, který je idealizovaný v tom, že může provádět více úloh současně . Například úkoly T1 a T2 mohou být provedeny na P současně, přičemž každý obdrží 50 % magického výkonu P. Tato idealizace popisuje dokonalý multitasking , kterého se CFS snaží dosáhnout na skutečných, na rozdíl od idealizovaných procesorů. CFS je navržen tak, aby se přiblížil dokonalému multitaskingu.

• Plánovač CFS má cílovou latenci , což je minimální doba – ideálně nekonečně krátká – potřebná pro každou spustitelnou úlohu, aby se procesor zapnul alespoň jednou. Pokud by taková doba trvání mohla být nekonečně krátká, pak by se u každé spustitelné úlohy procesor zapnul během jakéhokoli daného časového úseku, jakkoli krátkého (např. 10 ms, 5 ns atd.). Samozřejmě, idealizované nekonečně malé trvání musí být aproximováno v reálném světě a výchozí aproximace je 20 ms. Každá spustitelná úloha pak dostane 1/N část cílové latence, kde N je počet úkolů. Pokud je například cílová latence 20 ms a existují čtyři soupeřící úlohy, pak každá úloha získá časový úsek 5 ms. Mimochodem, pokud je během události plánování pouze jeden úkol, tento šťastný úkol získá celou cílovou latenci jako svůj díl. Veletrh v CFS přichází do popředí v 1/N řez přidělený každé úloze bojující o procesor.

• 1/N řez je skutečně časový řez – ale ne pevný, protože takový řez závisí na N , počet úloh, které aktuálně čekají na procesor. Systém se v průběhu času mění. Některé procesy se ukončí a vytvoří se nové; spustitelné procesy zablokují a zablokované procesy se stanou spustitelnými. Hodnota N je dynamický, a proto je 1/N timeslice vypočítané pro každou spustitelnou úlohu ucházející se o procesor. Tradiční pěkné hodnota se používá pro váhu 1/N plátek:pěkné s nízkou prioritou hodnota znamená, že pouze zlomek 1/N řez je přidělen úkolu, zatímco pěkné s vysokou prioritou hodnota znamená, že úměrně větší zlomek 1/N plátek je přidělen úkolu. Stručně řečeno, pěkné hodnoty neurčují řez, ale pouze modifikují 1/N plátek, který představuje spravedlnost mezi soupeřícími úkoly.

• Operačnímu systému vzniká režie při každém přepnutí kontextu vyskytuje se; to znamená, když je jeden proces preemptován ve prospěch jiného. Aby se tato režie nestala nepřiměřeně velkou, existuje minimální doba (s typickým nastavením 1 ms až 4 ms), kterou musí každý naplánovaný proces spustit, než bude vyloučen. Toto minimum se nazývá minimální úroveň podrobnosti . Pokud o procesor soupeří mnoho úloh (např. 20), může být minimální úroveň podrobnosti (předpokládejme 4 ms) vyšší než 1/N řez (v tomto případě 1 ms). Pokud se ukáže, že minimální úroveň podrobnosti je větší než 1/N Slice, systém je přetížený, protože o procesor soupeří příliš mnoho úkolů – a spravedlnost jde ven.

• Kdy nastává preempce? CFS se snaží minimalizovat přepínání kontextu vzhledem k jejich režii:čas strávený přepínáním kontextu je čas nedostupný pro jiné úkoly. Jakmile tedy úloha získá procesor, běží po celou svou váženou 1/N plátek před tím, než bude preempován ve prospěch nějakého jiného úkolu. Předpokládejme, že úloha T1 byla spuštěna pro svou váženou 1/N slice a spustitelná úloha T2 má aktuálně nejnižší virtuální runtime (vruntime) mezi úkoly, které se ucházejí o procesor. Vruntime zaznamenává v nanosekundách, jak dlouho úloha běží na procesoru. V tomto případě by byl T1 preempován ve prospěch T2.

• Plánovač sleduje vruntime pro všechny úlohy, spustitelné a blokované. Čím nižší je vruntime úlohy, tím více si úloha zaslouží čas na procesoru. CFS podle toho posouvá úlohy s nízkým běhovým časem směrem k popředí plánovacího řádku. Podrobnosti budou připravovány, protože řádek je implementován jako strom, nikoli jako seznam.

• Jak často by měl plánovač CFS přeplánovat? Existuje jednoduchý způsob, jak určit plánovací období . Předpokládejme, že cílová latence (TL) je 20 ms a minimální granularita (MG) je 4 ms:

  TL / MG = (20 / 4) = 5 ## five or fewer tasks are ok

  V tomto případě by pět nebo méně úloh umožnilo každé úloze zapnout procesor během cílové latence. Pokud je například číslo úlohy pět, každá spustitelná úloha má 1/N plátek 4 ms, který se náhodou rovná minimální zrnitosti; pokud je číslo úkolu tři, každý úkol dostane 1/N úsek téměř 7 ms. V obou případech by plánovač přeplánoval za 20 ms, což je doba trvání cílové latence.

  Problém nastane, pokud počet úkolů (např. 10) překročí TL / MG, protože nyní musí každý úkol získat minimální čas 4 ms namísto vypočítaného 1/N řez, což je 2 ms. V tomto případě by plánovač přeplánoval za 40 ms:

  (number of tasks) * MG = (10 * 4) = 40ms ## period = 40ms

Linuxové plánovače, které předcházejí CFS, používají heuristiku k podpoře spravedlivého zacházení s interaktivními úkoly s ohledem na plánování. CFS zaujímá zcela odlišný přístup tím, že nechává fakta o vruntime mluvit hlavně sama za sebe, což náhodou podporuje férovost spánku . Interaktivní úloha má ze své podstaty tendenci hodně spát v tom smyslu, že čeká na uživatelské vstupy, a tak se stává I/O-vázanou; proto má taková úloha tendenci mít relativně nízkou dobu běhu, což má tendenci přesunout úlohu na začátek plánovací čáry.

Speciální funkce

CFS podporuje symetrické multiprocesování (SMP), ve kterém může být spuštěn jakýkoli proces (ať už jádro nebo uživatel) na libovolném procesoru. Přesto konfigurovatelné plánovací domény lze použít k seskupení procesorů pro vyrovnávání zátěže nebo dokonce segregaci. Pokud několik procesorů sdílí stejnou plánovací politiku, pak je možnost vyvažování zátěže mezi nimi; pokud má konkrétní procesor plánovací politiku odlišnou od ostatních, pak by tento procesor byl s ohledem na plánování oddělený od ostatních.

Konfigurovatelné skupiny plánování jsou další funkcí CFS. Jako příklad zvažte webový server Nginx, který běží na mém stolním počítači. Při spuštění má tento server hlavní proces a čtyři pracovní procesy, které fungují jako obslužné rutiny požadavků HTTP. Pro jakýkoli požadavek HTTP je konkrétní pracovník, který požadavek zpracovává, irelevantní; záleží pouze na tom, aby byl požadavek vyřízen včas, a tak tito čtyři pracovníci společně poskytnou fond, ze kterého mohou čerpat správce úloh, jakmile přijdou požadavky. Zdá se tedy spravedlivé zacházet se čtyřmi pracovníky Nginx spíše jako se skupinou než jako jednotlivci pro účely plánování a k tomu lze použít skupinu plánování. Čtyři pracovníci Nginx by mohli být nakonfigurováni tak, aby mezi sebou měli jeden vruntime spíše než jednotlivé vruntime. Konfigurace se provádí tradičním linuxovým způsobem prostřednictvím souborů. Pro sdílení vruntime soubor s názvem cpu .sdílí , s podrobnostmi zadanými prostřednictvím známých příkazů shellu.

Jak již bylo zmíněno dříve, Linux podporuje třídy plánování takže různé plánovací politiky spolu s jejich implementačními algoritmy mohou koexistovat na stejné platformě. Třída plánování je implementována jako modul kódu v jazyce C. CFS, dosud popsaná třída plánování, je SCHED_NORMAL . Existují také třídy plánování speciálně pro úkoly v reálném čase, SCHED_FIFO (první dovnitř, první ven) a SCHED_RR (koloběžka). Pod SCHED_FIFO , úkoly běží do dokončení; pod SCHED_RR , úkoly běží, dokud nevyčerpají pevně stanovený časový úsek a nejsou vyřazeny.

Implementace CFS

CFS vyžaduje efektivní datové struktury pro sledování informací o úkolech a vysoce výkonný kód pro generování plánů. Začněme ústředním pojmem plánování, runqueue . Jedná se o datovou strukturu, která představuje časovou osu pro naplánované úlohy. Navzdory názvu nemusí být runqueue implementována tradičním způsobem, jako seznam FIFO. CFS porušuje tradici používáním časově uspořádaného červeno-černého stromu jako runqueue. Datová struktura je pro danou úlohu vhodná, protože se jedná o samovyvažující binární vyhledávací strom s efektivním vložením a odebrat operace, které se provádějí v O(log N) čas, kde N je počet uzlů ve stromu. Strom je také vynikající datová struktura pro uspořádání entit do hierarchie založené na konkrétní vlastnosti, v tomto případě vruntime.

V CFS představují interní uzly stromu úlohy, které mají být naplánovány, a strom jako celek, stejně jako každá runqueue, představuje časovou osu pro provádění úlohy. Červeno-černé stromy jsou široce používány nad rámec plánování; například Java používá tuto datovou strukturu k implementaci své Stromové mapy .

V rámci CFS má každý procesor specifickou runqueu úloh a žádná úloha se nevyskytuje současně ve více než jedné runqueue. Každá runqueue je červeno-černý strom. Vnitřní uzly stromu představují úkoly nebo skupiny úkolů a tyto uzly jsou indexovány svými hodnotami vruntime, takže (ve stromu jako celku nebo v jakémkoli podstromu) mají interní uzly nalevo nižší hodnoty vruntime než ty napravo:

    25     ## 25 is a task vruntime

    /\

  17  29   ## 17 roots the left subtree, 29 the right one

  /\  ...

 5  19     ## and so on

...  \

     nil   ## leaf nodes are nil

Stručně řečeno, úlohy s nejnižším vruntime – a tedy s největší potřebou procesoru – se nacházejí někde v levém podstromu; úlohy s relativně vysokou dobou běhu se shromažďují ve správném podstromu. Preemptovaný úkol by se dostal do pravého podstromu, čímž by dal ostatním úkolům šanci posunout se ve stromu doleva. Úloha s nejmenší dobou běhu končí v levém (interním) uzlu stromu, což je tedy přední část runqueue.

Plánovač CFS má instanci C task_struct , chcete-li sledovat podrobné informace o každé úloze, která má být naplánována. Tato struktura vkládá sched_entity struktura, která zase obsahuje informace specifické pro plánování, zejména vruntime na úkol nebo skupinu úkolů:

struct task_struct {       /** info on a task **/

  ...

  struct sched_entity se;  /** vruntime, etc. **/

  ...

};

Červeno-černý strom je implementován známým způsobem C, s důrazem na ukazatele účinnosti. A cfs_rq instance struktury vkládá rb_root pole s názvem tasks_timeline , který ukazuje na kořen červeno-černého stromu. Každý z vnitřních uzlů stromu má ukazatele na nadřazený a dva podřízené uzly; listové uzly mají nulu jako jejich hodnotu.

CFS ilustruje, jak lze jednoduchý nápad – dát každému úkolu přiměřený podíl procesorových zdrojů – implementovat nenáročným, ale vysoce účinným způsobem. Stojí za to zopakovat, že CFS dosahuje spravedlivého a efektivního plánování bez tradičních artefaktů, jako jsou pevné časové úseky a explicitní priority úkolů. Snaha o ještě lepší plánovače samozřejmě pokračuje; v tuto chvíli je však CFS tak dobrý, jak jen může být pro všeobecné plánování procesorů.