Co je to kruhové plánování?
Název tohoto algoritmu vychází z principu kruhového plánování, kdy každá osoba dostane postupně stejný podíl něčeho. Jedná se o nejstarší a nejjednodušší algoritmus plánování, který se většinou používá pro multitasking.
Při Round-robin plánování běží každá připravená úloha postupně pouze v cyklické frontě po omezený časový úsek. Tento algoritmus také nabízí vykonávání procesů bez hladovění.
V tomto výukovém kurzu operačního systému se naučíte:
- Co je to kruhové plánování?
- Charakteristiky kruhového plánování
- Příklad kruhového plánování
- Výhody kruhového plánování
- Nevýhody kruhového plánování
- Nejhorší případ latence
Charakteristiky kruhového plánování
Zde jsou uvedeny důležité charakteristiky kruhového plánování:
- Round robin je preemptivní algoritmus
- Centrální procesor je přesunut na další proces po pevně stanoveném časovém intervalu, který se nazývá časové kvantum/časový úsek.
- Proces, který je preemptován, je přidán na konec fronty.
- Round robin je hybridní model, který je řízen taktem
- Časový úsek by měl být minimální, který je přidělen pro konkrétní úlohu, kterou je třeba zpracovat. Může se však lišit OS od OS.
- Jedná se o algoritmus reálného času, který reaguje na událost v určitém časovém limitu.
- Round robin je jeden z nejstarších, nejspravedlivějších a nejjednodušších algoritmů.
- Široce používaná metoda plánování v tradičních OS.
Příklad kruhového plánování.robin plánování
Považujte následující tři procesy
| Procesní fronta | Čas náběhu |
| P1 | 4 |
| P2 | 3 |
| P3 | 5 |
Krok 1) Provádění začíná procesem P1, který má burst time 4. Zde se každý proces vykonává po dobu 2 sekund. Procesy P2 a P3 jsou stále v čekací frontě.
Krok 2) V čase =2 je P1 přidán na konec fronty a P2 se začne vykonávat
Krok 3) V čase =4 je P2 preemptován a přidán na konec fronty. P3 se začne vykonávat.
Krok 4) V čase=6 , P3 je preemptován a přidán na konec fronty. P1 se začne vykonávat.
Krok 5) V čase=8 , P1 má burst time 4. Dokončil provádění. P2 začne vykonávat
Krok 6) P2 má burst time 3. Již vykonal 2 interval. V čase=9 P2 dokončí provádění. Poté se začne provádět P3, dokud se nedokončí.
Krok 7) Vypočítejme průměrnou dobu čekání pro výše uvedený příklad.
Wait time P1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7
Výhody kruhového plánování
Zde jsou uvedeny klady/výhody metody kruhového plánování:
- Nepotýká se s problémy hladovění nebo konvojového efektu.
- Všechny úlohy dostanou spravedlivě přidělený procesor.
- Pracuje se všemi procesy bez jakékoliv priority.
- Znáte-li celkový počet procesů ve frontě běhu, můžete také předpokládat nejhorší možnou dobu odezvy pro stejný proces.
- Tato metoda plánování není závislá na době výpadku. Proto je v systému snadno implementovatelná.
- Jakmile je proces vykonáván po určitou nastavenou dobu, je proces preemptován a po danou dobu se vykonává jiný proces.
- Dovoluje operačnímu systému použít metodu přepínání kontextu pro uložení stavů preemptovaných procesů.
- Dává nejlepší výkon z hlediska průměrné doby odezvy.
Nevýhody kruhového plánování
Zde jsou uvedeny nevýhody/nevýhody použití kruhového plánování:
- Pokud je doba krájení OS nízká, výkon procesoru se sníží.
- Tato metoda stráví více času přepínáním kontextu
- Její výkon silně závisí na časovém kvantu.
- Procesům nelze nastavit priority.
- Round-robin plánování nedává zvláštní prioritu důležitějším úlohám.
- Snižuje srozumitelnost
- Nižší časové kvantum má za následek vyšší režii přepínání kontextu v systému.
- Najít správné časové kvantum je v tomto systému poměrně obtížný úkol.
Nejhorší případ latence
Tento termín se používá pro maximální čas potřebný k provedení všech úloh.
- dt = Označuje dobu detekce při zařazení úlohy do seznamu
- st = Označuje dobu přepnutí z jedné úlohy na druhou
- et = Označuje dobu provedení úlohy
Formula:
Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISRt,SR = sum of all execution times
Souhrn:
- Název tohoto algoritmu pochází z principu round-robin, kdy každý dostane na střídačku stejný díl něčeho.
- Round robin je jedním z nejstarších, nejspravedlivějších a nejjednodušších algoritmů a široce používaných metod plánování v tradičních OS.
- Round robin je preemptivní algoritmus
- Největší výhodou metody plánování round-robin je, že Pokud znáte celkový počet procesů ve frontě běhu, můžete také předpokládat nejhorší možnou dobu odezvy pro stejný proces.
- Tato metoda stráví více času přepínáním kontextu
- Zpoždění v nejhorším případě je termín používaný pro maximální dobu potřebnou k provedení všech úloh.
.