Algoritmy plánování CPU v operačních systémech

Co je plánování CPU?

CPU Scheduling je proces určování, který proces bude vlastnit CPU k provádění, zatímco jiný proces je pozastaven. Hlavním úkolem plánování CPU je zajistit, aby vždy, když CPU zůstane nečinné, OS alespoň vybral jeden z procesů dostupných ve frontě připravenosti k provedení. Proces výběru provede plánovač CPU. Vybírá jeden z procesů v paměti, které jsou připraveny k provedení.

V tomto kurzu plánování CPU se naučíte:

• Co je plánování CPU?
• Typy plánování CPU
• Důležité terminologie plánování CPU
• Kritéria plánování CPU
• Intervalový časovač
• Co je dispečer?
• Algoritmus plánování CPU
• Kdo dřív příjde ten dřív mele
• Nejkratší zbývající čas
• Prioritní plánování
• Round-Robin Scheduling
• Nejkratší práce jako první
• Víceúrovňové plánování front
• Účel algoritmu plánování

Typy plánování CPU

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

Preventivní plánování

V preventivním plánování jsou úkoly většinou přiřazeny s jejich prioritami. Někdy je důležité spustit úkol s vyšší prioritou před jiným úkolem s nižší prioritou, i když úkol s nižší prioritou stále běží. Úkol s nižší prioritou nějakou dobu trvá a obnoví se, když úkol s vyšší prioritou dokončí své provádění.

Nepreventivní plánování

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

Kdy je plánování preventivní nebo nepřekonatelné?

Chcete-li zjistit, zda je plánování preventivní nebo nepřekonatelné, zvažte tyto čtyři parametry:

1. Proces se přepne z běžícího do čekajícího stavu.
2. Specifický proces se přepne z provozního stavu do připraveného stavu.
3. Specifický proces se přepne ze stavu čekání do stavu připravenosti.
4. Proces dokončil své spuštění a byl ukončen.

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

Všechny ostatní plány jsou preventivní.

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

• Burst Time / Execution Time: Jedná se o čas potřebný k dokončení procesu. Také se tomu říká doba běhu.
• Čas příjezdu: když proces vstoupí do připraveného stavu
• Finish Time: when process complete and exit from a system
• Multiprogramování: Několik programů, které mohou být přítomny v paměti současně.
• Práce: Jedná se o typ programu bez jakékoli interakce uživatele.
• Uživatel: Je to druh programu, který má interakci s uživatelem.
• Proces: Jedná se o referenci, která se používá pro úlohu i uživatele.
• Cyklus série CPU / IO: Charakterizuje provádění procesu, které se střídá mezi činností CPU a I / O. Časy CPU jsou obvykle kratší než doba I / O.

Kritéria plánování CPU

Algoritmus plánování CPU se snaží maximalizovat a minimalizovat následující:

Maximalizovat:

Využití CPU: Využití CPU je hlavním úkolem, ve kterém operační systém potřebuje zajistit, aby CPU zůstala co nejrušnější. Může se pohybovat od 0 do 100 procent. U RTOS to však může být rozmezí od 40 procent pro nízkou úroveň a 90 procent pro systém vysoké úrovně.

Propustnost: Počet procesů, které dokončují 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 té době se pracuje a práce dokončená za jednotku času se nazývá propustnost.

Minimalizovat:

Čekací doba: Čekací doba je částka, kterou musí určitý proces čekat ve frontě připravenosti.

Doba odezvy: Jedná se o množství času, ve kterém byl požadavek odeslán, dokud není vytvořena první odpověď.

Čas obratu: Čas obratu je doba potřebná k provedení konkrétního procesu. Jedná se o výpočet celkového času stráveného čekáním na vstup do paměti, čekáním ve frontě a spuštěním na CPU. Období mezi okamžikem odeslání procesu a časem dokončení je doba obratu.

Intervalový časovač

Přerušení časovače 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. Přerušení časovače i preempce přinutí proces vrátit procesor před dokončením jeho zhroucení CPU.

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

Co je dispečer?

Jedná se o modul, který poskytuje řízení CPU procesu. Dispečer by měl být rychlý, aby mohl běžet na každém přepnutí kontextu. Latence odeslání je doba potřebná plánovačem CPU k zastavení jednoho procesu a spuštění jiného.

Funkce prováděné dispečerem:

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

Algoritmus plánování CPU

Existuje hlavně šest typů algoritmů plánování procesů

1. První, první, první podání (FCFS)
2. Plánování nejkratší práce (SJF)
3. Nejkratší zbývající čas
4. Prioritní plánování
5. Round Robin Scheduling
6. Víceúrovňové plánování front

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

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

Když proces vstupuje do připravené fronty, jeho PCB (Process Control Block) je propojen s ocasem fronty. Když se CPU uvolní, mělo by to být přiřazeno procesu na začátku fronty.

Charakteristika metody FCFS:

• Nabízí nepreventivní a preventivní plánovací algoritmus.
• Úlohy se vždy provádějí podle zásady „kdo dřív přijde, je dřív na řadě“
• Je snadné jej implementovat a používat.
• Tato metoda má však špatný výkon a obecná čekací doba je poměrně vysoká.

Nejkratší zbývající čas

Plná forma SRT je nejkratší zbývající čas. To je také známé jako SJF preemptivní plánování. V této metodě bude proces přidělen úkolu, který je nejblíže jeho dokončení. Tato metoda zabrání procesu novějšího stavu připravenosti v držení 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 je třeba upřednostňovat krátké úlohy.
• To není ideální metoda pro implementaci ve sdíleném systému, kde není požadovaný čas CPU znám.
• Přiřaďte se ke každému procesu jako délka jeho dalšího výbuchu CPU. Takže operační systém používá tyto délky, což pomáhá naplánovat proces na co nejkratší dobu.

Prioritní plánování

Prioritní plánování je metoda plánování procesů na základě priority. V této metodě plánovač vybere úkoly, které mají fungovat podle priority.

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

Round-Robin Scheduling

Round robin je nejstarší a nejjednodušší plánovací algoritmus. Název tohoto algoritmu vychází z principu kruhových obměn, kdy každý člověk získá stejný podíl na něčem v pořadí. Většinou se používá pro plánování algoritmů v multitaskingu. Tato metoda algoritmu pomáhá bez hladovění provádění procesů.

Charakteristiky plánování Round-Robin

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

Nejkratší práce jako první

SJF je plná forma (Nejkratší úloha jako první) je plánovací algoritmus, ve kterém by měl být vybrán proces s nejkratší dobou provedení pro další provedení. Tato metoda plánování může být preemptivní nebo non-preventivní. Výrazně snižuje průměrnou čekací dobu na další procesy čekající na provedení.

Charakteristika plánování SJF

• Je spojena s každou úlohou jako jednotka času k dokončení.
• V této metodě, když je CPU k dispozici, bude nejprve proveden další proces nebo úloha s nejkratší dobou dokončení.
• Je implementováno s nepre-preventivní 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 úlohy tím, že nabízí kratší úlohy, které by měly být provedeny jako první, které většinou mají kratší dobu zpracování.

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ě konkrétní vlastnosti procesu, jako je priorita procesu, velikost paměti atd.

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

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

• U procesů s některými charakteristikami 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 uvedeny priority.

Účel algoritmu plánování

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

• CPU používá plánování ke zlepšení své účinnosti.
• Pomůže vám alokovat zdroje mezi konkurenční procesy.
• Maximální využití CPU lze dosáhnout multi-programováním.
• Procesy, které mají být provedeny, jsou ve frontě připravenosti.

Souhrn:

• Plánování CPU je proces určování, který proces bude vlastní CPU k provádění, zatímco jiný proces je pozastaven.
• V preventivním plánování jsou úkoly většinou přiřazeny s jejich prioritami.
• V metodě non-preemptive scheduling byla CPU přidělena konkrétnímu procesu.
• Burst time je čas potřebný pro dokončení procesu. Také se tomu říká doba běhu.
• Využití CPU je hlavním úkolem, ve kterém se operační systém musí ujistit, že CPU zůstane co nejrušnější
• Počet procesů, které dokončí své spuštění za jednotku času, je známý Propustnost.
• Čekací doba je částka, kterou musí určitý proces čekat ve frontě připravenosti.
• Jde o množství času, během kterého byl požadavek odeslán, dokud nebude předložena první odpověď.
• Doba obratu je doba potřebná k provedení konkrétního procesu.
• Přerušení časovače je metoda, která úzce souvisí s preempcí,
• Dispečer je modul, který poskytuje řízení procesoru procesu.
• Šest typů algoritmů plánování procesu je:
• First Come First Serve (FCFS), 2) Plánování s nejkratší dobou práce (SJF) 3) Nejkratší zbývající čas 4) Plánování priority 5) Plánování každý s každým 6) Víceúrovňové plánování fronty
• V metodě First Come First Serve získává proces, který požaduje CPU, nejprve přidělení CPU.
• V nejkratším zbývajícím čase bude proces přidělen úkolu, který je nejblíže jeho dokončení.
• V části Prioritní plánování plánovač vybere úkoly, které mají fungovat podle priority.
• V tomto plánování Round Robin funguje principiálně, kdy každá osoba získá stejný podíl na něčem
• V Nejkratší úloze jako první by měla být vybrána nejkratší doba provedení pro další provedení
• Ve víceúrovňovém plánování metoda oddě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.