4.3.3. Planovani podle priority

• Algoritmus SJF je specialnim pripadem planovani podle priority. Principielne toto planovani znamena, ze kazdy proces je asociovan se svou prioritou a CPU je pridelen procesu s nejvyssi prioritou. Mezi procesy se stejnou prioritou se planuje FCFS algoritmem.

• V pripade SJF planovani je prioritou p prevracena hodnota odhadnute doby , tj. p = 1/. Cim vetsi je odhadnuta doba, tim mensi je priorita daneho procesu a naopak.

• Priorita muze byt definovana bud interni nebo externi. Interni priorita uziva meritelne nebo pocitatelne veliciny, jako napr.: casovy limit, pametove naroky, pocet otevrenych souboru nebo pomer prumerne delky CPU a I/O cyklu pro vypocet priority.

• Externi priorita je nastavovana podle vnejsich kriterii OS, jako napr. dulezitost procesu a dalsi casto politicka kriteria.

• Planovani dle priority muze byt preemptivni i nepreemptivni. V okamziku, kdy proces dorazi do fronty pripravenych, je jeho priorita porovnana s procesem prave spustenym a je-li vyssi, u preemptivniho planovani je procesor pridelen ihned novemu procesu, u nepreemptivniho je novy proces zarazen na vrchol fronty.

• Hlavnim problemem planovani dle priority je neomezeni zablokovani (indefinite blocking) nebo umoreni (starvation) procesu. Procesy s velmi nizkou prioritou by totiz mohli na CPU cekat az neomezene dlouho. V silne zatizenem vypocetnim systemu muze soustavny tok procesu s vyssi prioritou zabranit procesu s prioritou nizsi jakkoli se dostat k CPU. Globalne nastane jedna ze dvou moznosti: bud se proces spusti v nedeli ve 14.00 hod, kdy je nizke zatizeni nebo pri moznem vypadku dojde ke ztrate tohoto procesu. (Kdyz v roce 1973 provedly na MIT (Massachussets Institute of Technology) shut down systemu IBM 7094, nasly proces s nizkou prioritou zadany v roce 1967, a ktery do te doby nebyl ani jednou spusten).

• Resenim problemu neomezeneho zablokovani procesu je aging. Aging je technika, ktera vyznamne zvysi prioritu procesu, ktery je v systemu dlouhou dobu. Napr. je-li priorita definovana na intervalu 0 - 127, je mozne inkrementovat prioritu a 1 kazdych 15 minut. Takto kazdy proces, i ten s nejnizsi prioritou dosahne casem priority vyssi a bude spusten. I v nejhorsim pripade to nebude trvat dele nez 32 hodin.

4.3.4. Planovani cyklickou obsluhou (Round-Robin Scheduling)

• Tento algoritmus je vhodny zejmena pro OS se sdilenim casu. Je podobny algoritmu FCFS, obsahuje vsak navic moznost preemptivniho planovani. V systemu je definovana mala casova jednotka - casove kvantum vetsinou 10 - 100 ms. Fronta pripravenych je definovana jako cyklicka fronta a planovac CPU touto frontou prochazi stale dokola a prideluje CPU jednotlivym procesum vzdy na jedno casove kvantum.

• Pri RR planovani je fronta pripravenych implementovana formou bezne FIFO fronty procesu a novy proces je vzdy zarazen na jeji konec. Planovac CPU vezme proces na vrcholu, nastavi casovac na preruseni po uplynuti 1 casoveho kvanta a prideli procesu CPU.

• Nastane jedna ze dvou moznosti:

1. CPU cyklus procesu muze byt kratsi nez casove kvantum. V tom pripade proces sam uvolni CPU a planovac ho muze pridelit dalsimu procesu z fronty pripravenych.

2. CPU cyklus aktualne spusteneho procesu je delsi nez jedno casove kvantum a behem vykonavani procesu vyvola casovac preruseni. Nastava prepnuti kontextu a stavajici proces je umisten na konec fronty pripravenych. Planovac CPU potom z fronty pripravenych vybere dalsi proces pro prideleni CPU.

• Prumerna cekaci doba pri RR planovani je ovsem dosti znacna. Uvazujme nasledujici mnozinu procesu, jez dorazily do fronty pripravenych v case 0 a delka jejich CPU cyklu je uvedena:

• Uzijeme-li jako delku casoveho kvanta 4 ms, potom proces P1 dostane pridelen procesor na 4 ms, ovsem pro dokonceni sveho CPU cyklu ho potrebuje jeste dalsich 20 ms. Jeho beh je vsak preemptivne ukoncen a CPU pridelen procesu P2. Ten ani cele 4 ms nevycerpa a po 3 ms je jeho CPU cyklus ukonce a CPU se prideli procesu P3. Protoze kazdy proces ve fronte pripravenych jiz mel CPU pridelen na 1 casove kvantum, je CPU opet pridelen procesu P1, fronta pripravenych je prazdna, takze je mu procesor pridelen 6x za sebou:

• Cekaci doba procesu P1 je 6 ms, procesu P2 je 4 ms a procesu P3 je 7 ms. Prumerna cekaci doba je tedy 17/3 = 5.66 ms.

• V pripade RR planovani nedostane zadny proces najednou CPU na dobu delsi nez 1 casove kvantum. Pokud je CPU cyklu procesu delsi ne 1 kvantum je proces preemptivne odloucen od CPU a zarazen na konec fronty pripravenych. RR algoritmus je preemptivni.

• Efektivita RR planovani znacne zavisi na delce casoveho kvanta. Je-li casove kvantum prilis velke, RR algoritmus se premenuje na FCFS algoritmus se vsemi jeho nedostatky. Je-li casove kvantum prilis male (rekneme 1 ms), stava se RR pristup sdilenim procesoru a uzivatelsky se (teoreticky) zda, ze kazdy z n procesu je spusten na vlastnim procesoru s vykonem 1/n oproti skutecnemu procesoru systemu. Tento pristup vyuziva CDC hardware (Control Data Corporation), tak ze implementuje 10 virtualnich procesoru jednim fyzickym a 10 sadami registru. Tento hardware spusti jednu instrukci na jedne sade registru a jde na nasledujici. Celkove je program vykonavan jakoby deseti pomalejsimi procesory namisto jednim rychlym. (Kazda instrukce referuje pamet, ktera je mnohem pomalejsi nez rychly procesor, takze skutecne zpomaleni behu programu je minimalni).

• Pri definici casoveho kvanta je treba brat v uvahu pocet prepinani kontextu, ktery se zvysuje se snizujici se delkou casoveho kvanta. Uvazujme proces, ktery potrebuje 10 casovych jednotek CPU. Je-li delka casoveho kvanta 12 jednotek, procesu staci jedno kvantum, ktera ani cele nevyuzije. Byla-li by delka kvanta 6 jednotek, spotrebuje proces kvanta 2 a dojde k prepnuti kontextu. Pri delce kvanta 1 jednotka by doslo k 9 prepinanim kontextu, coz by uz znacne zpomalilo beh procesu:

Obr. 47 Cim mensi casove kvantum, tim vice prepinani kontextu

• Casove kvantum by tedy melo byt rozumne velike vzhledem k delce prepinani kontextu. Je-li doba nutna k prepnuti kontextu 10 % delky casoveho kvanta, potom 10 % CPU casu padne pouze na prepinani kontextu.

Obr. 48 Vztah prumerne doby obratky a delky casoveho kvanta

• Delka casoveho kvanta primo podminuje dobu obratky (turnaround time) procesu. Jak je videt z Obr. 48, prumerna doba obratky mnoziny procesu nemusi nutne zlepsovat s prodluzovanim casoveho kvanta. Globalne se prumerna doba obratky zlepsuje, jestlize mnoho procesu vykona svuj CPU cyklus behem jednoho casoveho kvanta.

• Na druhe strane, je-li casove kvantum prilis velke, RR planovani degeneruje na FCFS.