4.3.6. Planovani pomoci vice front se zpetnou vazbou (Multilevel Feedback Queue Scheduling)

• V beznem systemu planovani pomoci vice front je kazdemu procesu pridelena fronta, ve ktere bude vzdy cekat na CPU jiz v okamziku vytvoreni procesu. Procesy se mezi frontami nemohou presouvat. Tento system snizuje reziji planovani, ale neni prilis flexibilni.

• Planovani pomoci vice front se zpetnou vazbou umoznuje procesum presouvat se mezi frontami. Hlavni myslenka je oddelit procesy s ruznou charakteristikou CPU cyklu. Jestlize nejaky proces vyuziva CPU prilis mnoho, bude presunut do fronty s nizsi prioritou, aby tolik nezatezoval OS. A naopak, proces, ktery jiz velmi dlouho ceka ve fronte s nizsi prioritou muze byt presunut do fronty s prioritou vyssi - prevence pred neomezenym zablokovanim procesu.

• Toto schema ponechava vysokou prioritu interaktivnim a I/O-bound procesum.

• Uvazujme system planovani pomoci vice front se zpetnou vazbou se 3 frontami 0 az 2 (viz. Obr. 50). Planovac CPU nejprve obslouzi vsechny procesy ve fronte 0, pouze v pripade, ze je fronta 0 prazdna, dostane se na procesy ve fronte 1 a stejne tak procesum z fronty 2 muze byt CPU pridelen jedine v pripade, ze jak fronta 0 tak i 1 jsou prazdne. Proces z fronty 1 muze preemptivne ukoncit beh procesu z fronty 2, proces z fronty 0 muze preemptivne ukoncit beh procesu z fronty 1 i 2.

• Proces, ktery vstoupi do fronty pripravenych je zarazen do fronty 0 a casove kvantum v teto fronte je 8 ms. Jestlize za tuto dobu nestihne vykonat cely svuj CPU cyklu, je presunut do fronty 1, kde je casove kvantum 16 ms a jestlize ani za tuto dobu nestihne dokoncit svuj CPU cyklus je presunut do fronty 2, kde je planovano modelem FCFS.

Obr. 50 Planovani pomoci vice front se zpetnou vazbou

• Tento zpusob planovani prideluje nejvyssi prioritu procesum s delkou CPU cyklu 8 ms a mensi. Procesy s delkou CPU cyklu mezi 8 a 16 ms jsou obsluhovany take rychle, ale s nizsi prioritou nez kratsi procesy. Dlouhe procesy automaticky klesnou do fronty 2.

• Planovani pomoci vice front se zpetnou vazbou je v globale definovano:

1. Poctem front
2. Planovacim algoritmem v kazde fronte
3. Metodou, ktera je uzita k identifikaci procesu, ktery je treba presunout do fronty s vyssi prioritou
4. Metodou, ktera je uzita k identifikaci procesu, ktery je treba presunout do fronty s nizsi prioritou
5. Metodou, ktera je uzita k identifikaci fronty, do ktere bude zarazen proces kdyz bude potrebovat CPU

• Planovani pomoci vice front se zpetnou vazbou je jednim z nejvyznamnejsich algoritmu planovani CPU. Muze byt konfigurovan pro libovolny specificky system, je velmi komplexni.

4.4. Planovani CPU ve viceprocesorovych systemech

• Vsechno planovani se az dosud tykalo vypocetniho systemu s jednim procesorem. Je-li k dispozici vice CPU, stava se problem planovani jeste vice rozsahlym a obtiznejsim. Bylo vyzkouseno mnoho technik, ale zadna neni otpimalni. Zminime nektere problemu tykajici se multiprocesoroveho planovani. Komplexni diskuse tohoto problemu je mimo ramec prednasky.

• Jsou-li vsechny procesory ve vypocetnim systemu stejne (homogenni system), potom libovolny procesor muze vykonyvat libovolny proces ve fronte. Jestlize jsou ve vypocetnim systemu procesory ruzne (heterogenni system), mohou byt na danem procesoru spusteny pouze procesy prelozene pro jeho instrukcni sadu. To se tyka zejmena distribuovanych systemu (viz. dale).

• Jsou-li vsechny procesory stejne, muze byt pouzita technika rovnomerneho vytizeni (load sharing). V tom pripade ma kazdy procesor svou frontu. Pri nerovnomernem planovani by se mohlo stat, ze jeden procesor ma frontu prazdnou a je spici, zatimco jiny je velmi zatizen. Aby se teto situaci predeslo vyuziva se jedna spolecna fronta pripravenych a z ni jsou procesy planovany pro jednotlive procesory.

• Planovani muze probihat podle jednoho ze dvou schemat:

1. Symetricky multiprocesing: Kazdy procesor je v planovani samostatny. Ma svou frontu pripravenych a sam rozhoduje, kteremu procesu bude pridelen. Jak bude rozebirano v dalsi kapitole muze nastat situace, kdy dva ruzne procesy na dvou ruznych procesorech chteji modifikovat taz data. OS musi byt v tomto pripade naprogramovan velmi opatrne. Je treba zajistit, aby dva procesory nevybraly stejny proces apod.

2. Asymetricky multiprocesing: Moznym resenim vyse uvedeneho problemu je dedikovat jeden procesor jako planovac ostatnich procesoru a vytvorit tak strukturu ridiciho a podrizenych (master - slave). Mnoho systemu doplnuje tento stupen jeste o dalsi a maji vsechna planovaci rozhodnuti, vsechnu I/O cinnost a dalsi aktivity systemu rizeny jednim vyhrazenym procesorem - master serverem a ostatni procesory pouze spousteji uzivatelsky kod. Asymetricky multiprocesing je jednodussi nez symetricky, protoze jen jeden procesor pracuje se systemovymi datovymi strukturami a tudiz neni zapotrebi definovat pravidla sdileni techto dat.

4.5. Planovani v realnem case

• Planovani v realnem case muze byt dvoji:

1. Tvrde pridelovani casu (hard real-time computing), ktere pozaduje pro kompletaci ulohy predem garantovane mnozstvi casu. Do takoveho systemu je proces odeslan s pozadavkem na mnozstvi casu, ktere potrebuje pro kompletaci nebo I/O operaci. V po teto dobe je proces bud dokoncen nebo vracen jako nepripustny. Tato metoda je znama jako metoda rezervovani zdroju (resource reservation). Tvrde pridelovani casu vyzaduje, aby planovac procesu vedel presne, jak dlouho trva ktera operace kazde operaci je potom garantovana maximalni pripustna doba. To je ovsem nemozne u systemu napr. s virtualni pameti, jak bude v budoucnu ukazano., protoze tyto systemy vyvolavaji nevyhnutelne a nepredvidatelne zmeny v mnozstvi casu nutneho k prubehu procesu. Proto je toto pridelovani casu uzivano u specialniho softwaru spusteneho na vyhrazenem hardwaru, kde neni treba vsech schopnosti moderniho OSu.

2. Mekke pridelovani casu (soft real-time computing) je mene omezujici. Vyzaduje pouze, aby kriticke procesy ziskaly vyssi prioritu nez ostatni. Z toho vyplyva, ze pridani mekkeho pridelovani casu do systemu sdileni casu muze vyvolat nespravedlive alokace zdroju, muze vest k delsim cekacim dobam nebo k moznosti umoreni procesu. Vysledkem je vsak univerzalni system podporujici multimedia, vysokorychlostni interaktivni grafiku a mnoho dalsich uloha, ktere by nemusely byt akceptovatelnem v jinem systemu bez podpory mekkeho pridelovani casu.

• Implementace mekkeho pridelovani casu musi byt velmi pecliva. OS musi mit planovani dle priority a procesy v realnem case musi mit vzdy prioritu vyssi. Cekaci doba pro prideleni (dispatch latency) musi byt co nejmensi. Cim je tato doba mensi, tim rychleji jsou procesy spousteny.

• Je relativne jednoduchy vyse uvedene podminky splnit. Je mozne zakazat aging, cimz se zajisti, ze priorita procesu se nebude menit. Druhy problem je mnohem komplikovanejsi. Problem je v tom, ze mnoho OSu, vcetne mnoha UNIXu je nuceno cekat na dokonceny systemoveho volani nebo I/O cyklu nez je mozno provest prepnuti kontextu. Cekaci doba pro prideleni muze byt v techto systemech dlouha, nebot mnoho systemovych volani je rozsahlych a mnoho I/O zarizeni je pomalych.

• Pro udrzeni nizke doby pro prideleni je nutno umozni preemptivni planovani systemovych volani. K tomu vedou ruzne cesty. Jednou z nich je vlozeni bodu nuceneho preruseni (preemption points) do dlouhych systemovych volani. Tento bod zjisti, jestli nemusi byt spusten nejaky proces s vysokou prioritou. Pokud ano, je mu preemptivne pridelen CPU a pote co je dokoncen pokracuje prerusene systemove volani. Bod nuceneho preruseni muze byt vlozen pouze na bezpecne misto, kdy neprobiha zmena systemovych dat. Dopad tohoto reseni vsak neni nijak oslnujici, protoze prakticky muze byt takovych bodu nuceneho preruseni vlozeno do systemovych volani jen velice malo.

• Jinou cestou je vytvorit cele jadro preemptivni. Vsechna systemova data musi byt chranena synchronizacnimi mechanismy proti poskozeni. Tato metoda je uzita u Solarisu 2.

• Co se vsak stane, bude-li chtit nejaky vysoce prioritni proces menit systemova data, ktera prave meni proces s nizsi prioritou? Proces s vyssi prioritou musi pockat na dokonceni procesu s prioritou nizsi - inverze priority.

• Na Obr. 51 je videt prubeh cekaci doby pro prideleni. Faze konfliktu ma 3 casti:

1. Preemptivni preruseni procesem jadra
2. Procesy s nizsi prioritou uvolnuji zdroje pozadovane vysoce prioritnimi procesy
3. Prepnuti kontextu od aktualniho procesu k procesu s vyssi prioritou

Obr. 51 Cekaci doba pro prideleni