Round Robin plánovací algoritmus s příkladem

Charakteristika Round-Robin Scheduling

Zde jsou důležité charakteristiky Round-Robin Scheduling:

• Round robin je preventivní algoritmus
• CPU se přesune na další proces po pevném časovém intervalu, který se nazývá časové kvantum/časový řez.
• Proces, který je preemptován, je přidán na konec fronty.
• 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 pro konkrétní úkol, který je třeba zpracovat. Může se však lišit OS od OS.
• Je to algoritmus reálného času, který reaguje na událost v určitém časovém limitu.
• Round robin je jedním z nejstarších, nejspravedlivějších a nejjednodušších algoritmů.
• Široce používaná metoda plánování v tradičních OS.

Příklad plánování po obou stranách

Zvažte to následující tři procesy

Fronta procesů	Čas prasknutí
P1	4
P2	3
P3	5

Krok 1) Provádění začíná procesem P1, který má dobu shluku 4. Zde se každý proces provádí po dobu 2 sekund. P2 a P3 jsou stále ve frontě.

Krok 2) V čase =2 se P1 přidá na konec fronty a P2 se spustí

Krok 3) V čase=4 je P2 vyřazen a přidán na konec fronty. P3 se spustí.

Krok 4) V čase=6 je P3 vyřazen a přidán na konec fronty. P1 se spustí.

Krok 5) V čase=8 má P1 dobu shluku 4. Dokončilo provádění. P2 zahájí provádění

Krok 6) P2 má dobu shluku 3. Proběhl již 2 interval. V čase=9 dokončí P2 provádění. Poté P3 zahájí provádění, dokud nebude dokončeno.

Krok 7) Vypočítejme průměrnou dobu čekání pro výše uvedený příklad.

Wait time 
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

Výhoda Round-Robin Scheduling

Zde jsou výhody/výhody metody Round-robin plánování:

• Nečelí problémům hladovění nebo efektu konvoje.
• Všechny úlohy dostanou spravedlivé přidělení CPU.
• Zabývá se veškerým procesem bez jakékoli priority
• Pokud znáte celkový počet procesů ve frontě běhu, můžete také předpokládat dobu odezvy v nejhorším případě pro stejný proces.
• Tato metoda plánování nezávisí na době shluku. Proto je snadno implementovatelný do systému.
• Jakmile je proces spuštěn po určitou množinu období, proces je preemptován a v daném časovém období se spustí jiný proces.
• Umožňuje OS používat metodu přepínání kontextu k uložení stavů preemptovaných procesů.
• Poskytuje nejlepší výkon z hlediska průměrné doby odezvy.

Nevýhody Round-Robin Scheduling

Zde jsou nevýhody/nevýhody použití plánování Round-robin:

• Pokud je doba řezání OS nízká, výkon procesoru se sníží.
• Tato metoda tráví více času přepínáním kontextu
• Jeho výkon silně závisí na časovém kvantu.
• Pro procesy nelze nastavit priority.
• Round-robin plánování nedává zvláštní prioritu důležitějším úkolům.
• Snižuje porozumění
• 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 docela obtížný úkol.

Latence v nejhorším případě

Tento termín se používá pro maximální dobu potřebnou k provedení všech úkolů.

• dt = Označuje čas detekce, když je úkol uveden do seznamu
• st = Označuje čas přepnutí z jedné úlohy na druhou
• et = Označuje čas provedení úlohy

Vzorec:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR	
t,SR = sum of all execution times

Shrnutí

• Název tohoto algoritmu pochází z principu round-robin, kde každá osoba dostane v tazích stejný podí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 preventivní algoritmus
• Největší výhodou metody kruhového plánování je to, že pokud znáte celkový počet procesů ve frontě běhu, můžete také předpokládat dobu odezvy v nejhorším případě pro stejný proces.
• Tato metoda tráví více času přepínáním kontextu
• Latence v nejhorším případě je termín používaný pro maximální dobu potřebnou k provedení všech úkolů.