Uv aznut
PA150 Principy operacnch systemu
Jan Staudek
http://www..muni.cz/usr/staudek/vyuka/
Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý
Verze: podzim 2020
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 | PA 150 Principy operacnch syst em u { 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 | PA 150 Principy operacnch syst em u { 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 | PA 150 Principy operacnch syst em u { Uv aznut 3
Problem uvaznut { souperen o zdroj
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { 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 | PA 150 Principy operacnch syst em u { 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, objekt, ...
predchoz prklady pouzvaj opakovane pouzitelne zdroje
2 Zdroje spotrebovavane, consumable
vznikaj generovanm a zanikaj zprstupnenm
prerusen, signaly, zpravy, ...
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 6
Dva procesy souper o opakovane prstupny zdroj
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 7
Dva procesy souper o opakovane prstupny zdroj
2 K uvaznut nedojde
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 8
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 | PA 150 Principy operacnch syst em u { Uv aznut 9
Prklad uvaznut pri pouzit spotrebovavaneho zdroje
2 prklad uvaznut pri vymene zprav cekanm na udalost zskan
zpravy
operace receive je synchronn, konc prijetm zpravy
P0: P1:
... receive(P0, q);
... ...
receive(P1, m); ...
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 10
Obecne platna denice uvaznut a starnut
2 zskan prstupu k opakovane prstupnemu zdroji, zskan
spotrebovavaneho zdroje { udalost
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 / zdroj { 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 | PA 150 Principy operacnch syst em u { Uv aznut 11
Postupovy prostor 2 procesu bez moznosti uvaznut
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 12
Postupovy prostor 2 procesu s moznost uvaznut
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 13
Postupovy prostor 2 procesu bez moznost uvaznut
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 14
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 | PA 150 Principy operacnch syst em u { Uv aznut 15
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 (instance) zdroje, Request (Get)
pouzit (instance) zdroje (po konecnou dobu)
uvolnen (instance) zdroje, Release
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 16
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 | PA 150 Principy operacnch syst em u { Uv aznut 17
Graf pridelen zdroju, RAG
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 18
Prklad RAG { cyklicke retezen
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 19
Prklady RAG
bez uvaznut s uvaznutm
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 20
Prklad RAG { s cyklem a bez uvaznut
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 21
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 | PA 150 Principy operacnch syst em u { Uv aznut 22
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 | PA 150 Principy operacnch syst em u { Uv aznut 23
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, resp, WFG
a obnova stavu bez uvaznut
2 Ignorovan hrozby uvaznut
resen uplatnene v univerzalnch OS { Unix, Windows, ..
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 24
Metody zvladnut uvaznut
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 25
Metody zvladnut uvaznut
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 26
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 | PA 150 Principy operacnch syst em u { Uv aznut 27
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 | PA 150 Principy operacnch syst em u { Uv aznut 28
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 | PA 150 Principy operacnch syst em u { Uv aznut 29
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 | PA 150 Principy operacnch syst em u { Uv aznut 30
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 | PA 150 Principy operacnch syst em u { Uv aznut 31
Obchazen uvaznut
2 Procesy mohou zadat o zdroje dynamicky, alokaci mus resit
middleware (spravce alokac / uvaznut)
2 Povoluje se existence vsech tr nutnych podmnek,
zabranuje se ale vzniku postacujc podmnky
2 Spravce dynamicky testuje, zda splnen pozadavku na
pridelen zdroje by v budoucnosti mohlo vest k uvaznut
Spravce mus znat mozne pocty pozadovanych zdroju procesy
Nebezpecne pozadavky spravce odmta, hroz starnut
Pripoust se ale vce soubeznosti nez pri prevenci
2 Dva mozne prstupy k obchazen
proces, jehoz pozadavky by mohly zpusobit uvaznut, nespoustet
nesplnit az dynamicky zadany pozadavek procesu na zdroj,
jestlize by splnen pozadavku v budoucnosti mohlo vest k uvaznut
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 32
Obchazen uvaznut { resen inicialnm rozhodnutm
Spravce zna pocty vsech pridelovanych zdroju,
Resource vector, R = (R1, R2, . . . , Rm)
Kazdy z n procesu deklaruje maxima svych pozadavku
na jednotlive zdroje v matici Max =
M11 ... M1m
... ... ...
Mn1 ... Mnm
Spusteny proces postupne zada o pridelen zdroju.
Zadny proces nemuze pozadovat vce zdroju, nez v systemu existuje
Maxij ≤ Rj, pro vsechna i, j
Spravce uvaznut si vede prehled o poctech pridelenych instanc zdroju
kazdemu z n procesu v matici Allocation =
A11 ... A1m
... ... ...
An1 ... Anm
Zadny proces nemuze zskat vce zdroju nez deklaroval jako maximum
Aij ≤ Maxij, pro vsechna i, j
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 33
Obchazen uvaznut { resen inicialnm rozhodnutm
Spravce si vede prehled o poctech dostupnych,
dosud nepridelenych instancch zdroju,
Available vector, V = (V1, V2, . . . , Vm)
Vsechny zdroje mus byt dostupne nebo pridelene,
Rj = Vj +
n
i=1
Aij pro vsechna j
2 Novy proces Pn+1 se spust pouze kdyz lze uspokojit do vyse
maxim vsechny dosud existujc procesy a proces 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 | PA 150 Principy operacnch syst em u { Uv aznut 34
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 zdroju a pridelenych zdroju a
{ maximy pozadavku jednotlivych procesu
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 35
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 vycka dokud se nektery predchoz Pj neukonc,
a 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 | PA 150 Principy operacnch syst em u { Uv aznut 36
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 | PA 150 Principy operacnch syst em u { Uv aznut 37
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 | PA 150 Principy operacnch syst em u { Uv aznut 38
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 | PA 150 Principy operacnch syst em u { Uv aznut 39
Algoritmus RAG pro obchazen
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 40
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 | PA 150 Principy operacnch syst em u { Uv aznut 41
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 | PA 150 Principy operacnch syst em u { Uv aznut 42
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 | PA 150 Principy operacnch syst em u { Uv aznut 43
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 | PA 150 Principy operacnch syst em u { Uv aznut 44
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 | PA 150 Principy operacnch syst em u { Uv aznut 45
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 | PA 150 Principy operacnch syst em u { Uv aznut 46
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 | PA 150 Principy operacnch syst em u { Uv aznut 47
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 | PA 150 Principy operacnch syst em u { Uv aznut 48
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 | PA 150 Principy operacnch syst em u { Uv aznut 49
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 | PA 150 Principy operacnch syst em u { Uv aznut 50
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 | PA 150 Principy operacnch syst em u { Uv aznut 51
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 | PA 150 Principy operacnch syst em u { Uv aznut 52
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 | PA 150 Principy operacnch syst em u { Uv aznut 53
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 | PA 150 Principy operacnch syst em u { Uv aznut 54
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 | PA 150 Principy operacnch syst em u { Uv aznut 55
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 | PA 150 Principy operacnch syst em u { Uv aznut 56
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 | PA 150 Principy operacnch syst em u { Uv aznut 57
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 | PA 150 Principy operacnch syst em u { Uv aznut 58
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 | PA 150 Principy operacnch syst em u { Uv aznut 59
Prklad 4 bankerova algoritmu
2 Pozadovana alokace 100 pro P2 se odmtne
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 60
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 | PA 150 Principy operacnch syst em u { Uv aznut 61
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 v grafu vzajemneho cekan procesu
2 Cm je dano porad nasilneho ukoncen?
priorita procesu
doba behu procesu, doba potrebna k ukoncen procesu, pokud se zna
prostredky, ktere proces drz
prostredky, ktere proces potrebuje k ukoncen
pocet procesu, ktere bude potreba ukoncit
Je proces interaktivn nebo davkovy?
...
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 62
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 | PA 150 Principy operacnch syst em u { Uv aznut 63
Graf pridelen zdroju (RAG) a graf cekan (WFG)
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 64
Prpad vce instanc zdroje kazdeho typu
2 Available
Vektor delky m
indikuje pocet dostupnych instanc zdroju kazdeho typu
2 Allocation
Matice n × m
indikuje pocet instanc zdroju kazdeho typu z m typu
pridelenych kazdemu z n procesu
2 Request
Matice n × m
indikuje okamzite pozadavky na zdroje kazdeho z n procesu
na kazdy z m typu zdroju
Jestlize plat Request[i, j] = k,
pak proces Pi pozaduje k dalsch instanc zdroje typu Rj.
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 65
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 | PA 150 Principy operacnch syst em u { Uv aznut 66
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 | PA 150 Principy operacnch syst em u { Uv aznut 67
Prklad 1 detekce uvaznut
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
Po ukoncen P0 je Available = 0, 1, 0
Po ukoncen P2 je Available = 3, 1, 3
Po ukoncen P3 je Available = 5, 2, 4
Po ukoncen P1 je Available = 7, 2, 4
Po ukoncen P4 je Available = 7, 2, 6
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 68
Prklad 1 detekce uvaznut, 2
2 Nyn necht' 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 P2, P3, P1 a P4 se neuspokoj
System uvazl, uvaznut se tyka procesu P1, P2, P3, a P4
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 69
Prklad 2 detekce uvaznut
2 Jaky je stav systemu?
Uspokojit lze pozadavek pouze P3 na R5 a P3 pote uvoln R4 a R5
P1 pozaduje R5 a nedostupny R2
P2 pozaduje R5 a nedostupny R3
P4 pozaduje R5 a nedostupne R1 a R3
Uvaznut se tyka procesu P1, P2 a P4
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 70
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 | PA 150 Principy operacnch syst em u { Uv aznut 71
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, pokud se zna
prostredky, ktere proces drz
prostredky, ktere proces potrebuje k ukoncen
pocet procesu, ktere bude potreba ukoncit
Je proces interaktivn nebo davkovy?
Jan Staudek, FI MU Brno | PA 150 Principy operacnch syst em u { Uv aznut 72
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 | PA 150 Principy operacnch syst em u { Uv aznut 73
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 | PA 150 Principy operacnch syst em u { Uv aznut 74
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 | PA 150 Principy operacnch syst em u { Uv aznut 75
Ignorovan uvaznut
2 ,,pstros"politika
Matematici { najdou si prakticky 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 | PA 150 Principy operacnch syst em u { Uv aznut 76