Plánování (výpočetní) - Scheduling (computing)

V počítači je plánování akce přiřazování prostředků k plnění úkolů . Tyto prostředky mohou být procesory , síťové propojení nebo rozšiřující karty . Tyto úkoly mohou být nitě , procesy nebo datové toky .

Plánovací činnost je prováděna procesem zvaným plánovač . Plánovače jsou často navrženy tak, aby zaměstnávaly všechny počítačové zdroje (jako při vyrovnávání zatížení ), umožňovaly více uživatelům efektivně sdílet systémové prostředky nebo dosáhly cílové kvality služeb .

Plánování je zásadní pro samotný výpočet a je nedílnou součástí prováděcího modelu počítačového systému; koncepce plánování umožňuje mít počítačový multitasking s jedinou centrální procesorovou jednotkou (CPU).

Cíle

Plánovač se může zaměřit na jeden nebo více cílů, například:

• maximalizace propustnosti (celkové množství práce dokončené za časovou jednotku);
• minimalizace čekací doby (doba od chvíle, kdy se práce začne připravovat, až do prvního bodu, kdy začne provádění);
• minimalizace latence nebo doby odezvy (doba od přípravy práce do dokončení v případě dávkové aktivity nebo do doby, než systém odpoví a předá první výstup uživateli v případě interaktivní aktivity);
• maximalizace spravedlnosti (stejný čas CPU pro každý proces, nebo obecněji vhodné časy podle priority a pracovní zátěže každého procesu).

V praxi jsou tyto cíle často v rozporu (např. Propustnost versus latence), takže plánovač implementuje vhodný kompromis. Preference se měří jakýmkoli z výše uvedených problémů, v závislosti na potřebách a cílech uživatele.

V prostředích v reálném čase , jako jsou vestavěné systémy pro automatické řízení v průmyslu (například robotika ), musí plánovač také zajistit, aby procesy mohly dodržovat termíny ; to je zásadní pro udržení stability systému. Naplánované úlohy lze také distribuovat do vzdálených zařízení v síti a spravovat prostřednictvím administrativního back -endu.

Typy plánovačů operačního systému

Plánovač je modul operačního systému, který vybírá další úlohy, které mají být přijaty do systému, a další proces, který se má spustit. Operační systémy mohou obsahovat až tři různé typy plánovačů: dlouhodobý plánovač (také známý jako plánovač přijetí nebo plánovač na vysoké úrovni), střednědobý nebo střednědobý plánovač a krátkodobý plánovač . Názvy naznačují relativní frekvenci, s jakou jsou jejich funkce prováděny.

Plánovač procesů

Plánovač procesů je součástí operačního systému, který rozhoduje, který proces se spustí v určitém časovém okamžiku. Obvykle má schopnost pozastavit běžící proces, přesunout jej do zadní části běžící fronty a zahájit nový proces; takový plánovač je známý jako preemptivní plánovač , jinak je to kooperativní plánovač .

Podle toho, jak často se musí rozhodovat, rozlišujeme mezi „dlouhodobým plánováním“, „střednědobým plánováním“ a „krátkodobým plánováním“.

Dlouhodobé plánování

Dlouhodobé plánovač , nebo vstupné plánovač rozhodne, které úlohy nebo procesy, které mají být přijaty do připravené fronty (v hlavní paměti); to znamená, že když je proveden pokus o spuštění programu, jeho přijetí do sady aktuálně provádějících procesů je buď autorizováno, nebo zpožděno dlouhodobým plánovačem. Tento plánovač tedy určuje, jaké procesy mají být spuštěny v systému, a stupeň souběžnosti, která má být podporována současně-zda se má provádět souběžně mnoho nebo málo procesů a jak je rozděleno mezi I/O intenzivní a CPU -je třeba zvládnout intenzivní procesy. Za řízení stupně multiprogramování je zodpovědný dlouhodobý plánovač.

Obecně lze většinu procesů popsat jako vázané na I/O nebo na CPU . Proces vázaný na I/O je proces, který tráví více času I/O, než tráví výpočty. Naproti tomu proces vázaný na CPU generuje požadavky na I/O jen zřídka a využívá více času na výpočty. Je důležité, aby dlouhodobý plánovač vybral dobrou kombinaci procesů procesů vázaných na I/O a CPU. Pokud jsou všechny procesy vázány na I/O, připravená fronta bude téměř vždy prázdná a krátkodobý plánovač bude mít málo práce. Na druhou stranu, pokud jsou všechny procesy vázány na CPU, bude čekací fronta I/O téměř vždy prázdná, zařízení zůstanou nevyužita a systém bude opět nevyvážený. Systém s nejlepším výkonem tak bude mít kombinaci procesů vázaných na CPU a I/O. V moderních operačních systémech se to používá k zajištění toho, aby procesy v reálném čase dostaly dostatek času CPU na dokončení svých úkolů.

Dlouhodobé plánování je také důležité v rozsáhlých systémech, jako jsou systémy dávkového zpracování , počítačové klastry , superpočítače a farmy s vykreslením . Například v souběžných systémů , coscheduling interagujících procesů je často nutné, aby se zabránilo zablokování v důsledku čekání na sobě. V těchto případech se k podpoře těchto funkcí obvykle používá speciální účelový software plánovače úloh , navíc k jakékoli základní podpoře plánování příjmu v operačním systému.

Některé operační systémy umožňují přidávání nových úkolů pouze v případě, že je jisté, že je stále možné dodržet všechny termíny v reálném čase. Specifický heuristický algoritmus používaný operačním systémem k přijímání nebo odmítání nových úkolů je mechanismus řízení přijetí .

Střednědobé plánování

Medium-term plánovač dočasně odebere procesy z hlavní paměti a umístí je do sekundární paměti (jako například pevný disk ) nebo naopak, který je běžně označován jako „vyměňovat“ nebo „odkládání in“ (také nesprávně jako " klávesnici out “nebo„ paging in “). Střednědobý plánovač se může rozhodnout vyměnit proces, který již nějakou dobu není aktivní, nebo proces, který má nízkou prioritu, nebo proces, u kterého často dochází k chybám na stránce , nebo proces, který zabírá velké množství paměť, aby se uvolnila hlavní paměť pro jiné procesy, proces se vrátí zpět později, když je k dispozici více paměti nebo když byl proces odblokován a již nečeká na zdroj. [Stallings, 396] [Stallings, 370]

V mnoha dnešních systémech (v těch, které podporují mapování virtuálního adresního prostoru na sekundární úložiště jiné než odkládací soubor) může střednědobý plánovač ve skutečnosti plnit roli dlouhodobého plánovače tím, že binární soubory považuje za „vyměněné procesy“ na jejich provedení. Tímto způsobem, když je požadován segment binárního souboru, může být zaměněn na vyžádání nebo „líně načten“, [Stallings, 394] také nazýván stránkování poptávky .

Krátkodobé plánování

Krátkodobé plánovač (také známý jako plánovač CPU ) rozhoduje, které z pohotovosti v paměti procesů má být vykonán (přidělena CPU) po hodinovém přerušení , I / O přerušení, operační systém volání nebo jiná forma ze signálu . Krátkodobý plánovač tak činí rozhodnutí o plánování mnohem častěji než dlouhodobí nebo střednědobí plánovači-rozhodnutí o plánování bude nutné učinit minimálně po každém časovém úseku, a ta jsou velmi krátká. Tento plánovač může být preemptivní , což znamená, že je schopen násilně odebrat procesy z CPU, když se rozhodne přidělit tento procesor jinému procesu, nebo nepreemptivní (také známý jako „dobrovolný“ nebo „kooperativní“), ve kterém v případě, že plánovač není schopen „vynutit“ procesy mimo CPU.

Preemptivní plánovač se spoléhá na programovatelný intervalový časovač, který vyvolá obslužný program přerušení, který běží v režimu jádra a implementuje funkci plánování.

Odesílatel

Další komponentou, která je zapojena do funkce plánování CPU, je dispečer, což je modul, který poskytuje kontrolu nad procesem vybraným krátkodobým plánovačem. Ovládání dostává v režimu jádra v důsledku přerušení nebo systémového volání. Funkce dispečera zahrnují následující:

• Přepínače kontextu , ve kterých dispečer ukládá stav (také známý jako kontext ) procesu nebo vlákna, které bylo dříve spuštěno; dispečer poté načte počáteční nebo dříve uložený stav nového procesu.
• Přepnutí do uživatelského režimu.
• Skočením na správné místo v uživatelském programu restartujete program označený jeho novým stavem.

Dispečer by měl být co nejrychlejší, protože je vyvolán při každém přepnutí procesu. Během kontextových přepínačů je procesor po zlomek času prakticky nečinný, proto je třeba se vyhnout zbytečným kontextovým přepínačům. Doba, po kterou dispečer zastaví jeden proces a zahájí další, se nazývá latence odeslání .

Plánování disciplín

Plánovací disciplína (nazývaný také plánovací politikou nebo plánovací algoritmus ) je algoritmus použitý pro rozdělování prostředků mezi stranami, které současně i asynchronně požadují je. Disciplíny plánování se používají ve směrovačích (ke zpracování paketového provozu) i v operačních systémech (ke sdílení času CPU mezi vlákny i procesy ), diskové jednotky ( plánování I/O ), tiskárny ( zařazovací služba tisku ), většina vestavěných systémů atd. .

Hlavními účely plánovacích algoritmů je minimalizovat hladovění zdrojů a zajistit spravedlnost mezi stranami využívajícími zdroje. Plánování se zabývá problémem rozhodnutí, kterému z nevyřízených požadavků budou přiděleny zdroje. Existuje mnoho různých plánovacích algoritmů. V této sekci představujeme několik z nich.

V počítačových sítích s přepínáním paketů a dalším statistickém multiplexování se pojem plánovací algoritmus používá jako alternativa k frontování datových paketů, kdo dřív přijde , ten dřív mele.

Nejjednoduššími plánovacími algoritmy s nejlepším úsilím jsou round-robin , spravedlivé fronty ( algoritmus max-min spravedlivého plánování), proporcionálně spravedlivé plánování a maximální propustnost . Pokud je nabízena diferencovaná nebo zaručená kvalita služeb , na rozdíl od komunikace nejlepšího úsilí, lze použít vážené spravedlivé fronty .

V pokročilých paketových rádiových bezdrátových sítích, jako je HSDPA (vysokorychlostní downlink paketový přístup) 3,5G mobilní systém, lze pro využití informací o stavu kanálu použít plánování závislé na kanálu . Pokud jsou podmínky kanálu příznivé, je možné zvýšit propustnost a spektrální účinnost systému . V ještě pokročilejších systémech, jako je LTE , je plánování kombinováno dynamickým přidělováním paketů po paketech závislým na kanálu nebo přiřazením více nosných OFDMA nebo jiných vyrovnávacích komponent frekvenční oblasti uživatelům, kteří je mohou nejlépe využít.

Kdo dřív přijde, ten dřív mele

First in, first out ( FIFO ), také známý jako kdo dřív přijde, ten dřív mele (FCFS), je nejjednodušší plánovací algoritmus. FIFO jednoduše zařazuje procesy do fronty v pořadí, v jakém dorazí do připravené fronty. To se běžně používá pro a fronta úloh , například jak je znázorněno v této části.

• Vzhledem k tomu, že k přepínání kontextu dochází pouze po ukončení procesu a není nutná žádná reorganizace fronty procesů, je režijní náklady na plánování minimální.
• Propustnost může být nízká, protože dlouhé procesy mohou držet CPU, což způsobí, že krátké procesy čekají dlouhou dobu (známý jako efekt konvoje).
• Žádné hladovění, protože každý proces dostane šanci být proveden po určité době.
• Doba obratu , čekací doba a doba odezvy závisí na pořadí jejich příjezdu a mohou být vysoké ze stejných důvodů výše.
• Nedochází k žádnému stanovení priorit, takže tento systém má problémy s dodržováním termínů procesu.
• Nedostatek stanovení priorit znamená, že dokud se každý proces nakonec dokončí, nehrozí hladovění. V prostředí, kde se některé procesy nemusí dokončit, může dojít k hladovění.
• Je založen na frontách.

Prioritní plánování

Earlest deadline first (EDF) or less time to go je dynamický plánovací algoritmus používaný v operačních systémech v reálném čase k umístění procesů do prioritní fronty. Kdykoli dojde k události plánování (úkol skončí, nový úkol je vydán atd.), Bude ve frontě vyhledán proces, který se blíží jeho termínu, který bude dalším naplánovaným na spuštění.

Nejprve nejkratší zbývající čas

Podobné jako nejkratší zaměstnání jako první (SJF). Díky této strategii plánovač uspořádá procesy s nejmenším odhadovaným časem zpracování, který zbývá jako další ve frontě. To vyžaduje pokročilé znalosti nebo odhady doby potřebné k dokončení procesu.

• Pokud během provádění jiného procesu přijde kratší proces, aktuálně spuštěný proces se přeruší (známý jako preemption) a tento proces se rozdělí na dva samostatné výpočetní bloky. To vytváří přebytečnou režii prostřednictvím dalšího přepínání kontextu. Plánovač musí také umístit každý příchozí proces na konkrétní místo ve frontě, čímž vytvoří další režii.
• Tento algoritmus je navržen pro maximální propustnost ve většině scénářů.
• Čekací doba a doba odezvy se zvyšují se zvyšujícími se výpočetními požadavky procesu. Vzhledem k tomu, že doba obratu je založena na době čekání plus době zpracování, delší procesy jsou tím výrazně ovlivněny. Celková čekací doba je menší než u FIFO, protože žádný proces nemusí čekat na ukončení nejdelšího procesu.
• Zvláštní pozornost není věnována termínům, programátor se může pokusit zkrátit procesy s termíny co nejkratší.
• Hladovění je možné, zejména v rušném systému, kde je spuštěno mnoho malých procesů.
• Abychom mohli tuto zásadu používat, měli bychom mít alespoň dva procesy s různou prioritou

Přednostní plánování s opravenou prioritou

Operační systém každému procesu přiřadí pevnou prioritu a plánovač uspořádá procesy do připravené fronty v pořadí podle jejich priority. Procesy s nižší prioritou se přeruší příchozími procesy s vyšší prioritou.

• Režie není minimální ani není významná.
• FPPS nemá žádnou zvláštní výhodu, pokud jde o propustnost oproti plánování FIFO.
• Pokud je počet žebříčků omezený, lze jej charakterizovat jako kolekci FIFO front, jednu pro každé pořadí priorit. Procesy ve frontách s nižší prioritou jsou vybrány pouze tehdy, jsou-li všechny fronty s vyšší prioritou prázdné.
• Čekací doba a doba odezvy závisí na prioritě procesu. Procesy s vyšší prioritou mají kratší čekací doby a dobu odezvy.
• Termíny lze dodržet tím, že procesům s termíny bude přidělena vyšší priorita.
• Hladovění procesů s nižší prioritou je možné s velkým počtem procesů s vysokou prioritou, které stojí ve frontě na čas CPU.

Plánování každý s každým

Plánovač přiřazuje každému procesu pevnou časovou jednotku a cykluje je. Pokud se proces dokončí v rámci tohoto časového úseku, bude ukončen, jinak bude naplánován poté, co dá šanci všem ostatním procesům.

• Plánování RR zahrnuje rozsáhlou režii, zejména s malou časovou jednotkou.
• Vyvážená propustnost mezi FCFS/ FIFO a SJF/ SRTF, kratší úlohy jsou dokončeny rychleji než ve FIFO a delší procesy jsou dokončeny rychleji než v SJF.
• Dobrá průměrná doba odezvy, čekací doba závisí na počtu procesů a ne na průměrné délce procesu.
• Kvůli vysokým čekacím dobám se v čistě RR systému jen zřídka dodržují termíny.
• Hladovění nikdy nemůže nastat, protože není dána žádná priorita. Pořadí alokace časové jednotky je založeno na době příjezdu procesu, podobně jako u FIFO.
• Pokud je Time-Slice velký, stane se FCFS /FIFO, nebo pokud je krátký, pak se stane SJF /SRTF.

Víceúrovňové plánování front

Toho se využívá v situacích, kdy jsou procesy snadno rozděleny do různých skupin. Společné dělení je například mezi procesy v popředí (interaktivní) a procesy na pozadí (dávkové). Tyto dva typy procesů mají různé požadavky na dobu odezvy, a proto mohou mít různé potřeby plánování. Je velmi užitečný při problémech se sdílenou pamětí .

Plánovače šetřící práci

Plánovač práce nenáročných je plánovač, který se vždy snaží udržet plánované prostředky obsazeno, pokud jsou předkládány zaměstnání připraveni být naplánováno. Naproti tomu nepracovní plánovač šetřící je plánovač, který v některých případech může nechat naplánované prostředky nečinné navzdory přítomnosti úloh připravených k naplánování.

Problémy s plánováním optimalizace

Existuje několik problémů s plánováním, ve kterých je cílem rozhodnout, která úloha jde v kterou dobu na kterou stanici, takže celkový rozpětí je minimalizováno:

• Plánování dílny  - existuje n úloh a m identických stanic. Každá úloha by měla být provedena na jednom počítači. To je obvykle považováno za online problém.
• Plánování otevřeného obchodu  -existuje n úloh a m různých stanic. Každá práce by měla strávit nějaký čas na každé stanici, ve volném pořadí.
• Plánování toku obchodů  - existuje n úloh a m různých stanic. Každá práce by měla strávit nějaký čas na každé stanici, ve předem stanoveném pořadí.

Ruční plánování

Velmi běžnou metodou ve vestavěných systémech je ruční plánování úloh. To lze například provést časově multiplexovaným způsobem. Někdy je jádro rozděleno na tři nebo více částí: Manuální plánování, preemptivní a přerušovací úroveň. Přesné metody pro plánování úloh jsou často proprietární.

• Žádné problémy s hladověním zdrojů
• Velmi vysoká předvídatelnost; umožňuje implementaci tvrdých systémů v reálném čase
• Téměř žádná režie
• Nemusí být optimální pro všechny aplikace
• Účinnost je zcela závislá na implementaci

Volba plánovacího algoritmu

Při navrhování operačního systému musí programátor zvážit, který plánovací algoritmus bude nejlépe fungovat pro použití, které systém uvidí. Neexistuje žádný univerzální „nejlepší“ plánovací algoritmus a mnoho operačních systémů používá rozšířené nebo kombinace výše uvedených plánovacích algoritmů.

Například Windows NT /XP /Vista používá víceúrovňovou frontu zpětné vazby , kombinaci preemptivního plánování s pevnou prioritou, každý s každým a algoritmy první dovnitř, první ven. V tomto systému mohou vlákna dynamicky zvyšovat nebo snižovat prioritu v závislosti na tom, zda již byla opravena, nebo zda čekala rozsáhle. Každá prioritní úroveň je reprezentována vlastní frontou, přičemž každý s každým je naplánováno mezi vlákna s vysokou prioritou a FIFO mezi vlákna s nižší prioritou. V tomto smyslu je doba odezvy pro většinu vláken krátká a krátká, ale kritická systémová vlákna se dokončí velmi rychle. Protože vlákna mohou ve frontě s nejvyšší prioritou používat pouze jednu časovou jednotku každý s každým, může být hladovění problémem pro vlákna s vyšší prioritou.

Implementace plánovače procesů operačního systému

Použitý algoritmus může být stejně jednoduchý jako každý s každým, ve kterém je každému procesu v cyklovacím seznamu přidělen stejný čas (například 1 ms, obvykle mezi 1 ms a 100 ms). Proces A tedy probíhá po dobu 1 ms, poté proces B, poté proces C a poté zpět do procesu A.

Pokročilejší algoritmy zohledňují prioritu procesu nebo jeho důležitost. To umožňuje některým procesům používat více času než jiné procesy. Jádro vždy používá jakékoli prostředky, které potřebuje k zajištění správného fungování systému, a lze tedy říci, že má nekonečnou prioritu. V systémech SMP se má za to, že afinita procesoru zvyšuje celkový výkon systému, i když to může způsobit pomalejší běh samotného procesu. To obecně zlepšuje výkon snížením mezipaměti mezipaměti .

OS/360 a nástupci

IBM OS/360 byl k dispozici se třemi různými plánovači. Rozdíly byly takové, že varianty byly často považovány za tři různé operační systémy:

• Možnost Single Sequential Scheduler , známá také jako primární řídicí program (PCP), zajišťovala sekvenční spouštění jednoho proudu úloh.
• Možnost vícenásobného sekvenčního plánovače , známá jako multiprogramování s pevným počtem úloh (MFT), zajišťovala provádění více souběžných úloh. Provedení se řídilo prioritou, která měla pro každý stream výchozí hodnotu nebo ji bylo možné požadovat samostatně pro každou úlohu. MFT verze II přidal dílčí úkoly (vlákna), které se prováděly s prioritou na základě priority rodičovské úlohy. Každý proud úlohy definoval maximální velikost paměti, kterou by mohla použít jakákoli úloha v tomto proudu.
• Možnost Multiple Priority Schedulers nebo Multiprogramming with a Variable Number of Tasks (MVT) představovala dílčí úkoly od začátku; každá úloha požadovala před spuštěním prioritu a paměť, kterou vyžadovala.

Pozdější verze MVS virtuálního úložiště přidaly do plánovače funkci Workload Manager , která naplánuje prostředky procesoru podle propracovaného schématu definovaného instalací.

Okna

Velmi rané systémy MS-DOS a Microsoft Windows nebyly multitaskingové a jako takové neobsahovaly plánovač. Windows 3.1x používal nepředvídatelný plánovač, což znamená, že nepřerušoval programy. Spoléhalo se na to, že program skončí nebo řekne OS, že nepotřebuje procesor, aby mohl přejít na jiný proces. Toto se obvykle nazývá kooperativní multitasking. Windows 95 představil základní preventivní plánovač; nicméně, pro starší podporu se rozhodl nechat 16bitové aplikace běžet bez preemption.

Operační systémy založené na Windows NT používají víceúrovňovou frontu zpětné vazby. Je definováno 32 úrovní priority, od 0 do 31, přičemž priority 0 až 15 jsou „normální“ priority a priority 16 až 31 jsou měkké priority v reálném čase, které vyžadují přiřazení oprávnění. 0 je vyhrazeno pro operační systém. Uživatelská rozhraní a rozhraní API fungují s prioritními třídami pro proces a vlákna v procesu, které jsou pak spojeny systémem do úrovně absolutní priority.

Jádro může změnit úroveň priority vlákna v závislosti na využití I/O a CPU a na tom, zda je interaktivní (tj. Přijímá a reaguje na vstup od lidí), čímž zvyšuje prioritu interaktivních a I/O ohraničených procesů a snižuje prioritu Procesy vázané na CPU, aby se zvýšila odezva interaktivních aplikací. Plánovač byl v systému Windows Vista upraven tak, aby používal registr čítačů cyklů moderních procesorů ke sledování přesného počtu cyklů CPU, které vlákno provedlo, a nikoli pouze pomocí rutiny přerušení intervalového časovače. Vista také používá prioritní plánovač pro I/O frontu, takže defragmentace disku a další podobné programy neruší operace v popředí.

Klasický Mac OS a macOS

Mac OS 9 používá kooperativní plánování pro vlákna, kde jeden proces řídí více kooperativních vláken, a také poskytuje preemptivní plánování pro úlohy s více procesy. Jádro naplánuje víceprocesové úlohy pomocí algoritmu preemptivního plánování. Všechny procesy Process Manager běží v rámci speciální úlohy více procesů, která se nazývá „modrý úkol“. Tyto procesy jsou naplánovány kooperativně pomocí algoritmu plánování každý s každým ; proces poskytuje kontrolu nad procesorem jinému procesu výslovným voláním blokovací funkce , jako je WaitNextEvent. Každý proces má svou vlastní kopii Správce vláken, který naplánuje vlákna tohoto procesu kooperativně; vlákno poskytuje kontrolu nad procesorem do jiného vlákna voláním YieldToAnyThreadnebo YieldToThread.

macOS používá víceúrovňovou frontu zpětné vazby se čtyřmi prioritními pásmy pro vlákna-normální, s vysokou prioritou systému, pouze v režimu jádra a v reálném čase. Vlákna jsou naplánována preventivně; macOS také podporuje kooperativně naplánovaná vlákna při implementaci Správce vláken v Carbonu .

AIX

V systému AIX verze 4 existují tři možné hodnoty pro zásady plánování vláken:

• First In, First Out: Jakmile je vlákno s touto zásadou naplánováno, spustí se do dokončení, pokud není blokováno, dobrovolně poskytuje kontrolu nad CPU nebo se vlákno s vyšší prioritou stane odesílateelným. Zásady plánování FIFO mohou mít pouze vlákna s pevnou prioritou.
• Round Robin: To je podobné schématu AIX verze 3 plánovače round-robin založeného na 10 ms časových úsecích. Když vlákno RR má kontrolu na konci časového úseku, přesune se na konec fronty odesílatelných vláken s jeho prioritou. Zásady plánování Round Robin mohou mít pouze vlákna s pevnou prioritou.
• DALŠÍ: Tyto zásady definuje POSIX1003.4a jako implementaci. V systému AIX verze 4 je tato zásada definována jako ekvivalentní RR, kromě toho, že platí pro vlákna s nefixovanou prioritou. Přepočet hodnoty priority spuštěného vlákna při každém přerušení hodin znamená, že vlákno může ztratit kontrolu, protože jeho hodnota priority stoupla nad hodnotu jiného odesílatelného vlákna. Toto je chování AIX verze 3.

Vlákna jsou primárně zajímavá pro aplikace, které v současné době sestávají z několika asynchronních procesů. Pokud tyto aplikace převedete na vícevláknovou strukturu, mohou způsobit menší zatížení systému.

AIX 5 implementuje následující zásady plánování: FIFO, Round Robin a Fair Round Robin. Zásady FIFO mají tři různé implementace: FIFO, FIFO2 a FIFO3. Zásady kruhového hodnocení jsou v systému AIX pojmenovány SCHED_RR a spravedlivé kruhové hodnocení se nazývá SCHED_OTHER.

Linux

Linux 2.4

V Linuxu 2.4 byl použit plánovač O (n) s víceúrovňovou frontou zpětné vazby s úrovněmi priority od 0 do 140; 0–99 je vyhrazeno pro úkoly v reálném čase a 100–140 je považováno za pěkné úrovně úkolů. U úloh v reálném čase bylo časové kvantum pro přepínací procesy přibližně 200 ms a pro pěkné úkoly přibližně 10 ms. Plánovač prošel frontou spuštění všech připravených procesů, přičemž nechal procesy s nejvyšší prioritou projít nejprve a projít jejich časovými úseky, po kterých budou zařazeni do fronty, jejíž platnost vypršela. Když je aktivní fronta prázdná, prošlá fronta se stane aktivní frontou a naopak.

Některé podnikové distribuce Linuxu, jako je SUSE Linux Enterprise Server, však tento plánovač nahradily backportem plánovače O (1) (který udržoval Alan Cox ve své řadě Linux 2.4-ac Kernel) do jádra Linux 2.4 používaného distribucí .

Linux 2.6.0 až Linux 2.6.22

Ve verzích 2.6.0 až 2.6.22 používalo jádro plánovač O (1) vyvinutý Ingo Molnarem a mnoha dalšími vývojáři jádra během vývoje Linuxu 2.5. Pro mnoho jader v časovém rámci vyvinul Con Kolivas opravné sady, které zlepšovaly interaktivitu s tímto plánovačem nebo jej dokonce nahradily svými vlastními plánovači.

Od Linuxu 2.6.23

Práce Con Kolivase, nejvýrazněji jeho implementace „ spravedlivého plánování “ s názvem „Rotating Staircase Deadline“, inspirovala Ingo Molnára k vývoji Úplně spravedlivého plánovače jako náhrady za dřívější plánovač O (1) , přičemž připsal Kolivasovi své oznámení. CFS je první implementací plánovače spravedlivých front ve frontě, který se široce používá v operačním systému pro obecné účely.

Zcela Fair Scheduler (CFS) používá dobře studoval klasickou plánovací algoritmus zvaný fair queuing původně vynalezen pro paketové sítě . Spravedlivé fronty byly dříve použity na plánování CPU pod názvem krokové plánování . Férový plánovač CFS ve frontě má složitost plánování , kde je počet úkolů ve frontě . Výběr úkolu lze provádět v konstantním čase, ale opětovné vložení úkolu po jeho spuštění vyžaduje operace, protože fronta spuštění je implementována jako červeno -černý strom . ${\ displaystyle O (logN)}$${\ displaystyle N}$${\ displaystyle O (logN)}$

Brain Fuck Scheduler , také vytvořil Con Kolivas, je alternativou k CFS.

FreeBSD

FreeBSD používá víceúrovňovou frontu zpětné vazby s prioritami v rozmezí 0–255. 0–63 je vyhrazeno pro přerušení, 64–127 pro horní polovinu jádra, 128–159 pro uživatelská vlákna v reálném čase, 160–223 pro časově sdílená uživatelská vlákna a 224–255 pro nečinná uživatelská vlákna. Stejně jako Linux používá aktivní nastavení fronty, ale má také frontu nečinnosti.

NetBSD

NetBSD používá víceúrovňovou frontu zpětné vazby s prioritami v rozmezí 0–223. 0–63 je vyhrazeno pro časově sdílená vlákna (výchozí, zásada SCHED_OTHER), 64–95 pro uživatelská vlákna, která vstoupila do prostoru jádra , 96–128 pro vlákna jádra , 128–191 pro vlákna v reálném čase pro uživatele (zásady SCHED_FIFO a SCHED_RR) a 192–223 pro softwarová přerušení .

Solaris

Solaris používá víceúrovňovou frontu zpětné vazby s prioritami v rozmezí 0 až 169. Priority 0–59 jsou vyhrazeny pro časově sdílená vlákna, 60–99 pro systémová vlákna, 100–159 pro vlákna v reálném čase a 160–169 pro přerušení s nízkou prioritou . Na rozdíl od Linuxu, když se proces provádí pomocí jeho časového kvanta, dostane novou prioritu a zařadí se zpět do fronty. Solaris 9 představil dvě nové třídy plánování, a to třídu s pevnou prioritou a třídu spravedlivých akcií. Vlákna s pevnou prioritou mají stejný rozsah priorit jako třída sdílení času, ale jejich priority nejsou dynamicky upravovány. Třída spravedlivého plánování používá sdílené jednotky CPU k upřednostnění vláken pro rozhodování o plánování. Sdílené CPU označují oprávnění k prostředkům CPU. Jsou alokovány do sady procesů, které jsou souhrnně označovány jako projekt.

souhrn

Operační systém	Preemption	Algoritmus
Amiga OS	Ano	Prioritu Round-Robin Scheduling
FreeBSD	Ano	Víceúrovňová fronta zpětné vazby
Linuxové jádro před 2.6.0	Ano	Víceúrovňová fronta zpětné vazby
Linuxové jádro 2.6.0–2.6.23	Ano	O (1) plánovač
Linuxové jádro po 2.6.23	Ano	Naprosto spravedlivý plánovač
klasický Mac OS před 9	Žádný	Kooperativní plánovač
Mac OS 9	Nějaký	Preemptivní plánovač pro úkoly MP a kooperativní pro procesy a vlákna
Operační Systém Mac	Ano	Víceúrovňová fronta zpětné vazby
NetBSD	Ano	Víceúrovňová fronta zpětné vazby
Solaris	Ano	Víceúrovňová fronta zpětné vazby
Windows 3.1x	Žádný	Kooperativní plánovač
Windows 95 , 98 , Me	Polovina	Preemptivní plánovač pro 32bitové procesy a kooperativní pro 16bitové procesy
Windows NT (včetně 2000, XP, Vista, 7 a Server)	Ano	Víceúrovňová fronta zpětné vazby

Viz také

Poznámky

Reference

Další čtení

• Operační systémy: Three Easy Pieces od Remzi H. Arpaci-Dusseau a Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Příslušné kapitoly: Plánování: Úvod Víceúrovňová fronta zpětné vazby Plánování proporcionálního sdílení Plánování více procesorů
• Krátká diskuse o algoritmech plánování úloh
• Pochopení jádra Linuxu: Kapitola 10 Plánování procesů
• Kerneltrap: Články plánovače linuxového jádra
• Monitorování a ladění CPU AIX
• Úvod Joshe Aase do implementace plánovače Linux 2.6.8.1 CPU
• Peter Brucker, Sigrid Knust. Složitost výsledků pro problémy s plánováním [3]
• TORSCHE Scheduling Toolbox for Matlab je sada nástrojů pro plánování a grafové algoritmy.
• Průzkum plánování paketů mobilních sítí
• Rozsáhlá správa klastrů na Googlu s Borgem