Operaˇcn´ı syst´emy
Spr´ava procesoru Petr Krajˇca Katedra informatiky Univerzita Palack´ eho v Olomouci
11. bˇrezen, 2011
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
1 / 18
Procesy (1/2) neform´alnˇe: proces = bˇeˇz´ıc´ı program (vykon´av´a ˇcinnost) proces: pamˇet’ov´y prostor k´ od programu data – statick´a a dynamick´a (halda) z´asobn´ık registry
Obecn´ yˇ zivotn´ı cyklus procesu nov´y (new) – proces byl vytvoˇren pˇripraven´y (ready) – proces ˇcek´a, aˇz mu bude pˇridˇelen CPU bˇeˇz´ıc´ı (running) – CPU byl pˇridˇelen procesor a pr´avˇe prov´ad´ı ˇcinnost ˇcekaj´ıc´ı (waiting) – proces ˇcek´a na nˇejakou ud´alost (napˇr. na vyˇr´ızen´ı I/O poˇzadavku) ukonˇcen´y (terminated) – proces skonˇcil svou ˇcinnost
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
2 / 18
Procesy (2/2) multi-tasking: zd´anlivˇe soubˇeˇzn´y bˇeh v´ıce proces˚ u informace o procesu m´a OS uloˇzeny v process control block (PCB) obsahuje informace: identifikace procesu informace o stavu adresu instrukce, kterou bude program pokraˇcovat stav registr˚ u informace k pl´anov´an´ı proces˚ u informace o pˇridˇelen´e pamˇeti informace o pouˇzivan´ych I/O zaˇr´ızen´ıch, otevˇren´ych souborech, atd.
z´asadn´ı role pˇri pˇred´av´an´ı procesoru mezi procesy uloˇzen´ı stavu CPU (context switch) =⇒ jde ˇreˇsit softwarovˇe nebo s podporou HW kooperativn´ı vs. preemptivn´ı multitasking preemptivn´ı multitasking =⇒ velikost ˇcasov´eho kvanta potˇreba pl´anov´an´ı Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
3 / 18
Pl´anov´an´ı proces˚ u (1/2) Poˇ zadavky f´erovost – kaˇzd´emu procesu by v rozumn´e dobˇe mˇel b´yt pˇridˇelen CPU efektivita – maxim´aln´ı vyuˇzit´ı CPU maximalizace odveden´e pr´ace (throughput) minimalizace doby odezvy minimalizace doby pr˚ uchodu syst´emem (turnaround) Round robin kaˇzd´y proces m´a pevnˇe stanoven´e kvantum pˇripraven´e procesy jsou ˇrazeny ve frontˇe a postupnˇe dostavaj´ı CPU spravedliv´y Priority pˇripraven´e procesy jsou ˇrazeny podle priorit riziko vyhladovˇen´ı re´alnˇe se pouˇz´ıvaj´ı heuristick´e algoritmy sd´ılej´ıc´ı obˇe vlastnosti Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
4 / 18
Pl´anov´an´ı proces˚ u (2/2) R˚ uzn´ e typy u ´loh interaktivn´ı d´avkov´e zpracov´an´ı pracuj´ıc´ı v realn´em ˇcase intenzivn´ı na CPU vs. I/O Symmetric Multi-processing pˇrib´yv´a probl´em, jak vybrat procesor =⇒ pˇresun procesu =⇒ vypr´azdnˇen´ı cache ˇreˇsen´ı: oddˇelen´e planov´an´ı pro kaˇzd´y procesor nebo maska affinity (definuje procesor na kter´em m˚ uˇze proces bˇeˇzet)
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
5 / 18
Vl´akna (Threads) OS umoˇzn ˇuj´ı rozdˇelen´ı procesu na v´ıc vl´aken z´akladn´ı entitou vykon´avaj´ıc´ı program nen´ı proces, ale vl´akno proces se skl´ad´a z jednoho a v´ıce vl´aken kaˇzd´e vl´akno m´a sv˚ uj z´asobn´ık + registry =⇒ pˇrepnut´ı vl´aken v r´amci procesu rychlejˇs´ı vl´akna v r´amci procesu sd´ıl´ı pamˇet’ov´y prostor, data, prostˇredky =⇒ jednoduch´e sd´ılen´ı prostˇredk˚ u =⇒ nov´e probl´emy se synchronizac´ı Realizace vztah kernel thread - user thread kernel thread – vl´akno, jak jej v´ıd´ı OS user thread – vl´akno z pohledu uˇzivatelsk´eho prostoru 1:N – vl´akna jsou realizovan´a v uˇzivatelsk´em prostoru (probl´em s planov´an´ım) 1:1 – k jednomu vl´anku v uˇzivatelsk´em prostoru existuje jedno v jadern´em prostoru (nejˇcastˇejˇs´ı pouˇzit´ı) M:N – vl´akna v uˇzivatelsk´em prostˇred´ı jsou mapov´ana na menˇs´ı poˇcet jadern´ych vl´aken Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
6 / 18
Procesy a vl´akna v Unixech p˚ uvodnˇe z´akladn´ı entitou byl proces procesy tvoˇr´ı hierarchii rodiˇc-potomek (navrcholu je proces init) vytvoˇren´ı procesu pomoc´ı vol´an´ı fork(), kter´e vytvoˇr´ı klon procesu pˇreps´an´ı procesu pomoc´ı exec komunikace mezi procesy: zas´ıl´an´ı sign´al˚ u, roury, ... moˇznost nastavit niceness procesu (prioritu od -20 do 20) vl´akna do Unixu pˇrid´ana aˇz pozdˇeji (implementace se v r´amci r˚ uzn´ych OS liˇs´ı) v Linuxu (pthreads) vnitˇrnˇe implementov´any stejnˇe jako procesy (task), ale sd´ıl´ı pamˇet’ov´y prostor
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
7 / 18
Procesy a vl´akna ve Windows Windows NT navrˇzeny s vl´akny jako z´akladn´ı entitou pro bˇeh aplikace proces sdruˇzuje vl´akna, pl´anov´an´ı se u ´ˇcastn´ı vl´akno sofistikovan´y syst´em priorit pˇri pl´anov´an´ı vl´aken priorita vl´akna je odvozen´a od tˇr´ıdy priority procesu promˇenliv´a velikost kvant priority boost – dochaz´ı k doˇcasn´emu zv´yˇsen´ı priority po dokonˇcen´ı I/O operace po dokonˇcen´ı ˇcek´an´ı na semafor probuzen´ı vl´akna, jako reakce na UI vl´akno jiˇz dlouhodobu nˇebˇeˇzelo
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
8 / 18
Synchronizace vl´aken a proces˚ u pˇr´ıklad: pˇriˇcten´ı jedniˇcky dvˇema procesy 1 2 3 4 5 6 7
promˇenn´a X = 1 A: naˇcte hodnotu do registru A: zv´yˇs´ı hodnotu v registru o jedna B: nacte hodnotu do registru A: uloˇz´ı hodnotu do pamˇeti (X = 2) B: zv´yˇs´ı hodnotu v registry o jedna B: uloˇz´ı hodnotu do pamˇeti (X = 2)
ˇreˇsen´ı – atomick´e operace nebo synchronizace je potˇreba zajistit, aby v pr˚ ubˇehu manipulace s urˇcit´ymi zdroji s nimi nemohl manipulovat nˇekdo jin´y (vz´ajemn´e vylouˇcen´ı)
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
9 / 18
Atomick´y pˇr´ıstup do pamˇeti v´ıcevl´aknov´e aplikace/v´ıceprocesorov´e poˇc´ıtaˇce (+ out-of-order prov´adˇen´ı operac´ı) obecnˇe pˇr´ıstupy do pamˇeti nemus´ı b´yt atomick´e (z´aleˇzitost CPU) kl´ıˇcov´e slovo volatile – ˇcasto z´aleˇz´ı na pˇrekladaˇci memory barriers umoˇzn ˇuj´ı vynutit si synchronizaci (z´aleˇzitost CPU) Atomick´ e operace Compare-and-Swap (CAS): ovˇeˇr´ı jestli se dan´a hodnota rovn´a poˇzadovan´e a pokud ano, pˇriˇrad´ı ji novou (CMPXCHG) Fetch-and-Add: vr´at´ı hodnotu m´ısta v pamˇeti a zv´yˇs´ı jeho hodnotu o jedna (XADD) Load-link/Store-Conditional (LL/CS): naˇcte hodnotu a pokud bˇehem ˇcten´ı nebyla zmˇenˇena, uloˇz´ı do n´ı novou hodnotu umoˇzn ˇuj´ı implementovat synchronizaˇcn´ı primitiva na vyˇsˇs´ı u ´rovni
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
10 / 18
Synchronizaˇcn´ı primitiva slouˇz´ı k ˇr´ızen´ı pˇr´ıstupu ke sd´ılen´ym prostˇredk˚ um Peterson˚ uv algoritmus (umoˇzn ˇuje implementovat vz´ajemn´e vylouˇcen´ı dvou proces˚ u, pomoc´ı bˇeˇzn´ych operac´ı) Mutex & Kritick´ a sekce potˇrebujeme zajistit, aby k´ od pracuj´ıc´ı se sd´ılen´ymi zdroji mohlo pouˇz´ıt jen jedno vl´akno/proces =⇒ kritick´a sekce realizace pomoc´ı mutexu dvˇe operace: vstoupit do kritick´e sekce (pokud je v kritick´e sekci jin´y proces/vl´akno), proces ˇcek´a opustit kritickou sekci (pokud na vstup do kritick´e sekce ˇcek´a jin´e vl´akno), je v puˇstˇeno Semafor chr´anˇen´a promˇenn´a obsahuj´ıc´ı poˇc´ıtadlo s nez´aporn´ymi ˇc´ısly operace P: pokud je hodnota ˇc´ısla nenulov´a sn´ıˇz´ı hodnotu o jedna, jinak ˇcek´a, aˇz bude hodnota zv´yˇsena operace V: zv´yˇs´ı hodnotu o jedna Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
11 / 18
Deadlock uv´aznut´ı – syst´em se dostal do stavu, kdy nem˚ uˇze d´al pokraˇcovat Uˇ z´ıv´ an´ı prostˇredk˚ u request – poˇzadavek na prostˇredek, nen´ı-li k dispozici, proces ˇcek´a use – vl´akno s prostˇredkem pracuje release – uvolnˇen´ı prostˇredku pro dalˇs´ı pouˇzit´ı Podm´ınky vzniku Mutual exclusion – alespoˇ n jeden prostˇredek je v´yluˇcnˇe uˇz´ıv´an jedn´ım procesem Hold & wait – proces vlastn´ı alespoˇ n jeden prostˇredek a ˇcek´a na dalˇs´ı No preemption – prostˇredek nelze n´asilnˇe odebrat Circular wait – cyklick´e ˇcek´an´ı (proces A vlastn´ı prostˇredek 1, chce prostˇredek 2, kter´y drˇz´ı B a souˇcasnˇe ˇz´ad´a o 1)
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
12 / 18
ˇ sen´ı deadlocku (1/4) Reˇ Ignorace ,,neˇreˇsen´ı”, v praxi ˇcasto pouˇz´ıvan´e Detekce (detection & recovery) pokud vznikne deadlock, je detekov´an a nˇekter´y proces odstranˇen k detekci se pouˇz´ıv´a alokaˇcn´ı graf prostˇredk˚ u a graf ˇcek´an´ı alokaˇcn´ı graf: orientovan´y graf dva typy uzl˚ u – prostˇredek, proces hrana proces-prostˇredek – proces ˇcek´a na prostˇredek hrana prostˇredek-proces – prostˇredek je vlastnˇen procesem
graf ˇcek´an´ı vznikne vynech´an´ım uzl˚ u prostˇredk˚ u a pˇrid´an´ım hran Pn → Pm pokud existovaly hrany Pn → R a R → Pm , kde Pn a Pm jsou procesy a R je prostˇredek deadlock vznikne, pokud je v grafu ˇcek´an´ı cyklus Kdy m´a smysl prov´adˇet detekci? Jak vybrat obˇet’? Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
13 / 18
ˇ sen´ı deadlocku (2/4) Reˇ Zamezen´ı vzniku (prevention) snaˇz´ıme se zajistit, ˇze nˇekter´a z podm´ınek nen´ı splnˇena zamezen´ı v´yluˇcn´emu vlastnˇen´ı prostˇredk˚ u (ˇcasto nelze z povahy zaˇr´ızen´ı) zamezen´ı drˇzen´ı a ˇcek´an´ı proces zaˇz´ad´a o vˇsechny prostˇredky hned na zaˇcatku probl´em s odhadem pl´ıtv´an´ı a hladovˇen´ı mnoˇzstv´ı prostˇredk˚ u nemus´ı b´yt zn´am´e pˇredem jde pouˇz´ıt i v pr˚ ubˇehu procesu (ale proces se mus´ı vzd´at vˇsech prostˇredk˚ u)
zaveden´ı moˇznosti odejmout prostˇredek – vhodn´e tam, kde lze odejmout prostˇredky tak, aby neˇslo poznat, ˇze byly odebr´any zamezen´ı cyklick´emu ˇcek´an´ı – zaveden´ı glob´aln´ıho ˇc´ıslov´an´ı prostˇredk˚ u a moˇznost ˇz´adat prostˇredky jen v dan´em poˇrad´ı Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
14 / 18
ˇ sen´ı deadlocku (3/4) Reˇ Vyh´ yb´ an´ı se uv´ aznut´ı (avoidance) procesy ˇz´adaj´ı prostˇredky libovolnˇe syst´em se snaˇz´ı vyhovˇet tˇem poˇzadavk˚ um, kter´e nemohou v´est k uv´aznut´ı je potˇreba zn´at pˇredem, kolik prostˇredk˚ u bude vyˇz´ad´ano tomu je pˇrizp˚ usobeno pl´anovan´ı proces˚ u bezpeˇ cn´ y stav – existuje poˇrad´ı proces˚ u, ve kter´em jejich poˇzadavky budou vyˇr´ızeny bez vzniku deadlocku syst´em, kter´y nen´ı v bezpeˇcn´em stavu, nemus´ı b´yt v deadlocku syst´em odm´ıtne pˇridˇelen´ı prostˇredk˚ u, pokud by to znamenalo pˇrechod do nebezpeˇcn´eho stavu (proces mus´ı ˇcekat)
Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
15 / 18
ˇ sen´ı deadlocku (4/4) Reˇ Algoritmus na b´ azi alokaˇ cn´ıho grafu vhodn´y pokud existuje jen jedna instance kaˇzd´eho prostˇredku do alokaˇcn´ıho grafu pˇrid´ame hrany (proces-prostˇredek) oznaˇcuj´ıc´ı potenci´aln´ı ˇz´adosti procesu a prostˇredky ˇz´adosti a prostˇredek se vyhov´ı pouze tehdy, pokud konverze hrany na hranu typu (prostˇredek-je vlastnˇen-procesem) nepovede ke vzniku cyklu Bank´ eˇr˚ uv algoritmus vhodn´y tam, kde je vˇetˇs´ı poˇcet prostˇredk˚ u dan´eho typu na zaˇc´atku kaˇzd´y proces oznam´ı, kolik prostˇredk˚ u jak´eho typu bude maxim´alnˇe potˇrebovat pˇri ˇz´adosti o prostˇredky syst´em ovˇeˇr´ı, jestli se nedostane do nebezpeˇcn´eho stavu pokud nelze vyhovˇet, je proces pozdrˇzen porovn´avaj´ı se voln´e prostˇredky, s aktualnˇe pˇridˇelen´ymi a maxim´aln´ımi Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
16 / 18
Bank´eˇr˚ uv algoritmus (1/2) uvaˇzujme m prostˇredk˚ u a n proces˚ u matice n × m max – poˇcet prostˇredk˚ u, kter´e bude kaˇzd´y proces ˇz´adat assigned – poˇcet pˇriˇrazen´ych prostˇredk˚ u jednotliv´ym proces˚ um needed – poˇcet prostˇredk˚ u, kter´e bude kaˇzd´y proces jeˇste potˇrebovat (evidentnˇe needed = max − assigned)
vektory velikosti m E – poˇcet existuj´ıc´ıch prostˇredk˚ u P – poˇcet aktu´alnˇe drˇzen´ych prostˇredk˚ u A – poˇcet dostupn´ych zdroj˚ u (evidentnˇe A = E − P)
Algoritmus 1 najdi ˇ r´adek i v needed takov´y, ˇze needed[i] ≤ A, pokud takov´y nen´ı, syst´em nen´ı v bezpeˇcn´em stavu 2 pˇ redpokl´adej, ˇze proces skonˇcil a uvolnil sv´e zdroje, i.e., A ← A + assigned[i] 3 opakuj body 1 a 2, dokud nejsou odstranˇ eny vˇsechny procesy nebo nen´ı jasn´e, ˇze syst´em nen´ı v bezpeˇcn´em stavu Petr Krajˇ ca (UP)
KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
17 / 18
Bank´eˇr˚ uv algoritmus (2/2) A B C D E E = h6, 3, 4, 2i P = h5, 3, 2, 2i A = h1, 0, 2, 0i podm´ınku podm´ınku podm´ınku podm´ınku podm´ınku
K L M 3 0 1 0 1 0 1 1 1 1 1 0 0 0 0 assigned
splˇ nuje splˇ nuje splˇ nuje splˇ nuje splˇ nuje
Petr Krajˇ ca (UP)
N 1 0 0 1 0
proces proces proces proces proces
A B C D E
K L M 1 1 0 0 1 1 3 1 0 0 0 1 2 1 1 needed
N 0 2 0 0 0
D =⇒ odebr´an a A ← h2, 1, 2, 1i A =⇒ odebr´an a A ← h5, 1, 3, 2i B =⇒ odebr´an a A ← h5, 2, 3, 2i C =⇒ odebr´an a A ← h6, 3, 4, 2i E =⇒ odebr´an a A ← h6, 3, 4, 2i KMI/XOSY: Pˇredn´ aˇska III.
11. bˇrezen, 2011
18 / 18
