Plánovanie procesov

Obsah práce

1.	Procesy
2.	Plánovanie procesov
3.	Plánovanie procesov v OS Windows
4.	Rozbor programu pre meranie efektívnosti prioritných tried vlákien a procesov
5.	Analýza meraní efektívnosti prioritných tried vlákien a 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 (Plášil, 1992). 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í 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 fronty pripravených procesov na spracovanie. Každý aktívny proces má taktiež svoju plánovaciu prioritu. Pri výbere ďalšieho procesu sa 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 (DEITEL, 1990).

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 (Kvasnica, 2009). 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 (Kvasnica, 2009). 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é (Martincová, 1997).

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 (Kvasnica, 2009).

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 (Cada, 1993). 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 (Martincová, 1997). 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 fronta 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 (Kvasnica, 2009).

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 (Martincová, 1997).

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 (Kvasnica, 2009). 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ý. Tento spôsob sa nazýva stránkovanie (Plášil, 1992).

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 (Kvasnica, 2009).

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 (Cada, 1993).

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ší (Plášil, 1992). 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í (Kvasnica, 2009).

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 fronty pripravených procesov sa riadiaci blok procesu zaradí na koniec fronty. Takúto frontu nazývame FIFO (First in, First Out) (Martincová, 1997). 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 (Kvasnica, 2009). 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 (Martincová, 1997).

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 (Martincová, 1997). 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ánovania najkratšieho procesu 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) (Kvasnica, 2009).

Plánovanie podľa priorít

Obecný prípad pre algoritmus plánovanie podľa priorít je algoritmus najkratší proces najskôr (SJF). 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 (FCFS) (Plášil, 1992). 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é (Madnick, 1983).

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 (Madnick, 1983). Externé priority sa nastavujú kritériami vzhľadom na operačný systém, napr. dôležitosť procesu, alebo faktory z povahy procesu (Madnick, 1983). Plánovanie podľa priorít taktiež môže byť preemptívne alebo nepreemptívne (Kvasnica, 2009). 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 (Martincová, 1997). Pre odstránenie takéhoto nežiaduceho stavu bolo zavedené postupné zvyšovanie priorít procesov, ktoré čakajú, po uplynutí nejakej doby nastavenej systémom.

Cyklické plánovanie (RR - Round 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 (Kvasnica, 2009). 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 (Martincová, 1997). 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 na 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 (Kvasnica, 2009). 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 (FCFS) (Cada, 1993). Optimálny prípad pre nastavenie časového kvanta je, ak 80% procesov dokončí svoju činnosť v jednom časovom kvante (Madnick, 1983). Najčastejšie používané časové kvantum je 5 ms (Kvasnica, 2009).

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 (Roubíček, 2000). Pri použití tohto plánovania sa front pripravených procesov delí na niekoľko front, 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á fronta by mohla mať iný plánovací algoritmus napr. interaktívne procesy by sa mohli plánovať pomocou cyklického plánovania (RR). 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 (Martincová, 1997).

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

Každá fronta má vyššiu prioritu nad frontmi z nižšou prioritou, t.j. žiadny proces z fronty interaktívnych procesov nesmie byť vykonávaný, pokiaľ fronta zo systémovými procesmi nebude prázdna. Ďalší spôsob plánovania je pridelenie určitého časového kvanta procesora medzi fronty. Každá fronta dostane pridelenú časť časového kvanta procesora a nasledovne ju delí medzi procesy vo svojej fronte (Kvasnica, 2009). Ak by sme mali iba dve fronty, fronta procesov na pozadí a fronta procesov v popredí, potom fronta obsahujúca procesy v popredí môže dostať až 80% celkového časového kvanta procesora. Toto pridelené časové kvantum si delí medzi svoje procesy nejakým algoritmom plánovania napr. pomocou algoritmu cyklického plánovania (RR). Fronta procesov na pozadí dostane pridelení zvyšok časového kvanta t.j. 20%. Toto pridelené časové kvantum si môže deliť medzi procesy napr. pomocou algoritmu spracovania v poradí príchodu (FCFS). Všetky procesy v tomto plánovaní sú pevne spojené so svojím prideleným frontom a nemenia ho, pretože procesy sú roztriedené na základe nemennej charakteristiky. Výhodou tohto algoritmu sú nižšie réžie pre plánovanie. Toto plánovanie nie je dostačujúco flexibilné, je to jeho nevýhodou (Roubíček, 2000).

Plánovanie s viacerými frontami so spätnou väzbou

U tohto plánovania sa môžu procesy pohybovať medzi frontami, t.j. ich zaradenie nie je pevne dané na rozdiel od plánovania pomocou viacerých front bez spätnej väzby. Týmto sa toto plánovanie stáva flexibilným. Hlavnou myšlienkou tohto plánovania je oddeliť procesy s rôznou charakteristiku cyklu procesora (Martincová, 1997). Ako náhle nejaký proces príliš veľa využíva procesor, presunie sa do fronty s nižšou prioritou, aby toľko nezaťažoval systém a naopak. Proces vo fronte s nižšou prioritou, dlho čaká na pridelenie procesora, môže byť presunutý do fronty s vyššou prioritou, aby nenastal prípad nekonečného čakania procesu (Kvasnica, 2009). Ak budeme uvažovať plánovanie iba s tromi frontami 0, 1, 2. Plánovač začne prideľovať procesy z fronty 0, ak sa fronta 0 vyprázdni začne prideľovať procesy z fronty 1 ak nebudú žiadne procesy zaradené vo fronte 1 potom začne prideľovať procesy z fronty 2 ale iba v prípade ak je prázdna aj fronta 0, pretože proces z fronty 1 môže prerušiť proces vo fronte 2 a proces z fronty 0 môže prerušiť procesy z fronty 1 aj 2. Ak do systému medzi tým vstúpi proces a bude zaradení do fronty 0, preruší vykonávanie procesu v nižších frontách.

Novo vytvorený proces sa zaraduje do fronty 0, kde mu bude pridelene časové kvantum napr. 8 ms. Ak proces potrebuje väčšie časové kvantum na svoje dokončenie po vypršaní prideleného časového kvanta sa preruší a presunie sa do fronty z nižšou prioritou, v našom prípade do fronty 1. Ak fronta 0 nie je prázdna zvolí sa nasledujúci vo fronte 0, ak je prázdna vyberie sa prvý proces v poradí z fronty 1. V tejto fronte procesy dostávajú pridelené časové kvantum napr. 16 ms. Ak by proces nedokončil svoju činnosť do tohto časového kvanta presunie sa do fronty 2, kde sa procesy vykonávajú pomocou algoritmu spracovania v poradí príchodu (FCFS). Tento algoritmus uprednostňuje procesy, ktoré potrebujú čas procesora pre svoje dokončenie 8 ms alebo menej. Plánovač pomocou viacerých front so spätnou väzbou sa definuje podľa nasledovných parametrov :

• Počet front.
• Pre každú frontu plánovací algoritmus.
• Metódou, pre určenie charakteristiky, ktorý proces je treba presunúť do vyššej fronty s vyššou prioritou.
• Metódou, pre určenie charakteristiky, ktorý proces je treba presunúť do nižšieho frontu s nižšou prioritou.
• Metódou, pre určenie charakteristiky, do ktorej fronty bude zaradený proces, keď bude potrebovať prideliť procesor.

Je najuniverzálnejší, najvýznamnejší a najzložitejší algoritmus plánovania. Môže byť nakonfigurovaný pre akýkoľvek systém (Kvasnica, 2009).

Plánovanie systémov reálneho času

Systémy reálneho času môžeme rozdeliť na dve skupiny:

1. Systémy s tvrdým prideľovaním času.
2. Systémy s variabilnými prideľovaním času (Kvasnica, 2009).

Systémy s pevným prideľovaním času sú systémy, ktoré požadujú dokončenie úlohy v dopredu stanovenom čase. Pri zavedení procesu do systému sa dodáva aj s časom potrebným na dokončenie úlohy alebo pre kompletizáciu I/O operácie. Plánovač rozhoduje o prijatí procesu a jeho nasledovnej garancie splnenia procesu do požadovaného času, alebo ho odmietne ako nesplniteľný. Táto metóda sa nazýva ako metóda rezervovaných zdrojov (Martincová, 1997). Tvrdé prideľovanie času sa vyznačuje, koľko času treba na vykonanie určitej operácie, každej operácii je garantovaná maximálna priepustná doba. Garancia procesov nie je možná u systémov s virtuálnou alebo sekundárnou pamäťou, pretože tieto vyvolávajú nepredvídateľné zmeny času potrebného k vykonaniu procesu (Kvasnica, 2009). Systémy využívajúce plánovanie reálneho času sa skladajú zo špeciálnych programov, ktoré sa používajú iba na špeciálne navrhnutých platformách. Tieto systémy nie sú univerzálne. Systémy s variabilným prideľovaním času sú menej obmedzujúce. Vyžadujú, aby tzv. kritické procesy získali vyššiu prioritu ako ostatné procesy v systéme. Pridaním tohto plánovania do systémov využívajúcich zdieľanie času môže viesť k nespravodlivému prideľovaniu prostriedkov a tým k spomaleniu systému (Kvasnica, 2009). Existujú aj prípady, kde niektoré úlohy sa potrebujú spúšťať v prostredí s plánovaním v reálnom čase ako napr. vysokorýchlostná interaktívna grafika alebo multimediálne aplikácie, aby správne pracovali (Martincová, 1997). Pre implementáciu funkcií reálneho času potrebujeme adekvátne vlastnosti operačného systému a dobre navrhnutý plánovač. Systém musí využívať plánovanie pomocou priorít, pretože procesy v reálnom čase musia mať vyššiu prioritu, ktorá nesmie klesať ako iným procesom. Vybavovacia rýchlosť dispečera musí byť čo najmenšia, pretože čím je kratšia reakcia dispečera, tým môže byť rýchlejšie spustený proces v reálnom čase (Kvasnica, 2009). Veľa operačných systémov nemôže zabezpečiť krátku reakciu dispečera, pretože pred prepnutím kontextu sa musí čakať na dokončenie I/O operácie alebo systémového volania. Oneskorená reakcia dispečera v takýchto prípadoch býva veľká, pretože niektoré zo systémových volaní sú zložité a väčšina I/O zariadení sú pomalé. Pre udržanie malej doby reakcie dispečera, sa využíva preemptívne plánovanie systémových volaní. Sú dve riešenia. Prvé riešenie je zavedenie bodu núteného prerušenia pre dlhé systémové volania. Tento vložený bod zisťuje či nemusí byť spustený proces s vyššou prioritou, ak áno preemptívne sa mu pridelí procesor, čo vedie k prerušeniu systémového volania. Po dokončení procesu s vyššou prioritou sa dokončí systémové volanie. Tento bod musí byť vložený na bezpečné miesto, kvôli nebezpečenstvu prepísania systémových dát. Toto riešenie nie je veľmi efektívne, pretože do systému ich môže byť vložených veľmi málo (Martincová, 1997). Druhé riešenie je vytvoriť od základu celé preemptívne jadro, kde všetky systémové dáta musia byť chránené, čo zabezpečuje nejaký synchronizačný mechanizmus (Kvasnica, 2009). Toto riešenie je využité v operačnom systéme Solaris 2.