Detekce uváznutí v DS
PA150 o Principy operačních systémů
Jan Staudek http://www.fi.muni.cz/usr/staudek/vyuka/
Verze: podzim 2020
Wait-for-Graph (mezi procesy běžícími v uzlech DS)
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 1
Příklad uváznutí v DS
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 2
Poznámky k výkladu uváznutí
□ Procesy v DS mohou žádat o zdroje v libovolném pořadí
J Pořadí není známé a priori
□ Procesy mohou žádat o zdroje i když již mají přidělené jiné
zdroje
□ Předpoklady
/ zdroje jsou opakovaně přístupné
/ procesy požadují exkluzivní přístup ke zdroji
J zdroje jsou v jediných exemplářích
□ Stavy procesů
/ aktivní - má přidělené zdroje, které požadoval a je buď běžící nebo připravený k běhu
J blokovaný - čeká na přidělení zdroje
Jan Staudek, FI MU Brno I PA150 - Detekce uváznutí v DS 3
Principy řešeni uváznuti
□ Razením použitelnosti zdrojů - prevence uváznutí
/ definuje se globální uspořádání všech systémových zdrojů
J každý zdroj obdrží jedinečné pořadové číslo
/ proces smí požadovat zdroj s číslem i
pouze když nevlastní zdroj s číslem větším než i
J snadná implementovatelnost, možná neefektivita používání zdrojů
□ Bankéřův algoritmus - obcházení uváznutí
J jeden z procesů musí hrát roli bankéře - správce prostředků
J v distribuovaném prostředí nesnadno implementovatelný, větší režie
□ Detekce uváznutí
J zkoumání stavu interakcí mezi procesy a zdroji, vyhledávání cyklického čekání
J efektivní přístup ke zvládání uváznutí v distribuovaném prostředí
Jan Staudek, FI MU Brno I PA150 - Detekce uváznutí v DS 4
Modely uváznutí
□ Jednoduchý model
/ Proces může požadovat přidělení pouze jednoho zdroje / Proces být pouze v jednom cyklu
/ Cyklus ve WFG je postačující podmínkou pro detekci uváznutí
□ AND model
/ Proces může požadovat současné přidělení více zdrojů
J Požadavek přidělení je splněný přidělením všech zdrojů současně
/ Z uzlu WFG může vystupovat více hran
/ Cyklus ve WFG je postačující podmínkou pro detekci uváznutí J AND model je obecnější model než jednoduchý model
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 5
AND model
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 6
Modely uváznutí
□ OR Model
/ Proces může najednou požadovat více zdrojů
J Proces zůstává blokován dokud neobdrží alespoň jeden z požadovaných zdrojů
/ Cyklus ve WFG je nutnou podmínkou pro uváznutí
/ Uzel (knot) v grafu je postačující podmínkou pro detekci uváznutí
J Knot (uzel): podmnožina orientovaného grafu taková, že počínajíc z libovolného uzlu podmnožiny nelze opustit knot po hranách grafu.
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 7
OR model
site 4
Pokud jsou všechny procesy OK procesy,
pak Pil není uváznutý,
poněvadž až se ukončí P33,
ukončí se i P32
a lze splnit požadavek Pil
V OR modelu indikuje existenci uváznutí uzel (knot) a ten se zde nevyskytuje
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 8
Cyklus vs. uzel
Je zde cyklus nikoli uzel (knot)
Jsou zde cykly i uzel (knot)
Uváznutí v AND modelu, bez uváznutí v OR modelu
Uváznutí v AND mdelu i v OR modelu
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 9
Modely uváznutí
□ AND-OR model
J Kombinace požadavků na AND model a OR modelu
/ Např. přiděl (y and (x or z)
S Existence uváznutí se testuje opakovaným testem uváznutí v OR modelu
□ P-out-of-Q model, generalizovaný model
J Získání P z Q zdrojů
/ Např. prístup k replikám (stačí prístup k P replikám z Q replik) / Speciální prípady
- P = 1 ... OR model
- P = Q ... AND model
/ Uzel (knot) v grafu je postačující podmínkou pro detekci uváznutí
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 10
Správa uváznutí pomocí detekce
□ Spravá prevencí a obcházením je v DS neefektivní /
nepraktické řešení
□ Správa detekcí je vhodná pro DS
/ Uváznutí se musí
a) odhalit (detekovat) a
b) poté vyřešit
J Pro odhalení uváznutí musíme umět
a) udržovat WFG a
b) hledat ve WFG cykly (uzly)
J pro vyřešení se musí definovat aplikačně orientovaná politika
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 11
Detekce uváznutí, kritéria správnosti detekčního algoritmu
□ Živost, progress, nezůstne žádné nedetekované uváznutí
J všechna existující uváznutí musí algoritmus detekovat v konečném čase
/ jakmile se uváznutí vyskytne, spuštěný algoritmus
nesmí čekat na žádnou další událost aby uváznutí detekoval
□ Bezpečnost, safety, nedetekují se falešná uváznutí
J algoritmus nesmí oznamovat neexistující, falešná uváznutí
J tj. uváznutí detekované na základě konstrukce nekonzistentního WFG vytvořeného díky asynchronní komunikaci a neexist. společné paměti
□ Řešení detekovaného uváznutí
/ jeden nebo více z uvázlých procesů se zruší (vrátí na počátek) a jejich zdroje se přidělí blokovaným procesů, které pak mohou dále běžet
Jan Staudek, FI MU Brno I PA150 - Detekce uváznutí v DS 12
Metody detekce uváznutí
□ Centralizované řízení
J řídicí uzel v DS vytváří WFG a hledá v něm orientované cykly / WFG lze udržovat průběžně nebo budovat na žádost J řídicí uzel v DS řeší detekované uváznutí / negativa:
možnost výpadku centra, zahlcení centra, detekce falešných uváznutí
□ Distribuované řízení
J WFG je rozprostřen po částech v různých uzlech DS
J Kterýkoliv uzel DS může iniciovat proces detekce uváznutí
□ Hierarchické řízení
/ uzly DS jsou uspořádány do hierarchie (strom)
J uzly DS kontroluje cykly pouze u podřízených uzlů DS
\ Jan Staudek, FI MU Brno I PA150 - Detekce uváznutí v DS    13 )
Falešné cykly
Původní stav zobrazený ve wait-for grafu v koordinátorovi
cas
	P3 uvolní RA
	P3 požádá o RB
falešné uváznutí
Stav postupně zobrazovaný ve wait-for grafu v koordinátorovi když zpráva o uvolnění dojde dříve než zpráva o přidělení
Stav zobrazený ve wait-for grafu v koordinátorovi když zpráva o přidělení dojde dříve než zpráva o uvolnění
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 14
Falešné cykly
s1a1us;T2 waitlng lorTI       status :T1 waiting 1orT2
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 15
Centralizovaný Ho-Ramamoorthy 2-fázový algoritmus
□ pro AND i OR model
□ každý uzel DS si udržuje stavovou tabulku o lokálních
procesech
(který proces na koho čeká, tj. de facto lokální WFG)
□ řídicí uzel DS se periodicky dotazuje na obsah těchto tabulek
ve všech uzlech
□ řídicí uzel DS vytváří globální WFG, analyzuje jej, hledá v něm
cykly a pokud je najde, pak hledá řešení uváznutí
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 16
Centralizovaný Ho-Ramamoorthy 2-fázový algoritmus
□ nutnou podmínkou pro detekci uváznutí je nalezení cyklu,
pokud řídicí uzel DS najde cyklus v globálním WFG, požádá znovu o zaslání tabulek z participujících uzlů DS
□ pokud je opět detekován cyklus,
může se jednat o uváznutí
□ může se ale jednat i o falešný cyklus,
zdánlivé (phantom) uváznutí
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 17
Detekce uváznutí pomocí Mwait-f or "grafů, WFG
□ Předpoklad a důsledek
J každý alokovatelný zdroj ex. v jediném exempláři / cyklus ve Mwait-for"grafu reprezentuje uváznutí
□ Lokální Mwait-for"graf, platný pro odpovídající uzel sítě
J uzly v lok. WFG odpovídají jako lokálním tak i nelokálním procesům, pokud tyto procesy drží nebo požadují zdroje lokální v daném uzlu sítě
□ Globální Mwait-for"graf, platný pro celou síť
J sjednocení lokálních lokálních Mwait-for" grafů
□ Cyklus v lokálním „wait-for"grafu => existuje uváznutí
□ Acykličnost lokálního „wait-for" grafu
ještě neznamená neexistenci uváznutí
J existenci uváznutí indikuje až globální „wait-for"graf
Jan Staudek, FI MU Brno I PA150 - Detekce uváznutí v DS 18
Detekce uváznutí pomocí M wait-for "grafů, WFG
site S,    Lokální wait-for grafy    site S2
Pl běžící v SI má přidělený zdroj v SI P3 běžící v SI má přidělený zdroj v SI P5 běžící v SI čeká na uvolnění zdroje v SI drženého Pl
P2 běžící v S2 má přidělený zdroj v S2 a
čeká na uvolnění zdrojů v SI držených Pl a P3 P4 běžící v S2 má přidělený zdroj v S2
Lokální wait-for grafy neobsahují cyklus
Jestliže Pí bělící v s2 žádá zdroj držený pó běžícím v Si, pošle p{ zprávu do 5i a v lok. grafu v Si se zapíše hrana Pí^Pj
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 19
Detekce uváznutí pomocí M wait-for" grafů, WFG
site S,    Lokální wait-for grafy    site S2
Pl běžící v SI má přidělený zdroj v SI P3 běžící v SI má přidělený zdroj v SI a
čeká na uvolnění zdroje v S2 drženého P4
P5 běžící v SI čeká na uvolnění zdroje v SI drženého Pl
P2 běžící v S2 má přidělený zdroj v S2 a
čeká na uvolnění zdrojů v SI držených Pl a P3 P4 běžící v S2 má přidělený zdroj v S2
Lokální wait-for grafy neobsahují cyklus
Jestliže Pí bělící v s2 žádá zdroj držený pó běžícím v Si, pošle p{ zprávu do 5i a v lok. grafu v Si se zapíše hrana Pí^Pj
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 20
Detekce uváznutí pomocí M wait-for "grafů, WFG
site S|    Lokální wait-for grafy    site S2
Pl běžící v SI má přidělený zdroj v SI P3 běžící v SI má přidělený zdroj v SI a
čeká na uvolnění zdroje v S2 drženého P4 P5 běžící v SI čeká na uvolnění zdroje v SI drženého Pl P2 běžící v S2 má přidělený zdroj v S2 a
čeká na uvolnění zdrojů v SI držených Pl a P3 P4 běžící v S2 má přidělený zdroj v S2 a
čeká na uvolnění zdroje v S2 drženého P2
Lokální wait-for grafy neobsahují cyklus
Jestliže Pi běžící v s2 žádá zdroj držený pó běžícím v Si, pošle p{ zprávu do 5i a v lok. grafu v Si se zapíše hrana Pí^Pj
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 21
Detekce uváznutí pomocí wait-for"grafů, WFG
□ Centrální uzel si vyžádá stav jednotlivých uzlů:
/ Globální wait-for graf
Globální wait-for graf obsahuje cyklus, systém je v uváznutí: p2 čeká na p3, p3 čeká na p4, p4 čeká na p2
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 22
Distribuované algoritmy
□ Každý uzel má stejné možnosti detekovat uváznutí
/ WFG je abstrakcí, kde každý uzel obsahuje svou část WFG
/ Obecně je detekce vyvolána stranou,
kde nějaké vlákno čeká príliš dlouho ve frontě na zdroj
□ 4 modely
/ Path-pushing: informace o cestě v grafu (vztah čekajícího procesu a přiděleného zdroje) je posílána z čekajícího uzlu do blokujícího uzlu (Obermarck), pro AND model
/ Edge-chasing: hranami WFG jsou posílány speciální zprávy
(probe - sondy). Jestliže je sondovací zpráva přijata iniciátorem, je detekováno uváznutí (Chandy-Misra-Haas), pro AND model
/ Global state detection: získává se snímek (snapshot) o distribuovaném systému, konstruuje se a redukuje se WFG
/ Diffusion computation: WFG jsou posílány echo zprávy, obsahující dotaz na stav jednotlivých uzlů
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 23
Path-pushing, Obermarck
□ Za detekci uváznutí sdílejí odpovědnost všechny uzly DS.
□ V každém uzlu DS se konstruuje lokální wait-for graf,
který reprezentuje část globálního wait-for grafu
□ Do každého lokálního wait-for grafu se přidává
dodatečný uzel pex
S Hrana p{    pex reprezentuje stav, ve kterém Pí čeká na zdroj držený procesem ve kterémkoliv jiném uzlu sítě
/ Hrana pex    p{ reprezentuje stav,
ve kterém proces ve kterémkoliv jiném uzlu sítě čeká na zdroj držený procesem p{ v lokálním uzlu
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 24
Path-pushing, Obermarck
□ Jestliže lokální wait-for grafu obsahuje cyklus,
který neobsahuje uzel pex,
pak procesy v tomto uzlu jsou ve stavu uváznutí
□ Cyklus obsahující uzel pex implikuje možnost uváznutí.
Pro zjištění, zda procesy v DS uvázly či ne,
se musí spustit distribuovaný algoritmus detekce uváznutí
□ algoritmus může detekovat i falešná uváznutí protože snímek
zjišťuje asynchronně
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 25
Path-pushing, Obermarck
Pl běžící v SI má přidělený zdroj v SI
P3 běžící v SI má přidělený zdroj v SI
P5 běžící v SI ceká na uvolnění zdroje v SI drženého Pl
P2 běžící v S2 má přidělený zdroj v S2 a
ceká na uvolnění zdrojů v SI držených Pl a P3 P4 běžící v S2 má přidělený zdroj v S2 a
čeká na uvolnění zdroje v S2 drženého P2
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 26
Path-pushing, Obermarck
ťto £t site s3
Pl běžící v SI má přidělený zdroj v SI P3 běžící v SI má přidělený zdroj v SI a
čeká na uvolnění zdroje v S2 drženého P4
P5 běžící v SI čeká na uvolnění zdroje v SI drženého Pl P2 běžící v S2 má přidělený zdroj v S2 a
čeká na uvolnění zdrojů v SI držených Pl a P3 P4 běžící v S2 má přidělený zdroj v S2 a
čeká na uvolnění zdroje v S2 drženého P2
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 27
Path-pushing, Obermarck
□ Nechť s1 odhalí cyklus Pz-pex-P2-Pz
□ Protože p3 žádá zdroj z s2, pošle s1 do s2 zprávu popisující
cyklus v si
□ s2 koriguje svůj lokální graf a odhalí existenci uváznutí -
cyklus, který neobsahuje pex:
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 28
Edge chasing, Chandy-Misra-Haas
□ Blokovaný proces vysílá testovací zprávu (próbe) procesu,
který drží jím požadovaný zdroj
□ Proces může čekat na více zdrojů najednou (AND model)
□ Testovací zpráva obsahuje
/ ID blokovaného procesu
/ ID procesu vysílajícího testovací zprávu
/ ID cílového procesu testovací zprávy
□ Když testovací zprávu přijme blokovaný proces, přepošle ji
procesu(ům) držícím zdroj, který požaduje
J ID blokovaného procesu se nemění, zbývající dva parametry se mění
□ Jestliže blokovaný proces získá svoji testovací zprávu,
detekovalo se uváznutí
\ Jan Staudek, FI MU Brno I PA150 - Detekce uváznutí v DS    29 )
Edge chasing, Chandy-Misra-Haas
Probe (1, 9, 1)
S3
PI launches
Probe (1. 3.4)
Probe (1,7, 10)
S2
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 30
Difusní algoritmus, Chandy at al, OR model
□ Výpočet detekce uváznutí difunduje skrz de facto systémový
WFG, po hranách čekání mezi procesy
□ Z uzlu vyhledávajícího detekci uváznutí jistého procesu se
vysílají testovací zprávy (probes) a ty difundují hranami WFG do ostatních uzlů
□ jestliže testovací zpráva dosáhne aktivní neblokovaný proces,
je zahozena
□ jestliže testovací zpráva dosáhne blokovaný proces, posílá se
echo zpět iniciátorovi, každý uzel na cestě vždy jakmile dostane echo od všech procesů, kterým poslal testovací zprávu
□ pokud všichni pošlou zpět echo iniciátorovi, nastalo uváznutí
Jan Staudek, FI MU Brno I PA150 - Detekce uváznutí v DS 31
Difusní algoritmus, Chandy at al
pi =
Testovací zpráva a odpověď
obsahují:
ID iniciátora,
ID vysílajícího uzlu,
ID přijímajícího uzlu
Pl vyhledává uváznutí
P2 message at P2 ľmin PI (P l .P I, ?2)
Pl => P3 mess lige ar P3 from P2 (Pl. P2. P3)
Pí -  P4 menage ni P4 from P3 (PL. P.v P4)
P4 => P?
P5 = P? =
ETC
]>■■■ r
?6-> P3 P7=:-P10 PS =■■ P10 =
end condition I-1
P9 (Pl. PS. P'1 j. nu™ replv (Pl. P9, Pl) P9 (PI P10. Pfl). now reply (Pl, P9. Pi)
IM     ]'? < P3 <= P4 P2<= P3 PI     P2 teply (PLF2. PI)
PS *:.= P9re|>lv{Pl, P9, PS) P J í)■=:= P9ľí[>lv{Pl, Pí», P10) P6 - PS reply (Pl, PS. PŮ) P7<=P10 reply (Pl, P10, P7)
P5 <= P6 ETC P5-==P7
PS cannot reply until both P6 and P' replies arrive !
\mk com
ih'titilock tontiition
Jan Staudek, FI MU Brno    PA150 - Detekce uváznutí v DS 32