Deadlock

Agenda Úvod Definícia deadlock-u Cofmanovepodmienky vylúčenia Stratégie riešenia zablokovania Bankárov algoritmus Deadlockna križovatke Deadlock Deadlockmôžeme definovaťako permanentnéblokovanie množiny procesov, kde každý súťaží-pretekáo systémovézdroje alebo o komunikáciu medzi sebou. Zablokovanie –množina procesov je zablokovaná, keďkaždý proces z tejto množiny čakána udalosťktorúmôže spôsobiťiba iný proces z tejto množiny. 4 nutnépodmienky zablokovania –Coffmana kol. 1971
9
nutnépodmienky pre nastatie deadlocku(všetky podmienky musia byťsplnenénaraz) Vzájomnévylúčenie(Mutualexclusion) Drža čakaj(Hold and wait) Neodnímateľnosť(No preemption) Čakanie do kruhu(Circularwait) Coffmanovepodmienky zablokovania Vzájomnévylúčenie -procesy aktuálne vlastniace nejaký prostriedok môžu žiadaťnovéprostriedky Drža čakaj-procesy aktuálne vlastniace nejaký prostriedok môžu žiadaťnovéprostriedky Neodnímateľnosť-pridelenéprostriedky nemôžu byťodňatéspäťhrubou silou. Musia byťvrátenéexplicitne procesom, ktorý ich vlastní. Čakanie do kruhu-existuje kruhový reťazec procesov, kde každý čakána prostriedok, ktorý je vlastnený ďalším článkom reťazca Stratégie riešenia zablokovania Ignorovanie –pštrosíalgoritmus Detekcia a zotavenie Dynamicképredchádzanie zablokovaniu Prevencia zablokovania Riešenia -ignorovanie Pštrosíalgoritmus nerobím pre riešenie zablokovania nič, nastáva zriedka a používateľsi pomôže sám. (praktickériešenie -Unix) Riešenie –detekcia a zotavenie OS sa nepokúša zabrániťvzniku zablokovania, zistívznik zablokovania a pokúša sa odstrániť detekcia deadlocku–algoritmus hľadania kružnice v orientovaných grafoch Riešenie -predchádzanie zablokovaniu opatrnéprideľovanie prostriedkov stav procesov a prostriedkov je bezpečný, ak nie je zablokovaný a existuje cesta, ako uspokojiťvšetky požiadavky na prostriedky spustením procesov v istom poradí(za spolupráce plánovača) 10
Dijkstra–Bankárov algoritmus Bankárov algoritmus –myšlienka Bankár mázákazníkov, sľúbil im istúvýšku úveru. Bankár vie, že nie všetci zákazníci chcúcelý úver ihneď, ale postupne. Zákazníci sa starajúo svoj obchod a občas prídu ku bankárovi s požiadavkou na ďalšie peniaze z úveru. Bankár peniaze vydáiba vtedy, ak aj potom „zostane banka v bezpečnom stave“. Ažzákazník skončíso svojím obchodom, vráti bankárovi celý úver. Bankárov algoritmus -popis simulovať_pridelenie: vytvorínovúkópiu zoznamu prostriedkov, ktorémásprávca momentálne k dispozícii a odoberie s tohto zoznamu prostiredok, o ktorý žiada proces, ktorého žiadosťje práve skúmaná. Kópia zoznamu prostriedkov je lokálna, pri ukončenífunkcie možno_prideliťautomaticky zanikne. možno_ukončiť, ktorej parametrom je číslo procesu, porovnámomentálny obsah lokálneho zoznamu prostriedkov s max budúcimi požiadavkami zadaného procesu. Vracia nulu, ak súpožiadavky procesu nesplniteľné(prílišveľké) simulovať_ukončenie, ktorej parametrom je tiežčíslo procesu, proste pridáku lokálnemu zoznamu všetky prostriedky, ktorémázadaný proces pridelené. Bankárov algoritmus -kód Riešenie –prevencia zablokovania: narušením jednej z Coffmanovýchpodmienok napadnutie vzájomného vylúčenia –spooling, môže viesťk zablokovaniu, miesto na disku napadnutie drža čakaj –zaistiťaby procesy čo užvlastnia prostriedky, ďalej nečakali –žiadaťo všetky naraz... napadnutie neodnímateľnosti–chaos napadnutie čakanie do kruhu –jednoznačne identifikovaťprostriedky a žiadaťich iba vo vzostupnom poradí