Plánování procesů

Plánování procesů 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 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é , střednědobé a dlouhodobé . Název typu plánování vyjadřuje frekvenci, s jakou k ní dochází. +more 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í se označuje též jako plánování úloh je výběr, která úloha bude spuštěna. Má význam zejména u dávkového zpracování. +more 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.

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

Střednědobé plánování 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 . +more 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.

Krátkodobé plánování

Krátkodobé plánování se označuje též jako plánování procesoru ( - 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č 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):

# pokud některý běžící proces přejde do stavu blokovaný # pokud některý proces skončí # pokud je běžící proces převeden do stavu připravený # 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í. +more 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. +more nemůže násilně odebrat procesu přidělené systémové prostředky a nedrží tedy absolutní kontrolu nad počítačem. 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í, …). +more 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ů. +more 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. +more Kompletní uložení stavu procesu označujeme jako uložení kontextu a obnovení kontextu . 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 .

Tabulka popisu procesů (PCB)

Tabulka popisu procesů ( 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 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:

* 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 [url=://lwn. +morenet/Articles/224865/ * [[Take scheduling|"Take" Scheduling][Operační systém|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ů 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 * 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) -[/url]] * Two-level scheduling * Weighted fair queuing (WFQ) * Weighted least-connection scheduling * Weighted round robin (WRR) * Group Ratio Round-Robin: O(1) - http://www. +moreusenix. org/events/usenix05/tech/general/full_papers/caprita/caprita_html/index. html.

Literatura

[url=http://labe.felk.cvut.cz/~stepan/X33OSA/linux_cpu_scheduler.pdf]Understanding the Linux 2.6.8.1 CPU Scheduler[/url]

Reference

Kategorie:Operační systém