Plánovanie procesov

Obsah práce

1.	Procesy
2.	Plánovanie procesov
3.	Plánovanie procesov v OS Windows

Plánovanie procesov

Do základných funkcií systému patrí plánovanie času procesora. Pre zefektívnenie práce celého systému sa prideľuje procesor jednotlivým procesom.

Základné princípy

Základnou myšlienkou je, aby stále bežalo niekoľko procesov pre maximálne využitie procesora. V danom čase pri jednoprocesorových systémoch beží iba jeden proces. Ak sa v systéme nachádza viac ako jeden proces, ostatné procesy vo fronte pripravených musia čakať na uvoľnenie procesora. V jednoduchom operačnom systéme procesor nebude vykonávať žiadnu prácu. V multiprogramovom systéme sa snažíme tento čas využiť efektnejšie. Ak vykonávaný proces z nejakého dôvodu čaká napr. na I/O operáciu, sa zaradí sa do fronty I/O zariadení, systém pridelí procesor inému procesu z fronty pripravených procesov. V systémoch pracujúcich zo zdieľaním času sa novo vytvoreným procesom prideľuje aj časový úsek, nazývaný ako časové kvantum. Po vypršaní časového kvanta sa proces preruší a vyberie sa ďalší proces z frontu pripravených procesov na spracovanie. Každý aktívny proces má taktiež svoju plánovaciu prioritu. Pri výbere ďalšieho procesu prihliada na túto prioritu, zvolí proces s najvyššou prioritou. Pôvodnému procesu bude pridelené nové časové kvantum pre jeho ďalšie spracovanie.

Cykly periférií a procesora

Vykonávanie procesu pozostáva z cyklu využívania procesora a cyklu čakania na I/O. Proces prebieha medzi týmito dvomi cyklami. Vykonávanie procesu začína cyklom procesora a pokračuje striedaním cyklu procesora a cyklu I/O. Posledný cyklus pred ukončením procesu, aby mohol byť dokončený štandardnými operáciami je cyklus procesora. Procesy využívajúce prevažne I/O budú mať malé periódy využitia procesora, procesy využívajúce prevažne procesor budú mať tieto periódy dlhé. Pre výber plánovacieho algoritmu pre čas procesora sú tieto rozdiely veľmi podstatné.

Plánovač času procesora

Procesy počas svojej existencie putujú medzi rôznymi frontami. Nejakým spôsobom operačný systému musí rozhodnúť, ktorý proces vybrať z front. Tento proces zabezpečuje plánovač. Do systému postupuje viac úloh, ako sa môže naraz vykonávať. Tieto úlohy sa ukladajú najčastejšie na pevný disk. Systém obsahuje dva nasledovné plánovače:

• Plánovač úloh alebo tzv. dlhodobý plánovač, vyberie procesy z úloh uložených na pevnom disku a zavedie ich do pamäti k spusteniu.
• Plánovač procesov alebo tzv. krátkodobý plánovač, vyberá z procesov uložených v pamäti a prideľuje jednému z nich procesor.

Rozdiel medzi týmito plánovačmi je vo frekvencii ich spúšťania. Plánovač procesov sa musí spúšťať o veľa častejšie ako plánovač úloh. Spúšťa sa každých 1 ms. Pri prideľovaní procesora musí byť veľmi rýchly. Plánovač úloh vpúšťa úlohy do systému. Dajú sa rozdeliť na dve skupiny, tie ktoré využívajú I/O zariadenia a tie, ktoré využívajú iba procesor. Plánovač úloh musí tieto dve skupiny procesov vhodne striedať aby bolo zachované efektívne využívanie celého systému. Pretože ak by všetky procesy využívali I/O zariadenia, fronta pripravených procesov by bola prázdna a naopak, ak by všetky procesy využívali procesor frontu zariadení by bola prázdna, čo by viedlo k nevyváženosti systému. Plánovač úloh má tieto funkcie:

• Sleduje stav všetkých procesov, registruje všetky procesy, ktoré vstupujú do systému a všetky procesy, ktoré sú vo fronte pripravených procesov, vykonávajú sa alebo sú blokované.
• Volí stratégiu, podľa ktorej procesy vstupujú do systému, zavádzajú sa do fontu pripravených procesov. Rozhoduje podľa viacerých kritérií, ako napr. priorita, vyváženie systému, požadované prostriedky procesu.
• Procesu vo fronte pripravených procesov prideľuje potrebné prostriedky

Plánovač procesov ako náhle plánovač úloh zatriedi proces do fronty pripravených procesov rozhoduje, ktorému a na ako dlhú dobu pridelení procesor. Po výbere procesu je potrebné obnoviť registre procesora. Túto úlohu zastáva v systéme dispečer.

Systémy zo zdieľaním času majú interaktívnu úroveň prideľovania. Základná myšlienka spočíva v tom, že niekedy je výhodnejšie pre systém odstrániť vykonávajúci sa proces na čas z pamäti a presunúť ho na disk a znížiť tak počet procesov v pamäti. Týmto spôsobom sa môže zabrániť preplneniu pamäte. Proces môže byť neskôr opätovne načítaný do pamäte a spustený.

Preemptívne plánovanie

Pri jednom z ďalej uvedených prechodov sa môže urobiť rozhodovanie o plánovaní času procesora.

1. Prepínanie procesu zo stavu prebiehajúci do stavu čakajúci.

2. Prepínanie procesu zo stavu prebiehajúci do stavu pripravený.

3. Prepínanie procesu zo stavu čakajúci do stavu pripravený
4. Pri ukončení procesu
Ako náhle v plánovači dochádza iba, a len iba vo vykonávaní bodov 1 a 4 sa toto plánovanie nazýva nepreemptívne v opačnom prípade je plánovanie preemptívne. Ak je pri nepreemptívnom plánovaní pridelený procesor procesu, tento proces sa vykonáva až do svojho ukončenia, alebo ak vznikne požiadavka na I/O operáciu a procesu sa zmení kontext na čakajúci. Preemptívne plánovanie je náročnejšie. Pri preemptívnom plánovaní treba uvažovať s procesmi, ktoré zdieľajú dáta, tieto dáta treba udržovať v konzistentnom tvare pri prepnutí kontextu procesu. Na udržanie konzistentného stavu dát je treba dodatočných synchronizačných prostriedkov.

Dispečer

Dispečer je modul operačného systému, ktorý má kontrolu nad procesorom a procesom vybraným pre vykonanie plánovačom procesov. Dispečer sa spúšťa pri každom prepínaní kontextu procesov, preto by mal byť čo najrýchlejší. Jeho hlavné úlohy sú nasledovné:

• prepínanie kontextu procesov
• prepínanie medzi užívateľskými módmi
• skok na adresu kde bol proces prerušený, pri opätovnom spustení

Algoritmy plánovania

Plánovacie algoritmy riešia problém, ktorému procesu z fronty pripravených procesov bude pridelený procesor.

Spracovanie v poradí príchodu (FCFS – First come, First served)

Tento algoritmus spracovania v poradí príchodu je najjednoduchší. Základnou ideou tohto algoritmu je, proces, ktorý požiadal o pridelenie procesora ako prvý ho dostane ako prvý. Pri zaradovaní procesu do frontu pripravených procesov sa riadiaci blok procesu zaradí na koniec fronty. Takúto frontu nazývame FIFO (First in, First Out). Po uvoľnení procesoru prvým procesom, sa procesor pridelí nasledujúcemu procesu, teda druhému v poradí vo fronte pripravených procesov. Bežiaci proces sa odstráni z fronty. Algoritmus plánovania v poradí príchodu nie je preemptívny. Ak proces dostane procesor tak mu zostane pridelený až do ukončenia alebo, kým proces nevyžaduje nejakú I/O operáciu. Tento algoritmus môže veľmi predĺžiť čakaciu dobu krátkych procesov. Algoritmus nie je vhodný a je veľmi ťažko použiteľný v systémoch zdieľania času.

Najkratší proces najskôr (SJF – Shortest Job First)

Podľa času, ktorý vyžaduje proces na procesore sa určuje poradie spracovania procesov. Po uvoľnení procesora sa procesor pridelí procesu, ktorý má najmenšie požiadavky na čas procesora pre svoje dokončenie v prípade ak bol medzitým spracovávaný. Ak nastane prípad zhody požadovaného času na procesore algoritmus prihliada na poradie pri vstupe do systému. Pri tomto algoritme je potrebné dopredu vedieť požadovaný čas na procesore pre každý proces. Toto môžeme považovať ako nedostatok. Používa sa pri dlhodobom plánovaní procesov. Nie je vhodný na krátkodobé plánovanie, pretože pri krátkodobom plánovaní nepoznáme požiadavky na čas nasledovného procesu. Algoritmus plánovanie najkratší proces najskôr môže byť preemptívny alebo nepreemptívny. Výber medzi týmito dvomi variantmi sa robí pri príchode nového procesu do fronty pripravených procesov a predchádzajúci proces sa ešte vykonáva. Tento výber dvoch variant sa robí, pretože nový proces môže mať menšie požiadavky na čas procesora ako zostávajúce požiadavky vykonávajúceho sa procesu. Preemptívny algoritmus prepne vykonávajúci sa proces, nepreemptívny algoritmus nechá vykonávajúci sa proces dokončiť. Niekedy sa tento preemptívny algoritmus nazýva plánovanie podľa najkratšej zostávajúcej doby na vykonanie (SRTF - Shortest Remaining Time First).

Plánovanie podľa priorít

Obecný prípad pre algoritmus plánovanie podľa priorít je algoritmus najkratší proces najskôr. Každý proces má pridelenú prioritu , podľa tejto priority sa prideľuje procesor procesu. Procesor sa prideľuje procesu s najvyššou prioritou. Ak nastane prípad rovnakej priority pri procesoch sa plánovanie uskutočňuje podľa algoritmu plánovania spracovanie podľa poradia príchodu. Priority patria do intervalu celých čísiel napr. od 0 do 7. Nie je žiadne ustanovenie, že nižšie číslo znamená menšiu prioritu. V niektorých systémoch menšie číslo znamená nižšiu prioritu a u niektorých je to naopak. Priority sa môžu definovať:

• Interné
• Externé

Interné definovanie priority využíva niektoré merateľné hodnoty procesu napr. pamäťové časové limity, počet otvorených súborov, pomer priemerných požiadaviek na procesor a I/O operácie. Externé priority sa nastavujú kritériami externej ma vzhľadom na operačný systém, napr. dôležitosť procesu, alebo faktory z povahy procesu. Plánovanie podľa priorít taktiež môže byť preemptívne alebo nepreemptívne. Proces, ktorý príde do fronty pripravených procesov sa porovnáva s vykonávajúcim sa procesom vzhľadom na prioritu. Ak pri preemptívnom plánovaní podľa priorít bude priorita nového procesu vyššia ako priorita vykonávajúceho procesu tak bude prepnutý. Pri nepreemptívnom bude proces zaradený na začiatok fronty pripravených procesov. Pri takomto plánovaní môže vzniknúť situácia že procesy s nižšou prioritou by dlho čakali na pridelenie procesora alebo by neboli vôbec nikdy dokončené, čo by mohlo spôsobiť nefunkčnosť systému. Pre odstránenie takéhoto nežiaduceho stavu bolo zavedené postupné zvyšovanie priorít procesom , ktoré čakajú, po uplynutí nejakej doby nastavenej systémom.

Cyklické plánovanie (RR - Rond Robin)

Tento typ plánovacieho algoritmu bol špeciálne navrhnutý pre systémy so zdieľaním času. Je veľmi podobný algoritmu spracovania v poradí príchodu, ale je preemptívny. Pri tomto plánovaní sa definuje časové kvantum v rozmedzí (1- 10 ms). Procesy vo fronte pripravených procesov sa spracovávajú cyklicky. Plánovač procesov postupne pridelí jedno časové kvantum procesu vo fronte pripravených procesov, ktoré môže byť napr. 4 ms. Cyklické plánovanie využíva frontu pripravených procesov FIFO. Nový proces sa zaradí na koniec fronty pripravených procesov. Plánovač procesov vyberie vždy prvý proces na začiatku fronty, nastaví časovač na časové kvantum a pridelí procesu procesor. Ak proces potrebuje procesor na kratšie časové kvantum ako mu bolo pridelené a uvoľní procesor, plánovač vyberie nasledujúci proces, ktorý je prvej pozícii vo fronte a pridelí mu procesor. Ak by proces potreboval väčšie časové kvantum na svoje vykonanie, po uplynutí prideleného časového kvanta ho preruší a uloží si kontext procesu, nasledovne je presunutý na poslednú pozíciu vo fronte pripravených procesov. Procesor bude pridelený ďalšiemu procesu ktorý je na prvom mieste vo fronte. Výkonnosť algoritmu cyklického plánovanie bude závisieť zásadne od určenia veľkosti časového kvanta. Ak by sme uvažovali s nekonečne veľkým časovým kvantom, tento algoritmus bude rovnocenný s algoritmom Spracovania v poradí príchodu. Optimálny prípad pre nastavenie časového kvanta je, ak 80% procesov dokončí svoju činnosť v jednom časovom kvante. Najčastejšie používané časové kvantum je 5 ms.

Plánovanie pomocou viacerých front

Procesy sa dajú rozdeliť na dve skupiny, pre túto situáciu bola navrhnutá trieda plánovacích algoritmov pomocou viacerých front. Procesy môžeme rozdeliť na interaktívne a dávkové. Každá z týchto dvoch skupín má odlišné požiadavky na čas potrebný pre dokončenie procesu alebo môžu mať odlišné potreby pre plánovanie. Pri použití tohto plánovania sa front pripravených procesov delí na niekoľko frontov, ako je znázornené na obrázku 4. Procesy sú zadeľované do front podľa nejakého kritéria procesu napr. priorita, veľkosť, typ procesu atď. Každá z front by mohla mať iný plánovací algoritmus napr. interaktívne procesy by sa mohli plánovať pomocou cyklického plánovania. V tomto plánovaní prebieha aj plánovanie medzi frontami, ktoré je zvyčajne preemptívne s pevnými prioritami, t.j. procesy na popredí majú vyššiu externú prioritu, ako procesy na pozadí (dávkové procesy) kvôli interaktívnej komunikácii s užívateľom.


Obrázok 4 Plánovanie pomocou viacerými frontmi