Čo je Round-Robin Scheduling?
Názov tohto algoritmu vychádza z princípu round-robin, kde každý človek dostáva striedavo rovnaký podiel na niečom. Je to najstarší a najjednoduchší plánovací algoritmus, ktorý sa väčšinou používa na multitasking.
Pri plánovaní každý s každým beží každá pripravená úloha po jednotlivých cykloch iba v cyklickom rade na obmedzený časový úsek. Tento algoritmus tiež ponúka vykonávanie procesov bez hladovania.
V tejto príručke k operačnému systému sa dozviete:
- Čo je Round-Robin Scheduling?
- Charakteristiky plánovania podľa princípu Round Robin
- Príklad plánovania s každým okruhom
- Výhoda plánovania s každým okruhom
- Nevýhody plánovania typu každý s každým
- Najhoršia latencia
Charakteristiky plánovania podľa princípu Round Robin
Tu sú dôležité charakteristiky plánovania Round-Robin:
- Round robin je preventívny algoritmus
- CPU sa po pevnom časovom intervale posúva k ďalšiemu procesu, ktorý sa nazýva časový kvantum / časový úsek.
- Preempovaný proces sa pridáva na koniec poradia.
- Round robin je hybridný model poháňaný hodinami
- Časový úsek by mal byť minimálny, ktorý je priradený konkrétnej úlohe, ktorú je potrebné spracovať. Môže sa však líšiť od OS k OS.
- Je to algoritmus v reálnom čase, ktorý reaguje na udalosť v konkrétnom časovom limite.
- Round robin je jeden z najstarších, najspravodlivejších a najjednoduchších algoritmov.
- Často používaný spôsob plánovania v tradičnom operačnom systéme.
Príklad plánovania s každým okruhom
Zvážte nasledujúce tri procesy
| Procesný front | Čas prasknutia |
| P1 | 4 |
| P2 | 3 |
| P3 | 5 |
Krok 1) Vykonanie sa začína procesom P1, ktorý má čas roztrhnutia 4. Tu sa každý proces vykonáva po dobu 2 sekúnd. P2 a P3 sú stále v čakacej rade.
Krok 2 ) V čase = 2 sa na koniec frontu pridá P1 a P2 sa začne vykonávať
Krok 3) V čase = 4 je predinštalovaný P2 a pridaný na konci poradia. P3 sa začne vykonávať.
Krok 4) V čase = 6 je zabránený P3 a pridaný na konci frontu. P1 sa začne vykonávať.
Krok 5) V čase = 8 má P1 čas roztrhnutia 4. Dokončilo sa vykonávanie. P2 začne vykonávanie
Krok 6) P2 má čas roztrhnutia 3. Už sa vykonával pre 2 intervaly. V čase = 9 P2 dokončí vykonávanie. Potom P3 začne vykonávanie, kým sa nedokončí.
Krok 7) Vypočítajme priemernú dobu čakania pre vyššie uvedený príklad.
Wait timeP1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7
Výhoda plánovania s každým okruhom
Tu sú výhody a výhody metódy plánovania Round-robin:
- Nečelí problémom hladovania alebo pôsobenia konvojov.
- Všetky úlohy dostanú spravodlivé pridelenie CPU.
- Zaoberá sa všetkým procesom bez akejkoľvek priority
- Ak poznáte celkový počet procesov vo fronte spustenia, môžete pre ten istý proces tiež predpokladať najhorší čas odozvy.
- Táto metóda plánovania nezávisí od času roztrhnutia. Preto je ľahko implementovateľný do systému.
- Akonáhle je proces vykonaný pre konkrétnu množinu obdobia, proces je preempovaný a vykoná sa ďalší proces pre dané časové obdobie.
- Umožňuje OS použiť metódu prepínania kontextu na ukladanie stavov preempovaných procesov.
- Poskytuje najlepší výkon z hľadiska priemerného času odozvy.
Nevýhody plánovania typu každý s každým
Tu sú nevýhody / nevýhody plánovania Round-robin:
- Ak je čas na krájanie OS nízky, výkon procesora sa zníži.
- Táto metóda trávi viac času prepínaním kontextu
- Jeho výkon silno závisí od časového kvanta.
- Pre procesy nie je možné stanoviť priority.
- Pravidelné plánovanie nedáva osobitnú prioritu dôležitejším úlohám.
- Znižuje porozumenie
- Výsledkom nižšieho časového kvanta je vyššia réžia kontextu v systéme.
- Nájsť správne časové kvantum je v tomto systéme dosť náročná úloha.
Najhoršia latencia
Tento termín sa používa ako maximálny čas potrebný na vykonanie všetkých úloh.
- dt = Označuje čas detekcie, keď sa úloha presunie do zoznamu
- st = Označte čas prechodu z jednej úlohy na druhú
- et = Označte čas vykonania ú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
Zhrnutie:
- Názov tohto algoritmu pochádza z princípu round-robin, kde každý človek dostáva striedavo rovnaký podiel na niečom.
- Round robin je jedným z najstarších, najspravodlivejších a najjednoduchších algoritmov a široko používaných metód plánovania v tradičných OS.
- Round robin je preventívny algoritmus
- Najväčšou výhodou metódy plánovania typu každý s každým je, že ak poznáte celkový počet procesov vo fronte spustenia, môžete pre ten istý proces predpokladať aj najhorší čas odozvy.
- Táto metóda trávi viac času prepínaním kontextu
- Najhoršia latencia je termín používaný pre maximálny čas potrebný na vykonanie všetkých úloh.