Uv aznut
PB152 Operacn systemy
Jan Staudek
http://www..muni.cz/usr/staudek/vyuka/
Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý
Verze: jaro 2017
Osnova prednasky
2 Prklady ,,ze zivota"
2 Model
2 Charakteristika uvaznut
2 Metody zvladan uvaznut
2 Prevence uvaznut
2 Obchazen uvaznut
2 Detekce uvaznut
2 Obnova po uvaznut
2 Kombinovany prstup ke zvladan uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 1
Problem uvaznut
When two trains approach each other at a crossing, both shall come to
a full stop and neither shall start up again until the other has gone.
Statute passed by the Kansas State Legislature,
early in the 20th century.
2 Existuje mnozina blokovanych procesu:
{ kazdy vlastn nejaky prostredek (zdroj) a
{ kazdy ceka na zdroj drzeny jinym procesem
z teto mnoziny
2 prklad
v systemu se provozuj dva mechanismy pridelovanych disku
v systemu existuj dva procesy
kazdy z procesu vlastn 1 mechanismus a pozaduje alokaci dalsho
2 Univerzaln efektivn resen problemu uvaznut neexistuje
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 2
Problem uvaznut { souperen o zdroj
Auta (procesy) souper o v yhradn zsk an prostoru pro prejezd krizovatky (zdroj)
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 3
Problem uvaznut { souperen o zdroj
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 4
Prklad resen uvaznut odebranm zdroje
2 kazdy vjezd na most lze chapat jako zskan zdroje
2 Dojde-li k uvaznut, lze ho resit tm, ze se jedno auto vrat
2 uplatnila se preempce zdroje { (preemption a rollback)
(privlastnen si zdroje, vlastneneho nekym jiny)
a vracen soupere pred zadost o pridelen zdroje
2 Pri resen uvaznut
muze se vracet i vce vozu, zdroj lze odebrat vce procesum
muze dochazet ke starnut konkretnho auta,
pokud se toto bude opakovane vracet
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 5
Kategorie zdroju
2 Zdroje pouzitelne pouze vylucne, opakovane, reusable
v jednom case pouzitelne jedinym procesem
pouzitm zdroje se zdroj nevycerpa, existuje dal
Procesor, kanal, IO zarzen, soubor, zaznam, ...
predchoz prklady pouzvaj opakovane pouzitelne zdroje
2 Zdroje spotrebovavane, consumable
vznikaj generovanm a zanikaj zprstupnenm
prerusen, signaly, zpravy, ...
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 6
Dva procesy souper o opakovane prstupny zdroj
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 7
Dva procesy souper o opakovane prstupny zdroj
2 prostor v pameti lze pouzvat jako opakovane pouzitelny zdroj
2 prklad uvaznut pri pridelovan pameti
dostupna kapacita 200 MB
P0: P1:
rqst(80KB); rqst(70KB);
... ...
rqst(60KB); rqst(80KB);
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 8
Prklad uvaznut pri pouzit spotrebovavaneho zdroje
2 prklad uvaznut pri vymene zprav, cekanm na udalost
operace receive je synchronn, konc prijetm zpravy
P0: P1:
... receive(P0, q);
... ...
receive(P1, m); ...
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 9
Denice uvaznut a starnut
2 uvaznut
mnozina procesu P uvazla,
jestlize kazdy proces Pi z P ceka na udalost
(uvolnen prostredku, zaslan zpravy),
kterou vyvola pouze nektery procesu z P
prostredek { pamet'ovy prostor, IO zarzen, soubor,...
2 starnut
Pozadavky 1 nebo vce procesu z P nejsou dlouhodobe plneny
napr. z duvodu priorit, prevence uvaznut apod.
dlouhodobe =
dele nez je akceptovatelne pro resenou aplikacn ulohu,
bez zaruky za splnen v konecnem case, ...
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 10
Postupovy prostor s moznost uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 11
Postupovy prostor bez moznosti uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 12
Charakteristika uvaznut
K uvaznut dojde, kdyz soucasne plat
4 nasledujc podmnky (3x nutna, posledn postacujc):
2 vzajemne vyloucen, Mutual Exclusion
sdleny zdroj muze v jednom okamziku pouzvat pouze jeden proces
2 pozadavky se uplatnuj postupne, Hold and Wait
proces vlastnc alespon jeden zdroj ceka na zskan dalsho zdroje,
dosud vlastneneho jinym procesem
2 nepripoust se predbhan, No preemption
zdroj lze uvolnit pouze procesem, ktery ho v dane dobe vlastn
2 doslo k zacyklen pozadavku, Circular wait:
existuje posloupnost n cekajcch procesu {P0, P1, . . . , Pn−1}
takovych, ze P0 ceka na (uvolnen zdroje drzeneho) P1,
P1 ceka (na uvolnen zdroje drzeneho) P2, ... a
Pn−1 ceka (na uvolnen zdroje drzeneho) P0.
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 13
Pouzity model
2 Typy zdroju R1, R2, . . . , Rm
casove dly CPU, prostor pameti, I/O zarzen, ...
2 Kazdy zdroj Ri ma Wi instanc
2 Kazdy proces pouzva zdroj podle nasledujcho schematu
zadost o pridelen zdroje, Request (Get)
pouzit zdroje (po konecnou dobu)
uvolnen zdroje, Release
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 14
Graf pridelen zdroju
2 Resource-Allocation Graph, RAG
2 mnozina uzlu V a mnozina hran E
2 V se del do dvou typu:
P = {P1, P2, . . . , Pn}, mnozina procesu existujcch v systemu
R = {R1, R2, . . . , Rm}, mnozina zdroju existujcch v systemu
2 hrana pozadavku { orientovana hrana Pi → Rj
2 hrana pridelen { orientovana hrana Ri → Pj
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 15
Graf pridelen zdroju, RAG
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 16
Prklad RAG { cyklicke retezen
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 17
Prklady RAG
bez uvaznut s uvaznutm
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 18
Prklad RAG { s cyklem a bez uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 19
Cyklus v RAG a uvaznut
2 Jestlize se v RAG nevyskytuje cyklus { k uvaznut nedoslo
2 Jestlize se v RAG vyskytuje cyklus,
{ a existuje pouze jedna instance
zdroje daneho typu { k uvaznut doslo
{ a existuje vce instanc
zdroje daneho typu { k uvaznut muze dojt
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 20
Wait-for-Graph, WFG
2 Zavislost pouze mezi procesy
2 Uzel { proces,
2 Orientovana hrana u → v,
u ceka na uvolnen zdroje drzeneho v
2 System procesu uvazl, pokud je ve WFG cyklus
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 21
Metody zvladnut uvaznut
2 Ochrana pred uvaznutm prevenc
system se nikdy nedostane do stavu uvaznut,
rus se platnost nektere nutne podmnky
apriorn eliminace nektere nutne podmnky navrhovym rozhodnutm
2 Obchazen uvaznut
detekce potencialn moznosti vzniku postacujc podmnky uvaznut a
nepripusten takoveho stavu
prostredek se nepridel, pokud by hrozilo uvaznut =⇒ hroz starnut
2 Detekce uvaznut a obnova po uvaznut
detekce uvaznut, napr. analyzou RAG,
a obnova stavu bez uvaznut
2 Ignorovan hrozby uvaznut
resen uplatnene v univerzalnch OS { Unix, Windows, ..
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 22
Metody zvladnut uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 23
Metody zvladnut uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 24
Ochrana pred uvaznutm prevenc
konzervativn politika { omezuje se zpusob proveden pozadavku
2 moznosti
neprme metody { zneplatnen nektere nutne podmnky
prma metoda { nepripusten platnosti postacujc podmnky
(cyklus v grafu) usporadanm porad pridelovan prostredku
2 neprme metody
nepouzvan sdlenych zdroju, virtualizace prostredku (spooling), ...
ne vzajemna vylucnost
kdykoliv proces neco pozaduje, nesm vlastnit zadny jiny prostredek,
napr. pozaduje vsechny prostredky najednou pri svem vytvoren nebo
uvolnovan dosud drzenych prostredku pred zadost dalsho
prostredku { ne postupne uplatnovan pozadavku
odebran prostredku procesu spravcem, zarazen procesu do cekac
fronty, aktivace procesu pri dostupnosti potrebnych prostredku {
pripoust se predbhan, preemption
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 25
Prevence uvaznut, neprme metody
2 ne vzajemne vyloucen
aplikovatelne pro procesy uzvajc zdroje, ktere lze sdlet,
napr. pouzvan sdlenych zamku pri cten objektu v databazi
neaplikovatelne pri pouzvan opakovane dostupnych zdroju,
modikace sdleneho objektu v databazi vyzaduje aplikaci
exkluzivitnho zamku
nekdy lze resit virtualizac prostredku, pokud to jde (tiskarny, ...)
obecne neuplatnitelne resen
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 26
Prevence uvaznut, neprme metody
2 ne postupna alokace
proces zadajc nejaky zdroj nesm nevlastnit zadny jiny zdroj
proces mus pozadat o vsechny pozadovane zdroje a obdrzet je drve
nez se spust jeho beh nebo o ne sm zadat pouze tehdy,
kdyz zadne zdroje nevlastn
dusledek
{ nzka efektivita vyuzit zdroju
{ moznost starnut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 27
Prevence, neprme metody
2 ne predbhan
necht' proces drzc nejake zdroje pozaduje pridelen dalsho zdroje,
ktery mu nelze pridelit okamzite (zdroj nen volny)
spravce prostredku napr. odebere procesu vsechny jm drzene zdroje
v tomto okamziku, ,,odebrane\ zdroje zapse do seznamu zdroju,
na ktere proces ceka a proces bude obnoven pouze kdyz muze zskat
jak jm puvodne drzene zdroje, tak jm nove pozadovany zdroj
spravce prostredku muze nekteremu z uvazlych procesu
z duvodu cekan na jisty zdroj tento zdroj odebrat a uvolnit,
proces usp a obnov pozdeji, az bude pozadovany zdroj uvolneny
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 28
Prevence, prma metoda
2 zabranen zacyklen porad
zavede se uplne usporadan typu zdroju a kazdy proces pozaduje
prostredky v porad danem vzrustajcm poradm vyctu
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 29
Problem uvaznut na prkladu transakc
2 Uvazme dve transakce:
T1:
write (B);
write (A);
T2:
write (A);
write (B);
2 a plan s uvaznutm:
T1:
lock-X(B);
write (B);
cek an na dokoncen lock-X(A);
T2:
lock-X(A);
write (A);
cek an na dokoncen lock-X(B);
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 30
Prevence uvaznut soubeznych transakc
2 kazda transakce si zamkne vsechna data drve nez se spust
eliminace nutne podmnky uvaznut { hold-and-wait
velmi neefektivn resen,
zvlaste pro distribuovane prostred nepouzitelne
2 nebo se denuje se porad zamykan dat
eliminace postacujc podmnky uvaznut ve wait-for grafu
aplikuje se grafovy protokol rzen soubeznosti
nebo uplne usporadan dat + 2PLP aplikovany na toto porad
2 nebo se pripust preempce transakce,
ktera drz potrebne zdroje
eliminace nutne podmnky uvaznut no preemption
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 31
Prevence uvaznut soubeznych transakc
2 preempce a vracen (roll-back) transakc
jestlize T2 pozaduje zamek, ktery drz T1, muze TPM napr.
{ zamek odbrat T1,
{ T1 vratit (roll-back) a
{ zamek dat do drzby T2
pro rozhodovan o preempci slouz rozhodovac casova raztka transakc
{ tato slouz pouze pro rozhodovan o cekan/vracen transakc
{ data si transakce mus zamykat explicitne pomoc instrukce lock
vracene transakci se rozhodovac casove raztko nemen,
restartuje se s ,,puvodnm"rozhodovacm casovym raztkem,
takze postupne z hlediska rozhodovan starne a
zvysuje si tm prioritu z hlediska prava odebrat zamek
{ inicialn hodnotou rozhodovacho casoveho raztka je cas vzniku T
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 32
Prevence uvaznut na bazi TS
2 predpoklada se moznost predbhan procesu pri pouzit
prostredku (prostredky lze procesum odebrat)
2 TS se prideluje procesu pri prvnm vydan zadosti o zdroj a
pri prpadnem navratu procesu zpet na zacatek se nemen
2 Kazdy proces Pi odvozuje z TS jedinecne prioritn cslo
2 Prioritn csla se pouzvaj pri rozhodovan, zda proces Pi bude
cekat na proces Pj, nebo bude zadat o zdroj znovu, napr.
Pi ceka na Pj ma-li Pi vets prioritu (napr. tm, ze je stars) nez Pj
pokud Pi cekat nebude (ma nizs prioritu, napr. tm, ze je mlads),
bude pak ve svem behu vracen pred zadost a zadost bude opakovat
2 Schema chran pred uvaznutm
Pro kazdou hranu Pi → Pj v grafu cekan (wait-for graph) plat, ze
Pi ma vyss prioritu nez Pj. Cyklus vzniknout nemuze.
navraty ale predstavuj hrozbu starnut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 33
Prevence uvaznut na bazi TS, 2
2 Hroz starnut, procesy nzke priority se mohou stale vracet.
2 Starnut lze resit pomoc rozhodovacch casovych raztek
Wait-Die Scheme, cekej nebo zemri (zemri = delej se znovu)
{ stars T ceka na mlads T dokud tato neuvoln datovou polozku
{ mlads T neceka na stars T, vzdy je vracena (zemre) a
a spoust se znovu, ale se zachovanm veku (mozna i vcekrat,
ale postupne starne a jednou bude nejstars ...)
Wound-Wait Scheme, poran (at' se dela nekdo znovu) nebo cekej
{ stars T neceka na mlads T dokud tato neuvoln datovou polozku,
ran ji (tj. prosad jej vracen, ale se zachovanm veku)
{ mlads T ceka na stars T dokud tato neuvoln datovou polozku
2 schema Wait-Die Scheme muze zpusobovat vce navratu nez
schema Wound-Wait Scheme
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 34
Prevence uvaznut transakc na bazi TS, Wait-Die Scheme
2 Zalozeno na nepreemptivn technice
2 Kdyz se Ti inicialne startuje, zska rozhodovac T Si
2 Necht' pri uplatnen zadosti Ti s T Si o jisty zamek
drz tento zamek Tj s T Sj
je-li zadajc Ti stars nez okamzity vlastnk prostredku, { transakce Tj,
T Si < T Sj, Ti pocka na uvolnen zamku a zska ho po te,
jakmile jej drzitel zamku, tj. transakce Tj, uvoln
je-li zadajc Ti mlads nez okamzity drzitel zamku { Tj, T Si > T Sj,
Ti je vracena, zadost o pridelen opakuje, ale se stejnym T Si
2 Takze plat { jestlize Ti pozaduje zamek drzeny Tj, sm Ti
cekat (wait) jen kdyz T Si < T Sj (Ti je stars nez Tj). Jinak
je Ti vracena v historii zpet na vydan zadosti (dies, zemre).
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 35
Prevence uvaznut transakc na bazi TS, Wait-Die Scheme
2 Wait-Die Scheme zajist'uje, ze transakce muze zemrt vcekrat,
ale ne nekonecne krat, jednou prijde jej cas,
kdy si na uvolnen prostredku urcite pocka,
protoze bude ze vsech transakc nejstars
2 Prklad:
Transakce T1, T2 a T3 maj TS s hodnotami postupne 5, 10, resp. 15.
Jestlize T1 (T S1 = 5) pozaduje zamek drzeny T2 (T S2 = 10),
T1 bude cekat na uvolnen zamku transakc T2
Jestlize T3 (T S3 = 15) pozaduje zamek drzeny transakc T2
(T S2 = 10), pak T3 zemre, tj. bude vracena na zopakovan zadosti o
pridelen zamku, casove raztko se j zachova a tak casem se stava
stars a stars a ma stale vets sanci si na uvolnen zamku pockat.
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 36
Prevence uvaznut transakc na bazi TS, Wound-Wait Scheme
2 Wound-Wait Scheme zajist'uje,
ze stars transakce nikdy neceka na mlads transakci
2 Schema je zalozene na preemptivn technice
je-li zadajc Ti stars nez okamzity vlastnk prostredku { Tj ,
Ti odebere Tj zamek a Tj se v historii vrat, bude zopakovat zadost
o jeho pridelen, se stejnym casovym raztkem (roll-back, undo)
je-li zadajc Ti mlads nez okamzity vlastnk prostredku { Tj,
Ti ceka na uvolnen zamku a zska ho po te
jakmile jej dosavadn drzitel zamku Tj uvoln
2 navratu byva mene, cekan vce
2 obe schemata wait-die i wound-wait restartuj transakce
s puvodnm rozhodovacm TS, coz zabranuje starnut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 37
Prevence uvaznut transakc na bazi TS, Wound-Wait Scheme
Prklad:
2 Transakce T1, T2 a T3 maj TS s hodnotami 5, 10, resp. 15
2 Jestlize T1 (T S1 = 5) pozaduje zamek
drzeny transakc T2 (T S2 = 10),
prebere T1 zamek od T2,
T2 je ,,zranena"transakc T1, je vracena, ...
2 Jestlize T3 (T S3 = 15) pozaduje zamek
drzeny transakc T2 (T S2 = 10),
transakce T3 bude cekat na jeho uvolnen
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 38
Obchazen uvaznut
2 Procesy mohou zadat o zdroje dynamicky
2 Povoluje se existence vsech tr nutnych podmnek,
zabranuje se ale vzniku postacujc podmnky
2 Dynamicky se testuje, zda splnen pozadavku na pridelen
zdroje by v budoucnosti mohlo vest k pozdejsmu uvaznut
2 Pozaduje se tudz znalost budoucho chovan procesu
z hlediska jimi pozadovanych zdroju
2 Pripoust se ale vce soubeznosti nez pri prevenci
2 Dva mozne prstupy k obchazen
proces, jehoz pozadavky by mohly zpusobit uvaznut, nespoustet
nesplnit dynamicky pozadavek procesu na zdroj,
jestlize by splnen pozadavku v budoucnosti mohlo vest k uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 39
Obchazen uvaznut { resen inicialnm rozhodnutm
2 Mus resit middleware (spravce alokac / uvaznut) a plat:
Spravce zna pocty vsech pridelovanych zdroju,
Resource vector, R = (R1, R2, . . . , Rm)
Spravce si vede prehled o poctech dostupnych,
dosud nepridelenych instancch zdroju,
Available vector, V = (V1, V2, . . . , Vm)
Kazdy z n procesu deklaruje maxima svych pozadavku
na jednotlive zdroje v matici Max =
M11 ... M1m
... ... ...
Mn1 ... Mnm
Spravce uvaznut si vede prehled o poctech pridelenych instanc zdroju
kazdemu z n procesu v matici Allocation =
A11 ... A1m
... ... ...
An1 ... Anm
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 40
Obchazen uvaznut { resen inicialnm rozhodnutm
Vsechny zdroje mus byt dostupne nebo pridelene,
Rj = Vj +
n
i=1
Aij pro vsechna j
Zadny proces nemuze pozadovat vce zdroju, nez v systemu existuje
Maxij ≤ Rj, pro vsechna i, j
Zadny proces nemuze zskat vce zdroju nez deklaroval jako maximum
Aij ≤ Maxij, pro vsechna i, j
2 Novy proces Pn+1 se spust pouze kdyz lze uspokojit do vyse
maxim vsechny dosud existujc procesy i Pn+1
Rj ≥
n
i=1
Maxij + Max(n+1)j pro vsechna j
predpoklada se nejhors prpad {
vsechny procesy uplatn maxima pozadavku soucasne
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 41
Obchazen uvaznut { resen dynamickym rozhodovanm
2 tzv. Bankeruv algoritmus (reseny v middleware)
2 Middleware mus mt nejake dodatecne apriorn informace o
pozadavcch procesu na zdroje
2 Model pozaduje, aby kazdy proces udal maxima poctu
prostredku kazdeho typu, ktere muze pozadovat.
2 Algoritmus resc obchazen uvaznut dynamicky zkous,
zda stav systemu pridelovan zdroju zarucuje,
ze se procesy v zadnem prpade nedostanou
do cyklickeho cekan na sebe
2 Stav systemu pridelovan zdroju se denuje
{ poctem dostupnych a pridelenych zdroju a
{ maximy zadost procesu
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 42
Obchazen uvaznut, bezpecny stav
2 Kdyz proces pozaduje pridelen dostupneho prostredku,
algoritmus mus rozhodnout, zda toto pridelen ponecha
system procesu v ,,bezpecnem stavu\, ve kterem plat
Maxij − Aij ≤ Vj, pro vsechna j a i
2 System procesu je v bezpecnem stavu, jestlize existuje
,,bezpecna posloupnost procesu\
2 Posloupnost procesu {P1, P2, . . . , Pn} je bezpecna, jestlize
pozadavky kazdeho Pi lze uspokojit prave volnymi zdroji a
zdroji drzenymi vsemi predchozmi Pj , j < i.
Pokud nejsou zdroje pozadovane procesem Pi dostupne,
pak Pi muze vyckat dokud se vsechny predchoz Pj neukonc.
Pote Pi muze zskat vsechny jm pozadovane zdroje a provest se a
ukoncit se a jemu pridelene zdroje se vrat mezi dostupne zdroje.
Kdyz skonc Pi, muze sve potrebne zdroje zskat Pi+1 atd.
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 43
Obchazen uvaznut, fakta
2 Jestlize je system procesu v bezpecnem stavu (safe state),
do stavu uvaznut (deadlock) neprejde
2 Jestlize se by se system procesu dostal do stavu,
ktery nen bezpecny, (unsafe state),
prechod do stavu uvaznut je hrozbou,
stav uvaznut prpadne muze nastat
2 Obchazen
vykon spravy pridelovan zdroju procesum zajist'ujc,
ze system procesu se trvale nachaz v bezpecnem stavu,
resp. nikdy neprejde do stavu, ktery nen bezpecny
nepovoluje se beh potencialne nebezpecneho procesu
neprovad se potencialne nebezpecne pridelen zdroje
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 44
Ilustrace obchazen pomoc RAG
2 Zdroje mus byt narokovany a priori { narokovymi hranami
2 Narokova hrana Pi → Rj indikuje, ze proces Pi muze nekdy
v budoucnu pozadovat zdroj Rj;
vede stejnym smerem jako pozadavkova hrana
v RAG je zobrazovana carkovane
2 Narokova hrana Pi → Rj se konvertuje na
pozadavkovou hranu v okamziku,
kdy proces Pi pozada o zdroj Rj
vede stejnym smerem jako narokova hrana
v RAG je zobrazovana plnou carou
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 45
Algoritmus RAG pro obchazen
2 Kdyz proces Pi zdroj zska,
pozadavkova hrana se men na hranu pridelen, Pi ← Rj
2 Konverze pozadavkove hrany na hranu pridelen
nesm v RAG vytvorit cyklus
2 Kdyz proces zdroj uvoln,
hrana pridelen se men na narokovou hranu
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 46
Algoritmus RAG pro obchazen
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 47
Bankeruv algoritmus
2 procesy
zakaznci, kter si chtej pujcovat penze (prostredky) z banky,
predem deklaruj maximaln vyse uveru
uvery v konecnem case zakaznci splac
2 banker nemuze uver poskytnout, pokud si nen jisty, ze muze
uspokojit vsechny pozadavky vsech svych zakaznku
alespon v jednom porad uspokojen
2 Algoritmus obchazen uvaznut aplikovatelny i pri nasobnosti
instanc zdroju
2 Kazdy proces mus maxima pouzvanych zdroju deklarovat
apriori, tj. deklarac ihned pri svem vytvoren
2 Proces pozadujc pridelen muze byt dan do stavu cekan
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 48
Bankeruv algoritmus, 2
2 Proces zskane zdroje v konecnem case uvoln
2 Nikdy nedojde k uvaznut
proces vznikne jen tehdy, bude-li mozno uspokojit
vsechny jeho pozadavky (nen dulezite v jakem porad)
pozadavek na pridelen se uspokoj jen tehdy, bude-li mozno uspokojit
vsechny pozadavky vsech procesu (alespon v jednom porad)
2 Jde o sub-optimaln strategii
predpoklada se nejhors prpad, tj.
predpoklada se, ze vsechny procesy si vyzadaj deklarovana maxima
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 49
Datove struktury bankerova algoritmu
2 n { pocet procesu,
2 m { pocet typu zdroju
2 Available {
Vektor delky m
Jestlize plat Available[j] = k ,
pak je dostupnych k instanc typu Rj
2 Max {
matice n × m
Jestlize plat Max[i, j] = k,
(jinak zapsano Maxi[j] = k, vektor maxim procesu i)
pak proces Pi muze pozadovat nejvyse k instanc zdroje typu Rj
vektor maxim Maxi[j] = k, j = 1, . . . , m
je povinnou deklarac v procesu Pi
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 50
Datove struktury bankerova algoritmu, 2
2 Allocation {
matice n × m
Jestlize plat Allocation[i, j] = k,
(jinak zapsano Allocationi[j] = k, vektor pridelen procesu i)
pak proces Pi ma v tomto okamziku
prideleno k instanc zdroje typu Rj
2 Need {
matice n × m
Jestlize plat Need[i, j] = k,
(jinak zapsano Needi[j] = k, vektor moznych pozadavku procesu i)
pak proces Pi muze pro ukoncen sveho ukolu potrebovat
jeste k instanc zdroje typu Rj
Obsah matice Need je denovan jako Max − Allocation
2 Request[i, j] {
(jinak zapsano Requesti[j] = k,
vektor okamzitych pozadavku procesu i)
Jestlize plat Requesti[j] = k,
pak proces Pi pozaduje k instanc zdroje typu Rj.
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 51
Algoritmus testu stavu systemu procesu
1. Necht' W ork a F inish jsou pomocne vektory delek m a n.
Inicializace:
W ork = Available; F inish[i] = false pro i = 1, 2, . . . , n
2. Nalezni i takove, ze plat obe nasledujc podmnky:
(a) F inish[i] = false (b) Need[i] ≤ W ork
Pokud neexistuje, pokracuj krokem 4
3. simulace ukoncen:
W ork = W ork + Allocation[i]; F inish[i] = true
pokracuj krokem 2
4. Pokud plat
F inish[i] = true pro vsechna i,
potom je system ve stavu bezpecny,
v opacnem prpade nen ve stavu bezpecny
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 52
Algoritmus vyzadan zdroje pro proces Pi
1. Pokud plat Request[i, j] ≤ Need[i, j] pokracuj krokem 2.
V opacnem prpade oznam chybu { proces prekrocil
deklarovane maximum
2. Pokud plat Request[i, j] ≤ Available[j], pokracuj krokem 3.
V opacnem prpade Pi mus cekat, nen dostupna instance
zdroje
3. Simuluje se pridelen pozadovaneho zdroje Pi zmenou stavu:
Available[j] = Available[j] − Request[i, j];
Allocation[i, j] = Allocation[i, j] + Request[i, j];
Need[i, j] = Need[i, j] − Request[i, j];
Provede se test stavu systemu.
Pokud je stav bezpecny, pak se pozadovane zdroje procesu
Pi pridel, pokud nen stav bezpecny, pak Pi mus cekat a
zachova se puvodn stav pridelen zdroju
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 53
Prklad 1 bankerova algoritmu
2 pet procesu P0 az P4
2 tri typy zdroju {
A (10 instanc), B (5 instanc) a C (7 instanc)
2 Momentka stavu v case t :
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
A B C
3 3 2
2 System je v bezpecnem stavu, ponevadz napr. posloupnost
P1, P3, P4, P2, P0 splnuje kriteria bezpecnosti
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 54
Prklad 1 bankerova algoritmu
2 ukoncil se P1
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
A B C
5 3 2
2 ukoncil se P3
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P2 3 0 2 9 0 2 6 0 0
P4 0 0 2 4 3 3 4 3 1
A B C
7 4 3
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 55
Prklad 1 bankerova algoritmu
2 ukoncil se P4
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P2 3 0 2 9 0 2 6 0 0
A B C
7 4 5
2 ukoncil se P2
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
A B C
10 47
2 ukoncil se P0 { stav je bezpecny
Allocation Max Need Available
A B C A B C A B C A B C
10 57
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 56
Prklad 1 bankerova algoritmu
2 Necht' P1 v case t pozaduje (1, 0, 2)
2 kontrola Request1 ≤ Need1, (1, 0, 2) ≤ (1, 2, 2) je true.
2 kontrola Request1 ≤ Available, (1, 0, 2) ≤ (3, 3, 2) je true.
2 proveden kontroly stavu ukaze, ze podmnku bezpecnosti
splnuje posloupnost procesu P1, P3, P4, P0, P2:
Momentka stavu v case t :
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
A B C
3 3 2
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 57
Prklad 1 bankerova algoritmu
2 Simulovane pridelen procesu P1 v case t :
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P1 3 0 2 3 2 2 0 2 0
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
A B C
2 3 0
2 ukoncil se P1 :
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
A B C
5 3 2
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 58
Prklad 1 bankerova algoritmu
2 ukoncil se P3 :
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P2 3 0 2 9 0 2 6 0 0
P4 0 0 2 4 3 3 4 3 1
A B C
7 4 3
2 ukoncil se P4 :
Allocation Max Need Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P2 3 0 2 9 0 2 6 0 0
A B C
7 4 5
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 59
Prklad 1 bankerova algoritmu
2 ukoncil se P0 :
Allocation Max Need Available
A B C A B C A B C
P2 3 0 2 9 0 2 6 0 0
A B C
7 5 5
2 ukoncil se P2 { stav je bezpecny:
Allocation Max Need Available
A B C A B C A B C A B C
10 5 7
2 pozadavek P1 na pridelen (1, 0, 2) se uspokoj
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 60
Prklad 2 bankerova algoritmu, bezpecny stav
2 Inicialn stav proverovany zda je bezpecnym stavem
2 Ukoncit se muze proces P2
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 61
Prklad 2 bankerova algoritmu, bezpecny stav
2 Ukoncil se proces P2
2 Ukoncit se muze kterykoliv proces z P1, P2 a P3
2 Ukonc se napr. proces P1
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 62
Prklad 2 bankerova algoritmu, bezpecny stav
2 Ukoncil se proces P1
2 Ukoncit se muze kterykoliv proces z P2 a P3
2 Ukonc se napr. proces P3
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 63
Prklad 2 bankerova algoritmu, bezpecny stav
2 Ukoncil se proces P3
2 Ukoncit se muze proces P4
2 Inicialn stav byl bezpecny, ukoncit se mohly vsechny procesy
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 64
Prklad 3 bankerova algoritmu
2 Inicialn stav
Kdyby nyn proces P2 pozadal o zdroj R1 a R3,
vysledkem je inicialn stav prkladu 2 a ten je bezpecny
Kdyby nyn proces P1 pozadal o zdroj R1 a R3,
pak vysledny stav je na nasledujcm obrazku
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 65
Prklad 3 bankerova algoritmu
2 Tento stav bezpecny nen,
kazdy proces muze pozadat o R1 a ten dostupny nen
2 Zadost procesu P1 z predchozho obrazku se mus zamtnout
mohlo by nastat uvaznut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 66
Prklad 4 bankerova algoritmu
2 Pozadovana alokace 100 pro P2 se odmtne
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 67
Bankeruv algoritmus { poznamky
2 behy procesu z bezpecneho stav nezpusob uvaznut
2 behy procesu ze stavu, ktery nen bezpecny, jeste nemus
zpusobit uvaznut
2 vsechny algoritmy obchazen uvaznut predpokladaj,
ze procesy jsou nezavisle, ze se synchronizacne neomezuj
2 obchazen uvaznut zamez uvaznut,
nemus ale zamezit starnut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 68
Detekce uvaznut
2 umoznuje se, aby se system uvaznul
2 provede se algoritmus detekce uvaznut { hledan cyklu
2 aplikuje se plan obnovy
Nasilne se ukoncuje jednotlive proces po procesu,
dokud se neodstran cyklus
2 Cm je dano porad nasilneho ukoncen?
priorita procesu
doba behu procesu, doba potrebna k ukoncen procesu
prostredky, ktere proces pouzil
prostredky, ktere proces potrebuje k ukoncen
pocet procesu, ktere bude potreba ukoncit
Je proces interaktivn nebo davkovy?
...
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 69
Detekce uvaznut
2 Algoritmus detekce pro prpad 1 instance prostredku kazdeho
typu
Udrzuje se graf cekan, uzly jsou procesy,
Pi → Pj jestlize Pi ceka na Pj
Periodicky se provad algoritmus,
ktery v grafu cekan hleda cykly
Algoritmus pro detekci cyklu v grafu pozaduje proveden n2
operac,
kde n je pocet hran v grafu
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 70
Graf pridelen zdroju, RAG a graf cekan
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 71
Prpad m instanc prostredku kazdeho typu
2 Available
Vektor delky m
indikuje pocet dostupnych instanc prostredku kazdeho typu
2 Allocation
Matice n × m
indikuje pocet instanc prostredku kazdeho typu
pridelenych kazdemu procesu
2 Request
Matice n × m
indikuje okamzite pozadavky kazdeho procesu
Jestlize plat Request[i, j] = k,
pak proces Pi pozaduje k dalsch instanc typu Rj.
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 72
Algoritmus detekce
1. Necht' W ork a F inish jsou pracovn vektory delek m a n.
Inicializace:
{ W ork = Available
{ pro i = 1, 2, . . . , n: je-li Allocation[i] = 0,
pak F inish[i] = false, jinak F inish[i] = true
2. Nalezni takove i ,ze :
(a) F inish[i] = false
(b) Request[i] ≤ W ork
jestlize takove i neexistuje, krok 4.
3. W ork = W ork + Allocation[i]; F inish[i] = true
pokracuj krokem 2.
4. Jestlize pro nejake i, 1 ≤ i ≤ n plat F inish[i] = false,
pak v sytemu ex. uvaznut. Uvazly Pi s F inish[i] = false
Algoritmus pozaduje pro detekci uvaznut O(mn2
) operac.
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 73
Prklad 1 detekce uvaznut
2 pet procesu P0 az P4,
2 tri typy zdroju { A (7 instanc), B (2 instanc) a C (6 instanc)
2 Momentka stavu v T0 :
Allocation Request Available
A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
2 V systemu procesu neexistuje uvaznut, posloupnost
P0, P2, P3, P1, P4 konc s F inish[i] = true pro vsechna i.
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 74
Prklad 1 detekce uvaznut, 2
2 P2 pozaduje dals exemplar zdroje typu C :
Allocation Request Available
A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 1
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
2 Jaky je stav systemu?
I kdyz se uvoln zdroje drzene procesem P0,
pozadavky procesu P1, P2, P3, a P4 se neuspokoj
System uvazl, uvaznut se tyka procesu P1, P2, P3, a P4
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 75
Prklad 2 detekce uvaznut
2 Jaky je stav systemu?
Dostupny je pouze jeden zdroj R5
Vsechny procesy pozaduj vce zdroju nez jeden R5
System uvazl, uvaznut se tyka vsech procesu P1, P2, P3, a P4
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 76
Pouzitelnost algoritmu detekce
2 Kdy, jak casto algoritmus detekce uvaznut vyvolavat?
zdroje drzene uvaznutymi procesy jsou nedostupne do zrusen uvaznut
2 Vzdy, kdyz nelze uspokojit pozadavek na pridelen
detekuje se proces zpusobujc uvaznut a uvazle procesy
jeden proces muze zpusobit vce cyklu v RAG
zvysuje se systemova rezie uvaznut
2 Algoritmus detekce uvaznut se vyvolava nahodne/cyklicky
v grafu cekan muze existovat vce cyklu a nelze urcit,
ktery z mnoha procesu uvaznut ,,zpusobil\
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 77
Obnova po detekci { ukoncen procesu
a. Nasilne ukoncen vsech uvazlych procesu
b. Nasilne se ukoncuje jednotlive proces po procesu,
dokud se neodstran cyklus
2 Cm je dano porad nasilneho ukoncovan?
2 heuristiky:
priorita procesu
doba behu procesu, doba potrebna k ukoncen procesu
prostredky, ktere proces pouzil
prostredky, ktere proces potrebuje k ukoncen
pocet procesu, ktere bude potreba ukoncit
Je proces interaktivn nebo davkovy?
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 78
Obnova po detekci { prerozdelen prostredku
Problemy:
2 Vyber obeti { minimalizace ceny { co je cenou ???
2 Navrat zpet (Rollback) { navrat procesu do nektereho
bezpecneho stavu, restart procesu z tohoto stavu
(checkpoints)
2 Starnut { nektery proces muze byt vybran jako obet' trvale, i
kdyz se bude do cenoveho kriteria poctat pocet navratu
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 79
Kombinovana ochrana pred uvaznutm
2 Kombinuj se tri zakladn prstupy
prevence
obchazen
detekce a obnova
2 optimalizovany prstup k ochrane pro kazdy typ zdroje
2 delen zdroju do hierarchickych trd
pouzije se prevence cyklickeho cekan na sebe mezi trdami prostredku
2 pouzit nejvhodnejs techniky pro zvladan uvaznut v kazde
trde
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 80
Kombinovana ochrana pred uvaznutm, prklad
2 Kategorie zdroju z hlediska porad pridelovan
oblast na disku pro odkladan procesu
zdroje procesu { periferie typu disky, pasky, soubory
oblast hlavn / operacn pamet'
I/O kanaly
2 oblast na disku pro odkladan procesu
prevence pridelenm prostoru pri zahajen
lze uplatnit i obchazen
2 zdroje procesu { periferie typu disky, pasky, soubory
lze uplatnit obchazen
lze pouzt prevenci stanovenm porad pozadavku
2 oblast hlavn / operacn pamet'
prevence odebranm zdroje (preempce)
2 I/O kanaly
prevence stanovenm porad pozadavku
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 81
Problem uvaznut transakc, ochrana casovymi limity
2 casovy limit, time-out
2 transakce cekajc na zamek se po uplynut casoveho limitu
vrac a restartuje
2 pokud byly nektere transakce uvazle, navraty se uvaznut rus
2 snadna implementace
2 obtzny odhad delky cekan
2 moznost starnut
2 vhodne pro prostred s kratkymi transakcemi a
s pravdepodobnym dlouhym cekanm pri uvaznut
2 velmi omezena pouzitelnost
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 82
Problem uvaznut transakc, detekce uvaznut a obnova
2 analogicke resen jako v prpade procesu
udrzuje se wait-for-graph
{ uzly { transakce
{ orientovane hrany { ktera transakce ceka na kterou transakci
ve vhodnych intervalech se res detekce cyklu ve WfG
co jsou to ,,vhodne intervaly"?
{ volbu ovlivnuje jak casto dochaz k uvaznut
{ volbu ovlivnuje kolik transakc muze byt ovlivneno uvaznutm ?
je nutne resit problem vyberu obeti pro vracen
{ vsechny ?
{ jen nektere az do zrusen cyklu ve WfG ? (Problem ocenen.)
{ problem starnut
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 83
Ignorovan uvaznut
2 ,,pstros"politika
Matematici { najdou si totalne neuskutecnitelne uvaznut a rkaj,
ze se mu mus za kazdou cenu zabranit prevenc
Inzenyri { otaz se na zavaznost a odmtnou zbytecne plytvat energi
na resen nepodstatneho problemu:
{ Resen v univerzalnch operacnch systemech (Unixovy prstup):
{ uzivatele preferuj moznost rdkeho vyskytu uvaznut
pred omezenm, ze by jejich procesy dynamicky zadajc zdroje
byly reseny totaln serializac
{ Pokud resen v univerzalnch operacnch systemech nevyhovuje,
mus system aplikacnch procesu resit uvaznut v middleware
Jan Staudek, FI MU Brno | PB152 Operacn syst emy { Uv aznut 84