Deadlock: Porovnání verzí

'''Deadlock''' (česky také '''uváznutí''', '''vzájemné čekání''') je odborný výraz pro situaci, kdy úspěšné dokončení první akce je podmíněno předchozím dokončením druhé akce, přičemž druhá akce může být dokončena až po dokončení první akce. Vzniká [[paradox]], často označovaný jako ‚Co bylo dříve? Slepice nebo vejce?‘. V reálném životě se uváznutí řeší např. couváním (v dopravě).

 

 

== Řešení zablokování ==

* Předcházení (prevence) – napadení jedné z Coffmanových podmínek

* Vyhýbání se – [[Operační systém]] vyhoví žádosti o přidělení prostředku pouze pokud zůstane v bezpečném stavu (tj. existuje cesta, jak uspokojit všechny požadavky na prostředky jejich přidělováním v určitém pořadí) – viz bankéřův algoritmus. Procesy musí předem specifikovat všechny prostředky, které budou potřebovat; v současných operačních systémech k tomu obvykle nejsou nástroje.

 

=== Bankéřův algoritmus ===

Bankéřův algoritmus se používá hlavně u prostředků, kterých se přiděluje určité množství (jednotky s výměnnými médii, jako jsou magnetopáskové jednotky, diskové jednotky u [[Mainframe|sálových počítačů]], [[Operační paměť|paměť]], odkládací prostor). Bankéř (operační systém) má klienty (procesy) a těm slíbil jistou výšku úvěru (maximální množství prostředků). Bankéř ví, že ne všichni klienti potřebují plnou výši úvěru najednou. Klienti občas navštíví banku a žádají postupně o prostředky až do maximální výše úvěru. Klient v konečném čase obchod dokončí a bance vypůjčené prostředky vrátí. Bankéř peníze půjčí pouze tehdy, zůstane-li banka v bezpečném stavu. To znamená, že existuje cesta, jak v každém okamžiku přidělit alespoň jednomu z klientů předem uvedené maximální množství prostředků, a poté, co všechny své prostředky vrátí, postupně uspokojovat další klienty.{{Sfn|Dijkstra|1968|loc=6.1. The Banker's Algorithm}}

=== Detekce deadlocku ===

Obecně je předvídání deadlocku nemožné (je ekvivalentní s [[Problém zastavení|problémem zastavení]]) – nemůžeme zjistit, na jaký prostředek bude proces čekat, ani jestli ho proces, který ho zrovna drží, bude ochoten včas uvolnit. Pokud se ovšem omezíme na detekci uváznutí mezi procesy čekajícími na určité typy událostí – např. [[operační systém]] sleduje alokované prostředky – jedná se o [[algoritmus]] hledání [[Kružnice (graf)|cyklu]] v [[Graf (teorie grafů)|grafu]].

 

== Odkazy ==

=== Reference ===

<references />

* [[Petriho síť]]

* [[Transakční paměť]]

 

[[Kategorie:Synchronizace]]