Deadlock - je uviaznutie skupiny procesov. K deadlocku dochadza, ak skupina procesov caka jeden na druheho. Uviaznutie mozeme modelovat pomocou alokacneho grafu
Aby doslo k uviaznutiu, tak musia byt splnene Coffmanove podmienky - nutne podmienky pre uviaznutie
- vzajomne vylucenie - prostriedok nemoze byt zdielany viacerymi procesmi (1 alebo ziaden)
- podmienka drz a cakaj - proces, ktory ma uz pridelene nejake prostriedky, moze ziadat o dalsie prostriedky
- podmienka neodnimatelnosti - prostriedok, ktory bol uz prideleny nejakemu procesu, mu nemoze byt nasilim odobrany
- podmienka cyklickeho cakania - musi existovat smycka dvoch a viac procesov, v ktorej kazdy proces caka na prostriedok prideleny dalsiemu prostriedku v smycke
Strategie riesenia uviaznutia
- pstrosi algoritmus
- problem ignorujeme
- ked sa stane, tak procesy ukoncime
- nesplnenie jednej z coffmanovych podmienok
- vzajomne vylucenie
- moznost zdielat prostriedky pomocou virtualizacie (napr. tlaciaren)
- podminka drz a cakaj
- kazdy proces musi alokovat vsetky potrebne prostriedky v okamihu spustenia - tu vznika problem efektivneho/optimalneho vyuzivania prostriedkov
- podmienka neodnimatelnosti
- v praxi tazko realizovatelne
- podmienka cyklickeho cakania
- proces bude moct alokovat viac prostriedkov v presne definovanom poradi
- a to len prostriedok s vyssim cislom, ako je maximum z alokovanych prostriedkov
- problem to ocislovat
- detekcia a zotavenie
- ak dojde k uviaznutiu, tak je detekovane a odstranene - to sa da sledovanim alokovanych a volnych prostriedkov a pozadovanych prostriedkov
- algoritmus
- kazdy proces je spociatku neoznaceny
- spravime maticu alokovanych prostriedkov, kde i je proces a j je typ prostriedku
- spravime maticu pozadovanych prostriedkov, kde i je proces a j je typ
- vytvorime vektor existujucich prostriedkov
- vytvorime vektor volnych prostriedkov
- pokusime sa najst neoznaceny proces, ktoreho riadok v matici pozadovanych prostriedkov ma mensie, alebo rovnake hodnoty ako prvky vektora volnych prostriedkov
- ak taky vektor nenajdeme, tak su vsetky procesy uviaznute
- dynamicke zabranenie uviaznutiu pomocou "korektnej" alokacie prostriedkov
- jedna sa o sposob pridelovania na zaklade rozhodnutia, ci je pridelenie bezpecne
- prikladom moze byt bankarov algoritmus
- bezpecny stav je, ze existuje alokacne poradie, ktore zarucuje, ze kazdy proces bude postupne uspokojeny a skonci
- ak by alokacia prostriedkov viedla na nebezpecny stav, tak ziadost bude odmietnuta
- pruser je, ze musime dopredu vediet, ake prostriedky sa po nas budu vyzadovat
