Plánování CPU Algorithms in Operating Systems

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 drží a obnoví se, když úloha s vyšší prioritou dokončí své provádění.

Nepreemptivní plánování

V tomto typu metody plánování je CPU přiděleno konkrétnímu procesu. Proces, který udržuje CPU zaneprázdněn, uvolní CPU buď přepnutím kontextu, nebo ukončením. Je to jediná metoda, kterou lze použít pro různé hardwarové platformy. To proto, že nepotřebuje speciální hardware (například časovač), jako je preemptivní plánování.

Kdy je plánování Preemptivní nebo Nepreemptivní?

Chcete-li určit, 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 z běžícího stavu do připraveného stavu.
3. Konkrétní proces se přepne ze stavu čekání do stavu připravenosti.
4. Proces dokončil své provádění a skončil.

Platí pouze podmínky 1 a 4, plánování se nazývá nepreemptivní.

Všechny ostatní plánování jsou preventivní.

Důležitá terminologie plánování CPU

• Čas burstu/čas provedení: Je to čas, který proces vyžaduje k dokončení realizace. Říká se tomu také doba běhu.
• Čas příjezdu: když se proces dostane do stavu připravenosti
• Konečný čas: po dokončení procesu a ukončení systému
• Multiprogramování: Řada programů, které mohou být v paměti současně.
• Pracovní místa: Je to typ programu bez jakékoli interakce uživatele.
• Uživatel: Je to druh programu s uživatelskou interakcí.
• Process: Je to reference, která se používá pro úlohu i uživatele.
• Cyklus prasknutí CPU/IO: Charakterizuje provádění procesu, které střídá činnost CPU a I/O. Časy CPU jsou obvykle kratší než čas 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, ve kterém se operační systém musí ujistit, že CPU zůstává co nejvíce zaneprázdněn. Může se pohybovat od 0 do 100 procent. U RTOS se však může pohybovat v rozmezí od 40 procent pro nízkoúrovňový a 90 procent pro vysokoúrovňový systém.

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

Minimalizovat

Čekací doba: Čekací doba je množství, které konkrétní proces potřebuje čekat ve frontě připravených položek.

Doba odezvy: Je to množství času, ve kterém byla žádost podána, dokud není předložena první odpověď.

Doba obratu: Doba obratu je doba potřebná k provedení určitého procesu. Je to výpočet celkového času stráveného čekáním na vstup do paměti, čekáním ve frontě a prováděním na CPU. Doba mezi okamžikem 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 víceprogramovaných operačních systémů používá nějakou formu časovače, aby se zabránilo procesu navždy svazovat systém.

Co je to Dispečer?

Jedná se o modul, který zajišťuje řízení CPU procesu. Dispečer by měl být rychlý, aby mohl běžet na každém přepínači kontextu. Latence odeslání je množství času, které potřebuje plánovač CPU k zastavení jednoho procesu a spuštění dalšího.

Funkce prováděné dispečerem:

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

Typy algoritmu plánování CPU

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

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

Kdo dřív přijde, ten dřív mele je plná forma FCFS. Je to nejjednodušší a nejjednodušší plánovací algoritmus CPU. V tomto typu algoritmu získá nejprve přidělení CPU proces, který požaduje CPU. Tuto metodu plánování lze spravovat pomocí fronty FIFO.

Jakmile proces vstoupí do fronty připravenosti, jeho PCB (Process Control Block) se propojí s koncem fronty. Takže když se CPU uvolní, mělo by být přiřazeno procesu na začátku fronty.

Charakteristika metody FCFS

• Nabízí nepreemptivní a preemptivní 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 nejkratší zbývající čas. Je také známé jako preemptivní plánování SJF. V této metodě bude proces přiřazen úkolu, který je nejblíže jeho dokončení. Tato metoda zabraňuje tomu, aby novější proces ve stavu připravenosti pozdržel dokončení staršího procesu.

Charakteristika metody plánování SRT

• Tato metoda se většinou používá v dávkových prostředích, kde se vyžaduje upřednostnění krátkých zakázek.
• Toto není ideální způsob implementace ve sdíleném systému, kde není znám požadovaný čas CPU.
• Přiřaďte každému procesu délku jeho dalšího shluku CPU. Operační systém tedy používá tyto délky, což pomáhá naplánovat proces s co nejkratší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, které mají pracovat podle priority.

Prioritní plánování také pomáhá OS zahrnout prioritní přiřazení. Procesy s vyšší prioritou by měly být prováděny jako první, zatímco úlohy se stejnými prioritami jsou prováděny na principu round-robin nebo FCFS. Prioritu lze rozhodnout na základě požadavků na paměť, časových požadavků atd.

Round-Robin plánování

Round robin je nejstarší a nejjednodušší plánovací algoritmus. Název tohoto algoritmu pochází z principu round-robin, kde každá osoba dostane stejný podíl na něčem. Nejčastěji se používá pro plánovací algoritmy v multitaskingu. Tato metoda algoritmu pomáhá při provádění procesů bez hladovění.

Charakteristika Round-Robin Scheduling

• Round robin je hybridní model, který je poháněn hodinami
• Časový úsek by měl být minimální, který je přiřazen ke konkrétnímu úkolu, který má být zpracován. U různých procesů se však může lišit.
• Jedná se o systém reálného času, který reaguje na událost v určitém časovém limitu.

Nejdříve nejkratší práce

SJF je plná forma (Shortest job first) je plánovací algoritmus, ve kterém by měl být jako další vybrán proces s nejkratší dobou provádění. Tato metoda plánování může být preemptivní nebo nepreemptivní. Výrazně snižuje průměrnou dobu čekání na další procesy čekající na provedení.

Charakteristika rozvrhu SJF

• Je spojena s každou úlohou jako jednotka času k dokončení.
• U této metody, když je CPU k dispozici, bude jako první proveden další proces nebo úloha s nejkratším časem dokončení.
• Je implementován s nepreemptivní politikou.
• Tato metoda algoritmu je užitečná pro dávkové zpracování, kde čekání na dokončení úloh není kritické.
• Zlepšuje výstup úloh tím, že nabízí kratší úlohy, které by měly být provedeny jako první, které mají většinou kratší dobu obratu.

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

Tento algoritmus rozděluje připravenou frontu do různých samostatných front. V této metodě jsou procesy přiřazeny 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 OS, protože k plánování úloh potřebuje použít jiné typy algoritmů.

Charakteristika víceúrovňového plánování front

• Pro procesy s některými vlastnostmi by mělo být udržováno více front.
• Každá fronta může mít své samostatné plánovací algoritmy.
• Pro každou frontu jsou dány 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í procesy.
• Maximálního využití CPU lze dosáhnout pomocí vícenásobného programování.
• Procesy, které mají být provedeny, jsou ve frontě.

Shrnutí

• Plánování CPU je proces určování, který proces bude vlastnit CPU pro provádění, zatímco je jiný proces pozastaven.
• V Preemptivním plánování jsou úkoly většinou přiřazeny s jejich prioritami.
• V metodě Nepreemptivního plánování bylo CPU přiděleno konkrétnímu procesu.
• Doba shluku je doba potřebná k dokončení procesu. Říká se tomu také doba běhu.
• Využití CPU je hlavním úkolem, ve kterém musí operační systém zajistit, aby CPU zůstalo co nejvíce vytížené.
• Počet procesů, které dokončí své provádění za jednotku času, je známý propustnost.
• Čekací doba je množství, které konkrétní proces potřebuje čekat ve frontě připravených položek.
• Je to doba, za kterou byla žádost podána, dokud není vytvořena první odpověď.
• Doba obratu je doba potřebná k provedení určitého procesu.
• Přerušení časovačem je metoda, která úzce souvisí s preempcí.
• Dispečer je modul, který zajišťuje řízení CPU procesu.
• Šest typů algoritmů plánování procesů je: First Come First Serve (FCFS), 2) Shortest-Job-first (SJF) Scheduling, 3) Nejkratší zbývající čas, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Multilevel Queue Scheduling .
• v Metoda kdo dřív přijde, je dřív na řaděProces, který požaduje CPU, získá přidělení CPU jako první.
• V nejkratším zbývajícím čase bude proces přidělen úkolu, který je nejblíže jeho dokončení.
• V plánování priority plánovač vybírá úkoly, které mají pracovat podle priority.
• Round Robin plánování funguje na principu, kdy každý dostane rovný podíl na něčem.
• V nejkratší úloze jako první by měl být pro další provedení vybrán nejkratší čas provedení.
• Metoda víceúrovňového plánování rozděluje připravenou frontu do různých samostatných front. V této metodě jsou procesy přiřazeny do fronty na základě konkrétní vlastnosti.
• CPU používá plánování ke zlepšení své účinnosti.