Priority inversion je situace, kdy procesy s vyšší prioritou čekají na něco, co vlastní procesy s nižší prioritou. V nejhorším případě může priority inversion vést i k deadlocku. Řešením priority inversion může být priority inheritance.
Inversion and active and passive waiting ...
Z principu se podpora priority inheritance zdá být jednoduchá. V okamžiku, kdy proces začne na něco čekat, se jeho priorita propůjčí procesu vlastnícímu to, na co se čeká. Problém je v tom, že tohle funguje dobře u zámků, které mají jednoho vlastníka, ale u semaforů nebo condition variables se už nedá zjistit, kdo vlastně bude ten proces, který vázaný prostředek uvolní, a komu se tedy má priorita půjčit.
Řešení například v Solarisu, priority inheritance funguje přímočaře u mutexů, read write zámky zvýší prioritu prvního vlastníka a dalších už ne, condition variables nedělají nic.
Ke hladovění dochází v případě, kdy je některý proces neustále odkládán, přestože by mohl běžet. Tohle lze dobře ukázat například u čtenářů a písařů, kde písař může prostě čekat, protože někdo pořád čte. Při řešení synchronizačních úloh je proto často důležité, aby použité algoritmy zaručovaly, že nedojde ke hladovění.
Pokud jde o uváznutí synchronizovaných procesů, v podstatě se nabízí tři možnosti, jak se s uváznutím vypořádat, totiž zotavení, prevence a vyhýbání se.
Zotavení je technika, při které systém detekuje vznik deadlocku a odstraní ho. Hned dva problémy, jak detekovat a jak odstranit. Dokud systém ví, kdo na koho čeká, může detekovat prostým hledáním cyklů v grafu. Jakmile se ale neví, kdo na koho čeká, nejde to (e.g. aktivní čekání, user level implementace synchronizace a threadů). Mohou se použít náhradní techniky, například watchdogs, ale to není spolehlivé.
Pokud připustíme, že umíme deadlock detekovat, jeho odstranění také není triviální. Když se podíváme na prostředky, lze je rozdělit na preemptivní a nepreemptivní, pouze ty první lze procesu bezpečně odebrat. Mezi preemptivní prostředky se dá řadit například fyzická paměť, nepreemptivní je skoro všechno ostatní. Sebrat procesu nepreemptivní prostředek jen tak nejde, násilně ukončit proces může způsobit další problémy. Částečné řešení nabízejí transakce s možností rollbacku a retry.
Prevence uváznutí znamená, že procesy se naprogramují tak, aby nemohly uváznout. Aby mohly procesy uváznout, musí současně platit čtyři podmínky:
procesy musí čekat na prostředky v cyklu
procesy musí prostředky vlastnit výhradně
procesy musí být schopny přibírat si vlastnictví prostředků
prostředky nesmí být možné vrátit
Řešení jsou pak založena na odstranění některé z těchto podmínek, na první je to například uspořádání prostředků a jejich získávání v pořadí určeném tímto uspořádáním, na druhou virtualizace, na třetí současné zamykání všech prostředků, na čtvrtou spin styl zamykání prostředků.
Vyhýbání se deadlocku spočívá v tom, že procesy předem poskytují dost informací o tom, na které prostředky budou ještě čekat. Samozřejmě, to je problematické, ale občas se to dělá.
Ze škatulky vyhýbání se deadlocku je i bankéřův algoritmus. Jeho jméno pochází z modelové situace, kdy bankéř nabízí zákazníkům půjčky do určitého limitu, a jeho celkový kapitál je menší než počet zákazníků krát limit. Při každé žádosti o půjčku bankéř zkontroluje, zda po půjčení zůstane dost peněz na to, aby si alespoň jeden zákazník mohl vybrat plný limit, postupně pro všechny zákazníky. Pokud ano, půjčí, pokud ne, čeká. Předpokládá se, že pokud si alespoň jeden zákazník může vybrat plný limit, časem bude muset něco vrátit, a tím budou peníze na uspokojení ostatních zákazníků.