Plánování procesů

Plánování procesů (anglicky scheduling) je v informatice úkol jádra operačního systému, ve kterém je spuštěno více procesů najednou. Týká se tedy víceúlohových systémů podporujících multitasking anebo multithreading, které využívají paralelizmus anebo pseudoparalelizmus. Plánování procesů řeší výběr, kterému následujícímu procesu bude přidělen procesor a proces tak poběží, přičemž výběr je závislý na prioritách jednotlivých procesů a algoritmu, kterým výběr proběhne.

Běžné operační systémy (pro desktopové počítače) vyžadují, aby byla při přidělování procesoru jednotlivým procesům zachována jistá míra spravedlnosti. Operační systém reálného času (anglicky real-time operating system) vyžadují, aby navíc byly splněny dodatečné podmínky, například aby výběr byl preciznější, deterministický a pracoval se zárukami.

Druhy plánování procesů

Operační systém může podporovat až 3 druhy plánování procesů: krátkodobé (anglicky short-term), střednědobé (anglicky mid-term) a dlouhodobé (anglicky long-term).^[1] Název typu plánování vyjadřuje frekvenci, s jakou k ní dochází. Typy plánování též rozlišují, v jakém stavu procesu k němu dochází.

Dlouhodobé plánování

Dlouhodobé plánování (anglicky long-term) se označuje též jako plánování úloh (anglicky job scheduling) je výběr, která úloha bude spuštěna. Má význam zejména u dávkového zpracování. Jeho účelem je naplánovat spouštění úloh tak, aby byl počítač maximálně využit, například vhodného mixu úloh, které jsou náročné na I/O nebo CPU. V současné době není obvykle u desktopových systémů implementován, avšak je velmi důležitý u operačních systémů reálného času, protože systém by v případě spuštění více procesů, než může bezpečně zvládnout, nemohl plnit garantované limity.^[2]

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

Střednědobé plánování (anglicky mid-term) používají systémy s virtuální pamětí. Jde o výběr, který blokovaný nebo připravený proces bude odsunut z vnitřní paměti na pevný disk, je-li vnitřní paměti nedostatek (anglicky swapping out a swapping in). Je chybou považovat stránkování paměti za střednědobé plánování, protože v tomto případě se odkládá celý proces. Důvodem pro odložení procesu může být absence aktivity procesu, nízká priorita, časté výpadky stránek, odblokovaný proces, který již nečeká na systémové prostředky nebo alokace příliš velké části paměti, když je potřeba paměť pro jiné procesy.^[2]

Krátkodobé plánování

Krátkodobé plánování (anglicky short-term) se označuje též jako plánování procesoru (anglicky CPU scheduling – viz další odstavec), při němž se vybírá, kterému z připravených procesů bude přidělen procesor. Používá se ve všech víceúlohových systémech.

Plánování procesoru

Při plánování procesoru se v operačním systému plánovač (anglicky scheduler) rozhoduje, kterému procesu bude přidělen procesor, a tedy který proces v následujícím časovém úseku bude procesor počítače využívat pro svůj běh. K plánování procesoru dochází v následujících situacích (podrobnosti o stavech procesu viz článek o procesech):

1. pokud některý běžící proces přejde do stavu blokovaný
2. pokud některý proces skončí
3. pokud je běžící proces převeden do stavu připravený
4. pokud je některý proces převeden ze stavu blokovaný do stavu připravený

Preemptivnost

Pokud k plánování procesoru dochází jen v prvních dvou výše uvedených případech, označujeme takový operační systém (resp. plánovač procesů) jako nepreemptivní. Jinak se jedná o preemptivní plánování procesoru. Čtvrtý případ přeplánování používá operační systém reálného času.

Nepreemptivní

Dochází-li k plánování ve výše uvedených případech 1 až 2, jedná se o nepreemptivní plánování procesoru, u kterého musí operační systém vyčkat, až mu proces nabídne přeplánování procesoru speciálním voláním služby operačního systému. Tj. nemůže násilně odebrat procesu přidělené systémové prostředky a nedrží tedy absolutní kontrolu nad počítačem.^[2] Důvodem může být absence příslušných hardwarových možností procesoru (16bitové procesory x86) nebo nedostatečné využití schopností pokročilejšího procesoru operačním systémem (tj. systémy Microsoft Windows 3.x, avšak například OS/2 dokázal pokročilých schopností procesorů IA-32 využít).

Preemptivní

Dochází-li k plánování ve výše uvedených případech 1 až 3, jedná se o preemptivní plánování procesoru, u kterého je operační systém schopen kdykoliv procesu odebrat CPU, tj. drží si absolutní kontrolu nad počítačem a všemi prostředky, které procesům přiděluje (CPU, operační paměť, I/O zařízení, …). Dochází k němu zpravidla po uplynutí časového kvanta určeného pro běh procesu a je vyvoláno přerušením od časovače. Do této kategorie patří například všechny 32bitové systémy pro IBM PC kompatibilní počítače (Windows NT, Linux, macOS, …).

RTOS – operační systém reálného času

Čtvrtý případ plánování procesoru se používá zřídka, zejména u speciálních operačních systémů, jako je operační systém reálného času (RTOS).

Přepnutí kontextu

Ve víceúlohových systémech je obvykle k dispozici méně procesorů, než je procesů, které by měly zároveň běžet. Proto se u takových systémů využívá pseudoparalelismus, který umožňuje mít zdánlivě spuštěno zároveň více procesů. Procesy čekají ve frontě a postupně je jim na určitou dobu (tzv. časové kvantum) přidělován procesor. Je-li přepínání dostatečně rychlé, vzniká dojem, že procesy běží zároveň. K přepínání dochází zhruba 100–1000krát za sekundu (podle výkonu počítače nebo podle výše režie přepínání, kterou chceme obětovat ve prospěch plynulosti).

Při přepínání procesů je nutné, aby proces po opětovném spuštění pokračoval od stejného místa, ve kterém byl přerušen a aby v procesu až na časové zpoždění nebylo poznat, že k přerušení došlo. Z tohoto důvodu je nutné při přerušení vykonávání procesu (mezi dvěma libovolnými strojovými instrukcemi) uschovat kompletní stav procesoru a při opětovném přidělení procesoru stejnému procesu tento stav kompletně obnovit. Kompletní uložení stavu procesu označujeme jako uložení kontextu (anglicky context save) a obnovení kontextu (anglicky context restore). Při výměně procesů na procesoru dochází k uložení kontextu jednoho a obnovení kontextu druhého. Tuto činnost označujeme souhrnně jako změna kontextu (anglicky context switch).

Tabulka popisu procesů (PCB)

Tabulka popisu procesů (anglicky process control block, zkratka PCB) je datová struktura v jádře operačního systému, která uchovává data potřebná k běhu procesu. Každý proces má svoji PCB, která je využívána při změně kontextu (anglicky context switch) k uložení stavu procesu.

Strategie plánování procesoru

Strategie použitá pro výběr, kterému z připravených procesů bude přidělen procesor, může zohledňovat různá kritéria:^[1]

• spravedlnost – každý proces dostane spravedlivý díl času procesoru
• efektivita – udržovat maximální vytížení procesoru, případně jiné části systému
• čas odezvy – minimalizovat dobu odezvy pro interaktivní uživatele
• doba obrátky – minimalizovat dobu zpracování každé dávkové úlohy
• průchodnost – maximalizovat množství úloh zpracovaných za jednotku času

Příklady strategií plánování procesoru

Podle toho, které z výše uvedených kritérií bere tvůrce strategie plánování procesoru v úvahu a jakou jim přikládá váhu, se používají (a nadále vznikají) různé strategie. Používají se nejen v operačních systémech pro rozdělení času procesoru mezi jednotlivé procesy a thready, ale i pro prioritní směrování síťového provozu v routerech. Hlavním úkolem strategie je zamezit vyhladovění procesů (anglicky starvation) a zajistit spravedlivé rozdělení času procesoru.

• First In, First Out (FIFO), též známá jako First Come First Served (FCFS)
• Borrowed-Virtual-Time Scheduling (BVT)
• Completely Fair Scheduler (CFS)
• Critical Path Method of Scheduling
• Deadline-monotonic scheduling (DMS)
• Deficit round robin (DRR)
• Dominant Sequence Clustering (DSC)
• Earliest deadline first (EDF)
• Earliest eligible virtual deadline first scheduling (EEVDF), Linux od verze 6.6^[3]
• Elastic Round Robin
• Fair-share scheduling
• Gang scheduling
• Genetic Anticipatory
• Highest response ratio next (HRRN)
• Interval scheduling
• Last In, First Out (LIFO)
• Job Shop Scheduling (see Job shops)
• Least-connection scheduling
• Least slack time scheduling (LST)
• List scheduling
• Lottery Scheduling
• Multilevel queue
• Multilevel Feedback Queue
• Never queue scheduling
• O(1) scheduler
• Priority scheduling
• Proportional Share Scheduling
• Rate-monotonic scheduling (RMS)
• Round-robin scheduling (RR)
• Shortest expected delay scheduling
• Shortest job next (SJN)
• Shortest time remaining (STR)
• Staircase Deadline scheduler (SD) – http://lwn.net/Articles/224865/ (anglicky)
• "Take" Scheduling
• Two-level scheduling
• Weighted fair queuing (WFQ)
• Weighted least-connection scheduling
• Weighted round robin (WRR)
• Group Ratio Round-Robin: O(1) – http://www.usenix.org/events/usenix05/tech/general/full_papers/caprita/caprita_html/index.html (anglicky)

Literatura

• STALLINGS, William. Operating systems : internals and design principles. 5.. vyd. Upper Saddle River, N.J.: Pearson/Prentice Hall, 2005. 818 s. Dostupné online. ISBN 0-13-147954-7. 
• KOLÁŘ, Petr. Operační systémy [online]. Liberec: 2005-02-01 [cit. 2008-08-09]. Dostupné v archivu pořízeném dne 2009-03-13. 
• Understanding the Linux 2.6.8.1 CPU Scheduler^{[nedostupný zdroj]} (anglicky)

Reference