Round Robin Scheduling Algorithm with Example

Co je Round-Robin Scheduling?

Název tohoto algoritmu vychází z principu round-robin, kdy každý člověk získává střídavě stejný podíl na něčem. Jedná se o nejstarší a nejjednodušší plánovací algoritmus, který se většinou používá pro multitasking.

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

V tomto kurzu operačního systému se naučíte:

• Co je Round-Robin Scheduling?
• Charakteristiky plánování Round-Robin
• Příklad plánování každého s každým
• Výhoda plánování každý s každým
• Nevýhody plánování každý s každým
• Nejhorší latence

Charakteristiky plánování Round-Robin

Zde jsou důležité charakteristiky plánování Round-Robin:

• Round robin je preventivní algoritmus
• CPU se posune na další proces po pevně stanoveném časovém intervalu, který se nazývá časový kvantový / časový řez.
• Proces, který je preempted, 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í, který je přiřazen konkrétnímu úkolu, který je třeba zpracovat. Může se však lišit OS od OS.
• Jedná se o algoritmus v reálném čase, který reaguje na událost v konkrétní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ím OS.

Příklad plánování každého s každým

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

Procesní fronta	Čas prasknutí
P1	4
P2	3
P3	5

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

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

Krok 3) V čase = 4 je P2 předjímán a přidán na konci fronty. P3 se spustí.

Krok 4) V čase = 6 je P3 předjímán a přidán na konci fronty. P1 se spustí.

Krok 5) V čase = 8 má P1 čas roztržení 4. Dokončilo provedení. P2 zahájí provádění

Krok 6) P2 má čas shluku 3. Již byl proveden pro 2 intervaly. V čase = 9 dokončí P2 provádění. Poté P3 zahájí provádění, dokud se nedokončí.

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

Wait timeP1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7

Výhoda plánování každý s každým

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

• Nečelí problémům hladovění nebo efektu konvoje.
• Všechny úlohy získají spravedlivé rozdělení CPU.
• Zabývá se veškerým procesem bez jakékoli priority
• Pokud znáte celkový počet procesů ve frontě spuštění, můžete u stejného procesu předpokládat také nejhorší dobu odezvy.
• Tato metoda plánování nezávisí na době roztržení. Proto je v systému snadno implementovatelný.
• Jakmile je proces proveden pro konkrétní sadu období, je proces předjímán a pro dané časové období je proveden jiný proces.
• Umožňuje OS použít metodu přepínání kontextu k uložení stavů preempted procesů.
• Poskytuje nejlepší výkon z hlediska průměrné doby odezvy.

Nevýhody plánování každý s každým

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

• Pokud je doba krájení OS nízká, sníží se výkon procesoru.
• 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 stanovit priority.
• Plánování typu každý s každým nedává zvláštní prioritu důležitějším úkolům.
• Snižuje porozumění
• Nižší časové kvantum vede k 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.

Nejhorší latence

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 přenesen do seznamu
• st = Označte dobu přepnutí z jednoho úkolu na druhý
• et = Označte čas provedení úlohy

Vzorec:

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 vychází z principu round-robin, kdy každý člověk získává střídavě stejný podíl na něčem.
• 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ím operačním systému.
• Round robin je preventivní algoritmus
• Největší výhodou metody plánování každý s každým je, že Pokud znáte celkový počet procesů ve frontě spuštění, můžete u stejného procesu předpokládat také nejhorší dobu odezvy.
• Tato metoda tráví více času přepínáním kontextu
• Nejhorší latence je termín používaný pro maximální čas potřebný k provedení všech úkolů.