Pl anov an PB152 Operacn systemy Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/ Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý Verze: jaro 2017 Osnova prednasky Motivace: V multitaskingovych systemech existuje vce procesu pripravenych k behu procesoru je ve vypocetnm systemu (prakticky vzdy) mene nez procesu OS mus rozhodovat, ktery proces pobez jako prst, tj. kteremu procesu pridel (prp. na omezenou dobu) procesor Osnova: Zakladn pojmy Kriteria kvality planovan Planovac algoritmus FCFS, rezim fronty Planovac algoritmus SPF, prednost maj kratke procesy Prioritn planovac algoritmus, prednost maj prioritn procesy Planovac algoritmus Round-Robin, spravedlive cerpan kapacity CPU Planovan multiprocesoru Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 1 Klasi kace metod planovan Podle clovych objektu 2 planovan CPU { cl prednasky planuj se behy procesu / vlaken na CPU 2 IO planovan planuje se porad plnen pozadavku procesu na IO predmet hlubsho studia v PV062 Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 2 Klasi kace metod planovan podle casu uplatnen 2 kratkodobe, operativn planovan, hlavn cl prednasky kratkodoby planovac (operacn planovac, dispecer, dispatcher): rozhodovan, kteremu procesu /vlaknu OS pridel CPU vyvolavan velmi casto, destky { stovky milisekund, mus byt rychly samozrejma soucast spravy procesoru 2 strednedobe, takticke planovan Strednedoby planovac (takticky planovac) taktika vyuzvan omezene kapacity FAP pri multitaskingu, rozhodovan, ktere procesy mohou vyuzvat prostor hlavn pameti, logicky tudz nalez do spravy hlavn pameti rdic algoritmus techniky oznacovane pojmem swapping { vybra proces, ktery je nutne zaradit mezi odsunute procesy (odebra mu prostor ve FAP) a vybra odsunuty proces, kteremu lze opet pridelit prostor ve FAP Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 3 Klasi kace metod planovan podle casu uplatnen 2 dlouhodobe, strategicke planovan dlouhodoby planovac (strategicky planovac, job scheduler) ma se novy proces zaradit mezi aktivn procesy ? de nuje stupen multiprogramovan je vyvolavan rdce, nemus byt rychly muze byt soucast spravy procesu, soucasti rozhran OS, ... Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 4 Klasi kace metod planovan podle casu uplatnen Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 5 Pro pripomenut { stavovy diagram procesu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 6 Frontovy model metod planovan Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 7 Dlouhodobe planovan 2 Zadan ulohy ke zpracovan / programu se stane procesem a preda se do fronty pripravenych procesu dispecerovi 2 V nekterych OS se mohou zarazovat nove procesy mezi potlacene procesy, pak o jejich zarazen mezi pripravene procesy rozhoduje strednedoby planovac 2 V OS s moznost davkoveho zpracovan se nove zadane ulohy rad do fronty uloh na disku a z n dlouhodoby planovac vybra nove vytvareny proces udrzuje efektivn stupen multitaskingu porad vyberu muze byt typu { FCSF (first-come-first-served) { prioritn { urcene pozadavkem na vyvazenost IO a CPU cinnosti, ... Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 8 Dlouhodobe planovan 2 V interaktivne orientovanych systemech dlouhodoby planovac muze urcovat stav nasycenosti systemu a novym uzivatelum sdelovat nemoznost pripojen Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 9 Strednedoby planovac, odkladan (suspending) procesu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 10 Kratkodove planovan { prciny zskan/odebran CPU Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 11 Dals mozne klasi kace metod planovan Podle charakteru interakce s procesy 2 davkove planovan 2 planovan interaktivnch procesu 2 planovan procesu v real-time prostred Podle dynamiky aktualizace planu 2 nepreemptivn planovan, (planovan bez predbhan) provad se po dokoncen pripraveneho planu 2 preemptivn planovan, (planovan s predbhanm) provad se v okamziku zmeny stavu nektereho z procesu plan se dynamicky men Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 12 Kriteria (metriky) kvality planovan Uzivatelsky orientovana kriteria 2 Doba obratky, Turnaround time doba behu + doba cekan na zdroje vc. CPU vhodna mra pro davkove zpracovan prirozena je snaha o minimalizaci doby obratky v dimenzi doby cekan normalizovana doba obratky = doba obratky / doba behu 2 Doba reakce, Response time mra pro interaktivn systemy doba od zadan pozadavku do doby ocekavane reakce cl { snaha o minimalizaci pro co nejvets komunitu uzivatelu v interaktivne orientovanych systemech mvaj interaktivn ulohy prednost pred davkovymi ulohami Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 13 Kriteria (metriky) kvality planovan 2 Casove limity, Deadlines pokud jsou zadane, plnen ostatnch clu se mus upozadit vhodne pro real-time systemy 2 casova proporcionalita napr. cekan 45 s na uzavren modemoveho spojen je akceptovatelne doba reakce na spusten procesu z terminalu 45 s je neakceptovatelna Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 14 Kriteria / metriky kvality planovan Systemove orientovana kriteria 2 Propustnost, Throughput pocet procesu dokoncenych za jednotku casu prirozena je snaha o maximalizaci propustnosti pozadavek dosazen vysoke propustnosti nebyva kompatibiln s pozadavkem minimalizace doby obratky 2 Vyuzit CPU maximalizace ve vceuzivatelskych systemech pro real-time systemy a 1-uzivatelske systemy nepodstatne kriterium 2 Spravedlivost, Fairness porovnatelne procesy mus zskat porovnatelnou obsluhu pokud uzivatel nebo system nerekne jinak, maj vsechny procesy stejnou sanci, vc, ochrany pred starnutm Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 15 Kriteria / metriky kvality planovan 2 Prosazovan priorit uprednostnovan procesu oznacenych jako prednostn, prioritn 2 Vyrovnavan zateze oblast strednedobeho a dlouhodobeho planovan udrzovan vyuzitelnosti systemovych zdroju uprednostnovan procesu rdce vyuzvajcch kriticke, uzkopro love zdroje budou-li se uprednostnovat procesy vazane na CPU, budou IO casto v prostojch budou-li se uprednostnovat procesy vazane na IO, bude CPU casto v prostojch ideal { multiprogramovan se ucastn vhodny mix procesu vazanych na CPU a na IO Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 16 Vaha kriteri podle clove oblasti 2 Kriteria jsou nezavisla, nelze optimalizovat vsechny soucasne. 2 Interaktivn uzivatelske systemy pozaduj minimalizaci doby reakce { prepnan CPU mezi procesy mus byt caste, to zvysuje systemovou rezii, takze se snizuje propustnost minimalizaci doby obratky maximalizaci poctu interaktivnch uzivatelu (tj. i procesu) proporcionalitu plnen ocekavan uzivatelu (spravedlivost) systemech 2 Davkove systemy pozaduj maximalizaci propustnosti maximalizaci vyuzvan CPU Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 17 Vaha kriteri podle clove oblasti 2 Real-time systemy pozaduj dodrzovan casovych limitu, zamezen ztratam dat prepoveditelnost { zamezen degradace kvality v multimedialnch systemech 2 OS obecne pozaduj maximalizaci propustnosti minimalizaci dob obratek maximalizaci vyuzvan CPU pri zajisten proporcnho vyuzvan vsech komponent poctace spravedlivost odvozenou z prosazovane politiky zpracovan, dodrzovan priorit, ... minimalizaci potrebneho vykonu OS, minimalizaci systemove rezie Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 18 Pozadavky na planovan CPU 2 planovan mus racionalne zohlednovat ocekavan uzivatelu mejme 2 procesy: { korekce obrazovky po uzavren okna { odeslan e-mailu { zdrzen o 2s je akceptovatelne zdrzen korekce obrazovky po uzavren okna kvuli odeslan mailu o 2s je neakceptovatelne zdrzen odeslan mailu kvuli korekci obrazovky po uzavren okna o 2s je akceptovatelne 2 proces = strdan davek CPU (behu) a cekan na konec IO 2 maximalizace vyuzit CPU vyzaduje prokladan davek CPU ruznych procesu, pocet prokladan mus byt minimaln prepnut kontextu mezi procesy je slozite (100 K instrukc, ...) { prepnut z uzivatelskeho rezimu do privilegovaneho rezimu { uchovan stavu CPU { uchovan stavu procesu { obnova stavu procesu, ... Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 19 Pozadavky na planovan CPU 2 je zadouc uprednostnovan procesu orientovanych na IO (disk) trvale urychlovan CPU zpusobuje, ze vetsina procesu se stava vce vazana na IO (disk) 2 kdy vydavat planovac rozhodnut ? vytvoril se novy proces { ma bezet rodic nebo potomek ? proces skoncil { ktery proces ma bezet jak dals ? IO prerusen indikuje konec IO operace { { ma dale bezet proces cekajc na konec teto IO operace ? { ma dale bezet prave bezc proces ? { ma dale bezet uplne jiny proces ? uplynul planovany casovy interval { co dal ? Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 20 Planovac CPU, dispecer, soucast jadra OS 2 cl funkcionality { alokace CPU konkretnmu procesu / vlaknu 2 dispecer vybra mezi procesy, ktere sdl v hlavn pameti ty, ktere jsou pripravene k behu { ready 2 Planovac rozhodnut vydava v okamziku, kdy proces: vznika a rad se mezi pripravene procesy prechaz ze stavu bezc do stavu cekajc prechaz ze stavu cekajc do stavu pripraveny konc a nebo kdyz okoln podmnky indikuj potrebu zmeny alokace CPU, pak z rozhodnut dispecera muze nastat, ze proces prechaz ze stavu bezc do stavu pripraveny Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 21 Planovac CPU, dispecer 2 role v OS { po proveden vyzadane sluzby nekterym procesem nebo funkce aktivovane prerusenm se predava procesor procesu vybranemu kratkodobym planovacem 2 algoritmus predan: prepnut kontextu z kontextu OS na kontext procesu vc. prepnut rezimu procesoru na uzivatelsky rezim nale predan { skok na odpovdajc msto v uzivatelskem programu pro restart procesu (urcuje obraz ctace instrukc v PCB) 2 dispecerske zpozden { obvykla de nice doba, kterou potrebuje OS pro pozastaven behu jednoho procesu a pro start behu jineho procesu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 22 Studovane planovac politiky / algoritmy 2 Chovan systemu vymezuje politika, chovan planovacho systemu vymezuje planovac politika 2 Planovac politiku implementuje planovac algoritmus 2 Planovac algoritmus je realizac vyberove funkce 2 Vyberova funkce vybra proces z fronty pripravenych procesu Charakteristiky vyberove funkce w { waiting, doba cekan, doba ve fronte pripravenych procesu e { execution, doba behu procesu na CPU s { process service time, ocekavana doba realizace procesu, doba potrebna pro realizaci procesu urcena / odhadnuta uzivatelem, zahrnuje e Napr. max (w) je implementac politiky FCFS Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 23 Studovane planovac politiky / algoritmy 2 Planovan monoprocesorovych systemu First-Come, First-Served (FCFS) Round Robin, RR, cyklicke planovan Shortest-Proces-Next (SPN) Shortest-Remaining-Time-First (SRT) Prioritn planovan Planovan s vce frontami Fair Share Scheduler (FSS) 2 Planovan homogennch multiprocesoru Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 24 Studovane planovac politiky Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 25 Procesy pouzite pri studovan planovacch politik Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 26 First-Come, First-Served (FCFS) 2 take first-in-first-out (FIFO), resp. prsny frontovy rezim 2 Nepreemptivn politika, uvolneny procesor se prideluje procesu, ktery je ve fronte pripravenych procesu nejdele 2 Jednoducha implementace 2 Vhodne pro dlouhe procesy, uprednostnuj se procesy orientovane na CPU pred procesy orientovanymi na IO Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 27 Round Robin (RR), cyklicke planovan 2 preemptivn planovan typu FCFS zalozene na sledovan casovych intervalu 2 Kazdy proces dostava CPU cyklicky na malou jednotku casu { casove kvantum, q q = destky az stovky ms 2 po uplynut doby q je bezc proces predbehnuty nejstarsm procesem ve fronte pripravenych procesu a dosud bezc proces se zarazuje na konec teto fronty 2 je-li ve fronte pripravenych procesu n procesu, pak kazdy proces zskava 1/n-tinu doby (vykonu) CPU, najednou zskava CPU nejvyse na dobu delky q Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 28 Round Robin (RR), cyklicke planovan 2 Zadny proces neceka na pridelen CPU dele nez (n − 1)q 2 Vykonnostn hodnocen: q velmi velke { planovan se blz principu FCFS q velmi male { kratke procesy se budou rychleji ukoncovat, ale CPU se venuje prevazne prepnan kontextu procesu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 29 Round Robin (RR), cyklicke planovan 2 efektivn politika pro interaktivn vceuzivatelske systemy a pro transakcn zpracovan 2 Prumerna doba obratky se muze zlepsit, pokud vetsina procesu se dobe q ukonc 2 zlate pravidlo volby q { 80% davek CPU by melo byt < q Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 30 Round Robin (RR), cyklicke planovan 2 procesy orientovane na CPU zskavaj nefer vyhodu, plne vyuzvaj pridelene kvantum 2 procesy orientovane na IO obvykle kvantum nevyuzij a po ukoncen IO cekaj ve fronte pripravenych procesu resenm je prioritn planovan procesu orientovanych na CPU Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 31 Round Robin (RR), cyklicke planovan Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 32 Shortest-Process-Next (SPN) 2 Metoda jak redukovat nevhodne chovan disciplny FCFS 2 K de nici procesu se dopln delka jeho (prst) CPU davky 2 Vybra se { proces s nejkrats (prst) dobou davky CPU { resp. proces, ktery se ukonc nejdrve 2 pravdepodobne mohou starnout dels procesy 2 davka CPU se mus znat, { velikost muze udavat vlastnk procesu { velikost lze odhadovat na zaklade chovan procesu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 33 Shortest-Process-Next, Shortest-Remaining-Time-Next 2 Pouzvaj se dve varianty: nonpreemptivn, bez predbhan, Shortest-Process-Next (SPN) jakmile se CPU preda vybranemu procesu, tento nemuze byt predbehnuty zadnym jinym procesem, dokud svoji davku CPU nedokonc (nevycerpa pridelene kvantum casu procesoru) preemptivn, s predbhanm, Shortest-Remaining-Time-First (SRT) jakmile se ve fronte ready objev proces s delkou davky CPU krats nez je doba zbyvajc k dokoncen davky prave bezcho procesu, novy proces ,,predbehne"prave bezc proces 2 pokud je kriteriem kvality planovan prumerna doba cekan, je preemptivn varianta (tj. SRT) optimaln algoritmus { pro danou mnozinu procesu zarucuje minimaln prumernou dobu cekan Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 34 Shortest-Process-Next, Shortest-Remaining-Time-Next Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 35 Jak urcit (odhadnout) delku (prst) davky CPU procesu 2 Skutecny proces nemus odhadovanou davku CPU (pridelene kvantum casu procesoru) vyuzt (napr. vyvola I/O operaci a pridelenou dobu CPU nedocerpa, skonc drve, ...) 2 Delka prst davky CPU skutecneho procesu se zna presne jen ve specialnch prpadech, delku prst davky CPU skutecneho procesu lze pouze odhadnout 2 Zkusenostmi proverena heuristika { odhad pravdepodobne delky prst davky CPU se odvod z historie chovan procesu mus se znat predchoz odhady delky davek CPU mus se znat jak proces vyuzval pridelena kvanta CPU pouzije se exponencialn prumerovan, klasicke prumerovan odhaduje budouc chovan nepresne Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 36 Exponencialn prumerovan { tn ...skutecna delka n-te davky CPU { τn+1 ...odhad delky prst davky CPU { Klasicke prumerovan: τn+1 = 1 n n i=1 ti { Exponencialn prumerovan: τn+1 = αtn + (1 − α)τn { α, 0 ≤ α ≤ 1 ...parametr vlivu historie { inicialn odhad: τ0 = 10 { vliv historie: α = 1/2 { τn+1 = 0.5tn + 0.5τn = = 0.5(tn + τn) τ0 se vol jako prumerna delka CPU davky v systemu nebo se odvod z typu programu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 37 Exponencialn prumerovan { analyza vlastnost 2 cm je α mens, tm ma historie na odhad mens vliv, α = 0 , τn+1 = τn, procesu se prideluj konstantn doby CPU 2 cm je α vets, tm vce se respektuje (kratka) historie α = 1, pro pridelen doby CPU je urcujc pouze skutecna posledn CPU davka, τn+1 = tn 2 Kdyz formuli τn+1 = αtn + (1 − α)τn rozvineme (τn = αtn−1 + (1 − α)τn−1, ...) dostaneme pro obecne α τn+1 = αtn + (1 − α)αtn−1+ ... +(1 − α)j αtn−j+ ... +(1 − α)n τ0 τ0 se vol jako vhodna konstanta, τ0 = 0 prioritizuje nove procesy Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 38 Exponencialn prumerovan { analyza vlastnost Ponevadz α a (1 − α) jsou hodnoty ≤ 1, kazdy dals term ma na τn+1 mens vliv nez jeho predchudce Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 39 Exponencialn prumerovan vs. jednoduche prumerovan Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 40 Exponencialn prumerovan vs. jednoduche prumerovan Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 41 Highest Response Ratio Next (HRRN) 2 Vybra se proces s nejvetsm pomerem skutecne a ocekavane doby existence procesu R, normalizovana doba obratky,R = max(w+s s ) 2 Atraktivn algoritmus, protoze pocta s dobou existence procesu preference dele cekajcch kratsch procesu, ale pri zachovan moznosti pozdejsho vtezstv i delsch procesu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 42 Prioritn planovan 2 s kazdym procesem je spojeno prioritn cslo (integer) prioritn cslo { preference procesu pri vyberu prste bezcho procesu CPU se prideluje procesu s nejvyss prioritou nejvyss priorite obvykle odpovda nejnizs prioritn cslo 2 Pouzvaj se dve varianty: nonpreemptivn, bez predbhan jakmile se CPU vybranemu procesu preda, tento, dokud davku CPU nedokonc, nemuze byt predbehnut zadnym jinym procesem preemptivn, s predbhanm jakmile se ve fronte pripravenych objev proces s prioritou vyss, nez je priorita prave bezcho procesu, novy proces predbehne prave bezc proces Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 43 Prioritn planovan 2 SPN je prioritn planovan, prioritou je predpovdana delka prst CPU davky 2 Problem: starnut procesy s nizs prioritou se nemus nikdy provest 2 Resen starnut: zran procesu napr. priorita procesu se s postupem casu (doby cekan, ...) zvysuje, HRRN Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 44 Planovan s vceurovnovymi frontami 2 frontu pripravenych procesu lze delit napr. do dvou front: fronta prednostn (foreground) { interaktivn fronta procesu na pozad (background) { davkova 2 kazde fronte nalez speci cky planovac algoritmus, napr. prednostn fronta (interaktivn) { RR fronta na pozad (davkova) { FCFS 2 jine mozne delen fronty pripravenych procesu: systemove procesy (OS) interaktivn aplikacn procesy clove aplikace interaktivn editacn procesy clove aplikace (prprava programu, dat, ...) davkove procesy clove aplikace (tydenn plany, ...) ostatn procesy (hry, studenske ulohy, ...) Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 45 Planovan s vceurovnovymi frontami, 2 2 mus se uplatnit vhodna politika planovan, tj. rozhodovan, kdy se provad vyber z jedne a kdy z druhe (dals) fronty pevne prioritn planovan napr. pro prvy prklad na minule obrazovce { { davkova fronta se obsluhuje jen kdyz je interaktivn fronta prazdna { ex. hrozba starnut procesu v davkove fronte ! casove rezy { pro obsluhu kazde fronty se venuje jisty dl casu CPU, po ktery planovac procesy vybra z te ktere fronty { napr. 80 % casu CPU pro interaktivn ulohy s planovanm typu RR 20 % casu CPU pro davkove ulohy s planovanm typu FCFS Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 46 Zpetnovazebn planovan s vceurovnovymi frontami 2 planovac muze procesy mezi frontami presouvat 2 zpetna vazba { planovac zna charakteristiky behu procesu 2 takto lze implementovat zran procesu 2 Planovac s vceurovnovymi zpetnovazebn frontami lze de novat napr. nasledujcmi parametry pocet front planovac algoritmus kazde fronty metoda pouzita pro urcen kdy proces prelozit mezi procesy s vets preferenc (napr. po interakci) metoda pouzita pro urcen kdy proces prelozit mezi procesy s mens preferenc (napr. po plnem vycerpan casoveho kvanta) metoda pouzita pro urcen do ktere fronty bude proces vstupovat kdyz pozaduje provest nejakou sluzbu (napr. vstoup do faze krizoveho rzen aplikace) Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 47 Zpetnovazebn planovan s vceurovnovymi frontami Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 48 Zpetnovazebn planovan s vceurovnovymi frontami Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 49 Fair Share Scheduler (FSS) 2 Planovan v nekterych OS typu Unix 2 Cl { dat spravedlivou sanci procesum na bazi prslusnosti procesu do skupin Procesy se del do skupin napr. na bazi prslusnosti k uzivatelum Kazdemu uzivateli je pridelovana jista cast vykonu procesoru, kdo ho vyuzva vce nez je spravedlive, bude dostavat mene, kdo ho vyuzva mene nez je spravedlive, bude dostavat vce Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 50 Fair Share Scheduler (FSS) 2 Princip planovan je prioritn skupina procesu k vyuzva dl vykonu procesoru Wk koncept spravedlivosti { priorita procesu klesa s rustem doby pouzvan procesoru { procesem a { skupinou, do ktere proces patr skupine s vets vahou Wk, klesa pouzvanm CPU priorita pomaleji oznacovan priority { vyss prioritn cslo znamena nizs prioritu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 51 Fair Share Scheduler (FSS) prioritn cslo P i j procesu j patrcho skupine k v casovem intervalu i je dane vztahem: P i j = Bj + CP Ui−1 j 2 + GCP Ui−1 k (4Wk) kde Bj je bazova priorita procesu j CP Ui−1 j exponencialne vazeny prumer pouzvan procesoru procesem j v casovem intervalu i − 1 GCP Ui−1 k exponencialne vazeny prumer pouzvan procesoru skupinou k v casovem intervalu i − 1 Pro vypocty exponencialne vazenych prumeru se pouzva α = 1/2: CP Ui j = Ui−1 j 2 + CP Ui−1 j 2 , GCP Ui j = GUi−1 j 2 + GCP Ui−1 j 2 kde Ui−1 j je pouzit procesoru procesem j v intervalu i − 1 GUi−1 k je pouzit procesoru skupinou k v intervalu i − 1 Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 52 Zpetnovazebn planovan s vceurovnovymi frontami Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 53 Klasi kace multiprocesorovych systemu 2 Multiprocesor { poctac vybaveny vce procesory (CPU, IO procesor, ...) 2 Distribuovany multiprocesor, cluster kolekce relativne autonomnch systemu, kazdy se svou hlavn pamet a se svym IO podsystemem propojen st, typicky model klient-server 2 Funkcne specializovane procesory, asymetricky multiprocesor hlavn, univerzaln procesor + specializovane procesory realizujc procesy poskytujc sluzby (IO, ...) procesum hlavnho procesoru 2 Homogenn multiprocesor (HMP), uzce vazany multiprocesor symetricky multiprocesor skupina procesoru sdlejcch spolecnou hlavn pamet' a integrovane rzenych operacnm systemem Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 54 Planovan homogennho multiprocesoru (HMP) 2 Predmet studia { nezavisly paralelismus, planovan soubezneho resen vzajemne nezavislych procesu na HMP 2 Prirozene rozsren monoprocesoroveho prostred na multiprocesor 2 Planovan HMP zahrnuje vzajemne zavisle problemy pridelovan procesu k procesorum pouzit multitaskingu na jednotlivych procesorech vyber konkretnho procesu, jak vybrat z fronty pripravenych procesu ? Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 55 Planovan homogennho multiprocesoru (HMP) Pridelovan procesu procesorum v HMP 2 Procesory tvor bank a z banku se prideluj na zadost 2 Staticke pridelen procesu k procesoru pro kazdy procesor se udrzuje individualn fronta pripravenych procesu vhodne pro skupinove (gangove) planovan, detaily pozdeji 2 Dynamicke pridelovan procesu k procesoru udrzuje je globaln fronta pripravenych procesu, spolecna pro vsechny procesory kazdy proces muze strdave bezet na kteremkoliv procesoru vhodne pro dynamicke vyrovnan zateze (load balancing) Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 56 Planovan homogennho multiprocesoru (HMP) Kdo o pridelen rozhoduje ? 2 jediny, centraln (master) procesor res opakovane dostupnou planovac sluzbu z jadra OS na zadost generovanou uvolnenm podrzeneho procesoru 2 kterykoliv uvolneny procesor, symetricky multiprocesing udrzuje se jedna centraln fronta pripravenych procesu / sledu kazdy volny procesor si sam vyhledava prst sled presneji { kopie OS bezc na procesoru si sama vyhledava ... uvolneny procesor res nasobne dostupnou planovac sluzbou jadra OS, coz vyzaduje pouzvat vzajemne vylucovan v jadru Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 57 Planovan homogennho multiprocesoru (HMP) 2 Provozovat multitasking na jednotlivych procesorech HMP ? pokud je dostupnych mnoho procesoru nen dulezite, aby byl kazdy procesor vyuzvan co mozna nejvce 2 Jak vybrat z fronty pripravenych procesu / vlaken v HMP pri planovan na urovni procesu co nejjednoduss vyber { FIFO pri planovan na urovni vlaken se pouzvaj speci cke techniky, prioritn vyber ci vyber na zaklade sledovan historie nejsou pro planovan vlaken vyhodne politiky Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 58 Planovan vlaken v HMP 2 Sdlen zateze, load sharing kazdy procesor muze realizovat kterekoliv vlakno, procesy nejsou prideleny zadnemu konkretnmu procesoru globaln fronta ready, vyber z fronty { FIFO nebo prioritne (priorita klesa s rustem poctu vlaken v procesu) predbehnute sledy pravdepodobne nebudou pokracovat na stejnem procesoru { nelze proto pouzvat ,,cache"pameti procesoru jestlize jsou vsechna vlakna procesu v jedne spolecne fronte ready, pravdepodobne nebudou spustena najednou (paralelne) 2 Gangy technika planovan zarucujc soucasny beh vce sledu 1 procesu na vce procesorech vhodne pro aplikace jejichz vykon klesa, pokud se neres paralelne { napr. rozpoznavan sceny Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 59 Planovan vlaken v HMP 2 Dedikovane pridelen, opak sdlen zateze pri vytboren procesu se pridel kazdemu vlaknu procesor pri cekan vlakna na IO je procesor v prodleve, zadny multitasking na pridelenych procesorech v systemech s tisci ci stovkami procesoru nen vyuzit procesoru metrikou efektivnosti eliminace planovan v prubehu procesu muze vyznamne urychlit proveden procesu Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 60 Planovan v systemu Windows 2 V jadru neexistuje centraln planovac vlakno kdyz vlakno nemuze pokracovat v behu, vstupuje do rezimu jadra a provad program planovace a zjist'uje kteremu vlaknu se preda rzen 2 Vlakno nemuze pokracovat v behu kdyz mus cekat na udalost, semafor, mutex, IO, ..., signalizuje udalost (zveda semafor, ...) vycerpalo pridelene casove kvantum behu na CPU (doslo k prerusen casovacem) 2 Planovac se rovnez vyvolava kdyz se dokonc IO operace uplynul interval casove omezeneho cekan Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 61 Windows { Planovan je prioritn pro nastaven Real-time priority mus mt uzivatel specialn opravnen aplikacn vlakna maj priority 15 { 1 bazova priorita vlakna = priorita procesu bezna priorita vlakna = bazova priorita + relativn korekce priority Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 62 Windows { Planovan, korekce priorit 2 Nejvyss prioritn uroven je planovana v rezimu round-robin, cyklicke planovan 2 Navysen priority vlakna, prklady po dokoncen ocekavane IO operace + 1: disk, +2: komunikace, +6: klavesnice, +8: zvukova karta po udalosti, zvednut semaforu, ...: + 1 2 Snizovan priority vlakna kdykoliv vlakno vycerpa casove kvantum CPU az do urovne bazove priority Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 63 Prklad planovan { Linux, planovan procesu Linux pouzva dva algoritmy pro planovan procesu: 2 algoritmus pro spravedlive casove sdlen umoznujc predbhan (fair preemptive scheduling algorithm) kazdy proces zska jisty pocet kreditu pri kazdem prerusen casovacem ztrac bezc proces 1 kredit proces s 0 kredity se vzdava CPU jakmile neexistuje zadny pripraveny proces s kredity, provede se rekreditace, ktera prida kredity vsem procesum v systemu, nejen pripravenym, podle pravidla kredity = kredity/2 + priorita 2 real-time algoritmus pro resen tech ukolu, pro ktere je mnohem dulezitejs absolutn priorita pred spravedlivost neimperativn (soft) real-time Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 64 Prklad planovan { Linux, planovan procesu, 2 2 O aplikaci toho ktereho planovacho algoritmu rozhoduje planovac trda procesu (process’s scheduling class) 2 Linux implementuje FIFO planovac trdu a round-robin real-time planovac trdu 2 V obou variantach ma proces navc i prioritu 2 Planovac spoust proces nejvyss priority 2 Na stejne prioritn urovni se vybra podle doby cekan (FIFO) 2 Procesy pl´anovac´ı tˇr´ıdy FIFO bez dokud neskonc nebo se nezablokuj 2 Procesy round-robin real-time pl´anovac´ı tˇr´ıdy jsou po uplynut casovych kvant predbhane a rad se na konec planovac fronty round-robin procesy stejne priority se spravedlive strdaj v behu automaticky Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 65 Prklad planovan { Linux, planovan procesu, 3 2 V Linuxu se planovanm oznacuje i spousten ruznych ,,procesu jadra\ (tasks) spousten procesu jadra pozadovana behem normalnch procesu spousten procesu jadra vynucena drivery zarzen Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 66 Planovan javovskych sledu 2 JVM pouzva prioritn preemptivn planovan 2 na stejne prioritn urovni se aplikuje princip FIFO 2 JVM planuje beh sledu kdyz: bezc sled se vzdava prava bezet bezet { konec sledu { sled vystupuje z metody typu run(), { cekan na udalost { napr. na konec I/O operace se stane pripravenym sled vyss priority nez bezc sled Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 67 Planovan javovskych sledu 2 sledum se prideluje stejne kvantum casu 2 pokud podpurny OS nepodporuje RR planovan, ex. nastroje pro sdelen JVM, ze zbytek prideleneho kvanta nepotrebuje a lze proto planovat dals kvantum dalsmu sledu { thread.yield() { planuje se beh dalsho sledu stejne priority 2 sledu je priorita pridelena pri jeho vytvoren 2 JVM priority dynamicky nemen Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Pl anov an 68