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

Co je plánování Round-Robin?

Název tohoto algoritmu pochází z principu round-robin, kde každá osoba dostane v tazích stejný podíl něčeho. Je to nejstarší, nejjednodušší plánovací algoritmus, který se většinou používá pro multitasking.

V plánování typu Round Robin se každá připravená úloha spouští postupně v cyklické frontě po omezený časový úsek. Tento algoritmus také nabízí provádění procesů bez nutnosti hladovění.

Charakteristika Round-Robin Scheduling

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

• Round Robin je preventivní algoritmus.
• CPU se po uplynutí pevně stanoveného časového intervalu, který se nazývá časové kvantum/časový úsek, přesune k dalšímu procesu.
• Proces, který je preemptován, je přidán na konec fronty.
• Round Robin je hybridní model, který je řízen hodinami.
• Časový úsek by měl být minimální a je přiřazen pro konkrétní úkol, který je třeba zpracovat. Může se však lišit v závislosti na operačním systému.
• Jedná se o algoritmus pracující v reálném čase, 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ů.
• Je to široce používaná metoda plánování v tradičních operačních systémech.

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

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

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 je na konec fronty přidán P1 a začne se provádět P2.

Krok 3) V čase = 4 je P2 vyřazen a přidán na konec fronty. Začne se provádět P3.

Krok 4) V čase = 6 je P3 vyřazen a přidán na konec fronty. Začne se provádět P1.

Krok 5) V čase = 8 má P1 dobu burstů 4. Dokončil provádění. P2 zahajuje provádění.

Krok 6) P2 má dobu sérií 3. Již byl proveden po 2 intervaly. V čase = 9 P2 dokončí provádění. Poté P3 spustí provádění, dokud nedokončí.

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

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

Výhody plánování s kruhovým obsluhováním

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

• Nečelí problémům hladovění ani efektu konvoje.
• Všechny úlohy dostanou spravedlivé přidělení CPU.
• Zabývá se všemi procesy 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 čase shlukování. Proto je v systému snadno implementovatelná.
• 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 operačnímu systému použít metodu přepínání kontextu k uložení stavů preempovaný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žívání plánování Round-robin:

• Pokud je doba dělení operačního systému nízká, výkon procesoru se sníží.
• Tato metoda strá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.
• Plánování typu round-robin nedává zvláštní prioritu důležitějším úkolům.
• Snižuje to porozumění.
• Nižší časové kvantum má za následek vyšší režijní náklady na přepínání kontextů v systému.
• Nalezení správného časového kvanta je v tomto systému poměrně 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 úloha přidána do seznamu
• st = Označuje čas přepnutí z jedné úlohy na druhou
• et = Označuje dobu provádění úlohy

Vzorec:

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

Nejčastější dotazy