38 - Uváznutí při přidělování prostředků, detekce a řešení Flashcards
Přidělování prostředů, uváznutí a základní pojmy
Uváznutí
- každý proces má přiděleny nějaké prostředky (s omezenou kapacitou) a žádný nemůže pokračovat protože čeká na některý z blokovaných prostředků
- aneb: čekání na událost, která nenastane (prostředek, který nebude nikdy přidělen)
Kdy nastává?
- zamykání zámků, semaforů, souborů,..
- přidělování paměti (nebo bufferů) - je málo paměti, procesy chtějí víc, uváznou
- deadlock při zasílání zpráv
Příčiny uváznutí:
- Pouze jeden proces může používat přidělený prostředek, ostatní čekají
- Proces, který má přidělené prostředky, se při neúspěšné alokaci dalších nevzdá těchto prostředků, uvolní je až po ukončení
- Proces získává prostředky sekvenčně, oddělenými alokacemi
- Prostředek nemůže být preemptivně odebrán, proces sám uvolňuje prostředky
Problémy uváznutí
- Detekce - Jak zjistit které procesy uvázly?
- Zotavení - Jak se z uváznutí dostat?
- Prevence - Jak se uváznutí vyhnout?
Typy prostředků
- Serially Reusable (SR) - opakované použitelné
- Consumable Resources (CR) - jednorázové použitelné
Stav systému
- reprezentuje stav alokace prostředků
- přechody - stav je měněn procesy při požadavku (request), získání (allocation) a uvolnění (release) prostředku
blokovaný proces = nemůže změnit stav systému (Pokud není proces v daném stavu systému blokovaný může změnit jeho stav)
Uváznutý proces = je blokován a žádné změn stavu ho neodblokují
Stav uváznutí = stav systému, ve kterém je alespoň jeden uváznutý proces
Prevence uváznutí = omezení přechodů mezi stavy ale stavy uváznutí byly nedostupné
Bezpečný stav = nelze se z něj dostat do stavu uváznutí
PS: konstrukce grafu není v běžícím systému možná, jelikož nejsem předem známy požadavky
SR - Serially Reusable prostředky
SR prostředky:
- Prostředek se skládá z konstantního počtu stejných jednotek
- Jednotka je buďto volná nebo přidělená.
- Proces může uvolnit jednotku, pokud ji má přidělenu.
Graf alokace SR prostředků (prostředky - obdelník, procesy - kruh, přidělení, čekání)
- ukazuje stav systému pro SR prostředky
- Prostředek může být přidělen do maximální kapacity
- lze žádat maximálně o jeho celou kapacitu
Detekce uváznutí - hledá procesy, které nejsou zablokovány a mohou přivést systém do jiného stavu (požadavkem, přidělením, uvolněním)
!!! Procesy jsou zablokovány, pokud jejich požadavek nemůže být uspokojen ani nemohou uvolnit prostředky. !!!
Redukce grafu alokace prostředků - nezablokovaným procesem p - odstraňuje hrany z/do p přidělením požadovaných prostředků, dokončením procesu a jejich následným uvolněním.
- aneb spustíme a dokončíme proces
Neredukovatelný graf = nelze žádným procesem redukovat -> stav uváznutí
Úplně redukovatelný graf = je možné odstranit všechny hrany nějakou sekvencí redukcí. Všechny sekvence vedoucí k úplně redukovanému grafu jsou ekvivalentní.
Algoritmus detekce - Postupně prochází graf a redukuje jej - s využitím znalosti počtu požadovaných a přidělených prostředků
- Složitost O(mn)
Nutnou podmínkou uváznutí je cyklus v grafu alokace SR.
- Pokud graf neobsahuje cyklus nemůže nastat uváznutí - opačně to neplatí (bez cyklu nemůže být uváznutí, ale cyklus neznamená uváznutí)
SR - Speciální typy systémů
Knot = silná komponenta, ze které nevede žádná hrana ven, ale pouze dovnitř. Silná komponenta grafu je maximálně silně souvislý graf.
(Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů u, v existuje sled.)
Systém s okamžitým přidělením = přiděluje prostředky ihned. V grafu alokace SR prostředků pak zůstavají pouze neuspojitelné požadavky.
- Nutnou a postačující podmínkou uváznutí v systému s okamžitým přidělováním je KNOT v grafu alokace
Systém s prostředky kapacity 1 = všechny prostředky mají kapacitu pouze 1
- Nutnou a postačující podmínkou uváznutí v systému s prostředky kapacity 1 je CYKLUS v grafu alokace
Systém s jednotkovými požadavky = procesy žádají o maximálně jednu jednotku prostředku
- Nutnou a postačující podmínkou uváznutí v systému s jednotkovými požadavky je KNOT v grafu alokace
SR - zotavení z uváznutí
a) násilným ukončením procesu
b) odebráním prostředků
- Přímé - blokující požadavek na prostředky je ukončen chybou “prostředky odebrány”
- Nepříme - návrat k předchozímu stavu (rollback na checkpoint)
Výběr procesu pro odebrání SR prostředků podle:
- priorita procesu
- cena znovuprovedení
- typ procesu (systémový, uživatelský, …)
Po odebrání se změní stav (graf) a přepočítá se.
SR - prevence uváznutí
= omezuje přechody tak, aby se uváznutí vyhnula
Metody
- Sdílení prostředků (ale to porušuje podmínku výlučnosti).
- Přidělovat vždy všechny prostředky najednou jednomu procesu jedním požadavkem (neefektivní).
- Každému procesu umožnit držet vždy jen jeden prostředek (ne vždy možné - některé procesy mohou potřebovat držet více prostředků v jeden okamžik).
- Při požadavku další jednotky se nejprve všech vzdát a žádat najednou (né vždy možné)
- Používat blokující požadavky pouze pokud ještě žádné prostředky nevlastní, o další žádá neblokujícím způsobem. Pokud se nepodaří získat všechny, musí se všech vzdát a žádat znovu.
- Prostředky žádat v pevném pořadí (vzrůstající), pak nemůže vzniknout uváznutí (nejpoužívanější).
Bankéřův algoritmus - omezuje maximální počet požadavků
- Každý proces v systému deklaruje svoje maximální požadavky na prostředky
- Je kontrolováno zda: < počet_přidělených_prostředků > + < počet_požadovaných_prostředků > < = < deklarované_maximum >
Princip algoritmu:
Povolit pouze takové přidělení, po kterém existuje alespoň jedna posloupnost uspokojení maximálních požadavků všech procesů.
CR prostředky - Consumable - jednorázové prostředky
- CR - jednorázově použitelné - consumable resources
- počet dostupných prostředků se mění konzumováním a produkcí
- počet jednotek není omezen
Neomezený systém - !!!prevence není možná!!!
- Stav uváznutí - všechny procesy zablokované
- Zotavení - Pokud není některý proces zablokovaný může vyprodukovat libovolný počet prostředků a tím ostatní uvolnit
- Prevence - Žádný stav systému není bezpečný !!!prevence není možná!!!
Systém se známými producenty - !!!prevence není možná!!!
- Stav uváznutí - uváznutí pro všechny zúčastněné procesy (neexistuje žádný postup redukcí vedoucí na stav,kde proces není zablokován)
- Zotavení - zrušení zablokovaného procesu, pokud možno ne producenta
- Prevence - Žádný stav systému není bezpečný (prevence není možná)
- Zablokování může nastat při požadavku i přidělení
- Nutnou podmínkou uváznutí je cyklus v grafu alokace
- !!! záleží na pořadí redukcí !!! Pořadí redukcí v grafu alokací je důležité (mění se počet jednotek)
Systém se známými producenty a konzumenty = pro každý prostředek je definována množina producentů a konzumentů tohoto prostředku
- Všechny stavy jsou bezpečné pokud je graf blokovaných požadavků redukovatelný
- Na pořadí redukcí nezáleží
- Systém není bezpečný pokud neexistuje alespoň jeden proces, který nic nekonzumuje = systím je bezpečný pokud existuje alespoň jeden proces, který nic nekonzumuje
