Plánování CPU Algorithms in Operating Systems

Co je plánování CPU?

Plánování CPU je proces určování, který proces bude vlastnit CPU pro spuštění, zatímco jiný proces je pozastaven. Hlavním úkolem plánování CPU je zajistit, aby operační systém vždy, když CPU zůstane nečinný, vybral alespoň jeden z procesů dostupných ve frontě připravených ke spuštění. Proces výběru provádí plánovač CPU, který vybere jeden z procesů v paměti, které jsou připraveny ke spuštění.

Typy plánování CPU

Zde jsou dva druhy metod plánování:

Preemptivní plánování

V preemptivním plánování jsou úkoly většinou přiřazeny s jejich prioritami. Někdy je důležité spustit úlohu s vyšší prioritou před jinou úlohou s nižší prioritou, i když úloha s nižší prioritou stále běží. Úloha s nižší prioritou se nějakou dobu zdrží a obnoví se, jakmile úloha s vyšší prioritou dokončí své provádění.

Nepreemptivní plánování

V tomto typu metody plánování je CPU alokováno konkrétnímu procesu. Proces, který CPU zaměstnává, jej uvolní buď přepnutím kontextu, nebo ukončením. Je to jediná metoda, kterou lze použít napříč různými hardwarovými platformami, protože nevyžaduje speciální hardware (například časovač) jako preemptivní plánování.

Kdy je plánování preventivní nebo nepreventivní?

Pro určení, zda je plánování preemptivní nebo nepreemptivní, zvažte tyto čtyři parametry:

1. Proces se přepne z běžícího do čekajícího stavu.
2. Konkrétní proces se přepne ze stavu „běží“ do stavu „připraven“.
3. Konkrétní proces přepne ze stavu čekání do stavu připravenosti.
4. Proces dokončí své provádění a ukončí se.

Pokud platí pouze podmínky 1 a 4, plánování se nazývá nepreemptivní. Všechny ostatní situace plánování jsou preemptivní.

Důležité termíny pro plánování CPU

• Čas burstu/čas provedení: Čas potřebný k dokončení provedení procesu. Nazývá se také doba běhu.
• Čas příjezdu: Čas, kdy proces přejde do stavu připravenosti.
• Konečný čas: Čas, kdy je proces dokončen a systém ukončen.
• Multiprogramování: V paměti může být současně přítomno několik programů.
• Pracovní místa: Typ programu bez jakékoli interakce s uživatelem.
• Uživatel: Druh programu, který umožňuje interakci s uživatelem.
• Process: Reference, která se používá jak pro úlohu, tak pro uživatele.
• Cyklus prasknutí CPU/IO: Charakterizuje provádění procesů, které se střídá mezi aktivitou CPU a I/O. Časy CPU jsou obvykle kratší než časy I/O.

Kritéria plánování CPU

Plánovací algoritmus CPU se snaží maximalizovat a minimalizovat následující:

Maximalizovat

Využití CPU: Využití CPU je hlavním úkolem operačního systému, při kterém musí zajistit, aby CPU zůstalo co nejvíce vytížené. Může se pohybovat od 0 do 100 procent. U RTOS se však může pohybovat od 40 procent pro nízkoúrovňový systém do 90 procent pro vysokoúrovňový systém.

Propustnost: Počet procesů, které dokončí své spuštění za jednotku času, se nazývá propustnost. Takže když je CPU zaneprázdněno prováděním procesu, vykonává se práce a práce dokončená za jednotku času se nazývá propustnost.

Minimalizovat

Čekací doba: Doba čekání je doba, po kterou musí konkrétní proces čekat ve frontě připravenosti.

Dostupnost podpory: Jde o dobu od odeslání požadavku do doby, než je vydána první odpověď.

Doba obratu: Doba obratu je doba potřebná k provedení konkrétního procesu. Je to celkový čas strávený čekáním na přístup do paměti, čekáním ve frontě a prováděním na CPU. Období mezi časem odeslání procesu a časem dokončení je doba obratu.

Intervalový časovač

Přerušení časovačem je metoda, která úzce souvisí s preempcí. Když určitý proces získá přidělení CPU, může být časovač nastaven na zadaný interval. Jak přerušení časovače, tak preempce přinutí proces vrátit CPU před dokončením jeho shluku CPU.

Většina multiprogramovaných operačních systémů používá nějakou formu časovače, aby se zabránilo tomu, aby proces navždy zablokoval systém.

Co je to Dispečer?

Dispečer je modul, který zajišťuje řízení CPU procesu. Dispečer by měl být rychlý, aby mohl běžet při každém přepnutí kontextu. Latence dispečeru je doba, kterou plánovač CPU potřebuje k zastavení jednoho procesu a spuštění jiného.

Funkce vykonávané dispečerem:

• Přepínání kontextu.
• Přepínání do uživatelského režimu.
• Přesunutí na správné místo v nově načteném programu.

Typy plánování CPU Algorithms

Existuje především šest typů algoritmy plánování procesů:

1. Kdo dřív přijde, ten dřív mele (FCFS)
2. Plánování nejkratšího zaměstnání (SJF).
3. Nejkratší zbývající čas
4. Prioritní plánování
5. Plánování Round Robin
6. Víceúrovňové plánování fronty

Plánování Algorithms

Kdo dřív příjde ten dřív mele

FCFS je zkratka pro Kdo dřív příjde ten dřív meleJedná se o nejjednodušší a nejjednodušší algoritmus plánování CPU. V tomto typu algoritmu proces, který požaduje CPU, získá alokaci CPU jako první. Tuto metodu plánování lze spravovat pomocí fronty FIFO.

Jakmile proces vstoupí do fronty připravených procesů, jeho řídicí blok (PCB) je propojen s koncem fronty. Takže když se CPU uvolní, měl by být přiřazen procesu na začátku fronty.

Charakteristika metody FCFS

• Jedná se o nepreemptivní plánovací algoritmus.
• Úkoly jsou vždy prováděny podle zásady „kdo dřív přijde, je dřív na řadě“.
• Snadno se implementuje a používá.
• Tato metoda má však nízký výkon a obecná čekací doba je poměrně vysoká.

Nejkratší zbývající čas

Úplná forma SRT je Shortest Remaining Time (nejkratší zbývající čas). Je také známá jako preemptivní plánování SJF. V této metodě bude proces přidělen úkolu, který je nejblíže svému dokončení. Tato metoda zabraňuje tomu, aby novější proces ve stavu připravenosti zdržel dokončení staršího procesu.

Charakteristika metody plánování SRT

• Tato metoda se používá nejčastěji v dávkových prostředích, kde je třeba upřednostňovat krátké úlohy.
• Toto není ideální metoda pro implementaci ve sdíleném systému, kde není znám požadovaný čas CPU.
• Každý proces je spojen s délkou jeho dalšího zatížení CPU, takže operační systém používá tyto délky k naplánování procesu s co nejkratším možným časem.

Plánování podle priority

Prioritní plánování je metoda plánování procesů na základě priority. V této metodě plánovač vybírá úkoly, na kterých bude pracovat, podle jejich priority.

Plánování priorit také pomáhá operačnímu systému zahrnout přiřazování priorit. Procesy s vyšší prioritou se provádějí jako první, zatímco úlohy se stejnou prioritou se provádějí cyklicky neboli FCFS. Prioritu lze určit na základě paměťových požadavků, časových požadavků a dalších faktorů.

Round-Robin plánování

Round-Robin je jeden z nejstarších a nejjednodušších plánovacích algoritmů. Název tohoto algoritmu pochází z principu round-robin, kde každá osoba postupně dostává stejný podíl něčeho. Používá se nejčastěji pro plánování v multitaskingových systémech. Tato metoda pomáhá dosáhnout provádění procesů bez hladovění.

Charakteristika Round-Robin Scheduling

• Round Robin je hybridní model, který je řízen hodinami.
• Časový úsek přidělený pro zpracování konkrétního úkolu by měl být minimální. Může se však lišit v závislosti na procesu.
• Chová se jako systém sdílení času, který reaguje na každý proces v rámci specifického časového limitu.

Nejdříve nejkratší práce

SJF (Shortest Job First) je plánovací algoritmus, ve kterém je proces s nejkratší dobou provádění vybrán k dalšímu spuštění. Tato metoda plánování může být preemptivní nebo nepreemptivní. Výrazně zkracuje průměrnou dobu čekání pro ostatní procesy čekající na spuštění.

Charakteristika rozvrhu SJF

• Každá úloha je spojena s časovou jednotkou k dokončení.
• V této metodě, když je CPU k dispozici, se jako první provede další proces nebo úloha s nejkratší dobou dokončení.
• Je implementován s nepreemptivní politikou.
• Tento algoritmus je užitečný pro dávkové zpracování, kde čekání na dokončení úloh není kritické.
• Zlepšuje výkon úloh tím, že nejprve provádí kratší úlohy, které mají většinou kratší dobu odezvy.

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

Tento algoritmus rozděluje frontu připravených procesů do několika samostatných front. V této metodě jsou procesy přiřazovány do fronty na základě specifické vlastnosti procesu, jako je priorita procesu, velikost paměti atd.

Nejedná se však o nezávislý plánovací algoritmus, protože k plánování úloh je nutné použít jiné typy algoritmů.

Charakteristiky plánování víceúrovňových front

• Pro procesy se sdílenými charakteristikami by mělo být udržováno více front.
• Každá fronta může mít svůj vlastní samostatný plánovací algoritmus.
• Každé frontě jsou přiřazeny priority.

Účel plánovacího algoritmu

Zde jsou důvody pro použití plánovacího algoritmu:

• CPU používá plánování ke zlepšení své účinnosti.
• Pomáhá vám alokovat zdroje mezi konkurenčními procesy.
• Maximálního využití CPU lze dosáhnout multiprogramováním.
• Procesy, které mají být spuštěny, jsou uchovávány ve frontě připravenosti.

Nejčastější dotazy