Zablokování - Deadlock

Nesmí být zaměňována s Deathlok nebo Dreadlock .
Tento článek je o konceptu počítačové vědy. Pro jiná použití, viz Zablokování (disambiguation) .

Oba procesy potřebují prostředky, aby mohly pokračovat v provádění. P1 vyžaduje další zdroj R1 a je v držení zdroje R2 , P2 vyžaduje další zdroj R2 a je v držení R1 ; ani jeden proces nemůže pokračovat.
Čtyři procesy (modré čáry) soutěží o jeden zdroj (šedý kruh) podle zásad zprava doleva. K zablokování dochází, když všechny procesy současně zamknou zdroj (černé čáry). Zablokování lze vyřešit porušením symetrie.

V souběžném výpočtu je zablokování stav, ve kterém každý člen skupiny čeká, až jiný člen, včetně sebe, provede akci, jako je odeslání zprávy nebo běžnější uvolnění zámku . Uváznutí jsou běžným problémem v multiprocesních systémech, paralelních počítačích a distribuovaných systémech , kde se softwarové a hardwarové zámky používají k arbitraci sdílených zdrojů a implementaci synchronizace procesů .

V operačním systému dojde k zablokování, když proces nebo vlákno přejde do stavu čekání, protože požadovaný systémový prostředek je zadržen jiným procesem čekání, který zase čeká na jiný prostředek držený jiným procesem čekání. Pokud proces není schopen změnit svůj stav na neurčito, protože jím požadované prostředky jsou používány jiným čekajícím procesem, pak je systém údajně v mrtvém bodě.

V komunikačním systému dochází k zablokování hlavně kvůli ztraceným nebo poškozeným signálům, než kvůli sporům o zdroje.

Dva procesy soutěžící o dva zdroje v opačném pořadí.
  1. Prochází jeden proces.
  2. Pozdější proces musí počkat.
  3. K zablokování dochází, když první proces uzamkne první prostředek současně s tím, jak druhý proces uzamkne druhý prostředek.
  4. Zablokování lze vyřešit zrušením a restartováním prvního procesu.

Nezbytné podmínky

K zablokování zdroje může dojít tehdy a jen tehdy, pokud v systému nastanou současně všechny následující podmínky:

  1. Vzájemné vyloučení : Nejméně dva zdroje musí být drženy v režimu, který nelze sdílet. V opačném případě by procesům nebránilo v případě potřeby použít prostředek. V daném okamžiku může zdroj použít pouze jeden proces.
  2. Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being dedicated by other processes.
  3. Žádná preemption : zdroj může být uvolněn pouze dobrovolně procesem, který jej drží.
  4. Cirkulární čekání: každý proces musí čekat na zdroj, který je držen jiným procesem, který zase čeká na první proces uvolnění zdroje. Obecně existuje sada procesů čekání, P = { P 1 , P 2 , ..., P N }, takže P 1 čeká na zdroj držený P 2 , P 2 čeká na zdroj v držení P 3 a tak dále, dokud P N nečeká na zdroj držený P 1 .

Tyto čtyři podmínky jsou známé jako Coffmanovy podmínky z jejich prvního popisu v článku Edwarda G. Coffmana, Jr. z roku 1971.

Tyto podmínky jsou dostatečné k vytvoření zablokování v systémech prostředků s jednou instancí, ale pouze naznačují možnost zablokování v systémech s více instancemi prostředků.

Ovládání zablokování

Většina současných operačních systémů nemůže zabránit zablokování. Když dojde k zablokování, reagují na ně různé operační systémy různými nestandardními způsoby. Většina přístupů funguje tak, že zabrání vzniku jedné ze čtyř Coffmanových podmínek, zejména té čtvrté. Hlavní přístupy jsou následující.

Ignorování zablokování

Při tomto přístupu se předpokládá, že k zablokování nikdy nedojde. Toto je také aplikace pštrosího algoritmu . Tento přístup původně používaly systémy MINIX a UNIX . To se používá, když jsou časové intervaly mezi výskyty zablokování velké a ztráta dat vzniklá pokaždé je tolerovatelná.

Ignorování zablokování lze bezpečně provést, pokud se formálně prokáže, že k zablokování nikdy nedochází. Příkladem je rámec RTIC.

Detekce

Při detekci zablokování je povolen výskyt zablokování. Poté se prozkoumá stav systému, aby se zjistilo, že došlo k zablokování, a následně je opraven. Je použit algoritmus, který sleduje přidělování zdrojů a stavy procesů, vrací se zpět a restartuje jeden nebo více procesů, aby odstranil detekovaný zablokování. Zjištění zablokování, ke kterému již došlo, je snadno možné, protože prostředky, které každý proces zamkl a/nebo aktuálně požaduje, jsou známy plánovači prostředků operačního systému.

Jakmile je zablokování detekováno, lze jej opravit pomocí jedné z následujících metod:

  1. Ukončení procesu: jeden nebo více procesů zapojených do zablokování může být přerušeno. Dalo by se rozhodnout přerušit všechny konkurenční procesy zahrnuté v zablokování. Tím je zajištěno, že se zablokování vyřeší s jistotou a rychlostí. Ale náklady jsou vysoké, protože částečné výpočty budou ztraceny. Nebo se můžete rozhodnout přerušit jeden proces najednou, dokud nebude zablokování vyřešeno. Tento přístup má vysokou režii, protože po každém přerušení musí algoritmus určit, zda je systém stále v mrtvém bodě. Při výběru kandidáta na ukončení musí být zváženo několik faktorů, jako je priorita a věk procesu.
  2. Preemption zdrojů : prostředky přidělené různým procesům mohou být postupně předřazeny a přiděleny jiným procesům, dokud nedojde k přerušení zablokování.

Prevence

Hlavní článek: Algoritmy prevence zablokování
(A) Dva procesy soutěží o jeden zdroj podle zásady „kdo dřív přijde, ten dřív mele“. (B) K zablokování dochází, když oba procesy současně zamknou zdroj. (C) Zablokování lze vyřešit porušením symetrie zámků. (D) Zablokování lze zabránit porušením symetrie uzamykacího mechanismu.

Prevence zablokování funguje tak, že brání vzniku jedné ze čtyř Coffmanových podmínek.

  • Odebrání podmínky vzájemného vyloučení znamená, že žádný proces nebude mít výhradní přístup ke zdroji. U zdrojů, které nelze zařadit do spoolového programu, se to ukáže jako nemožné . Ale i při spoolovaných zdrojích může stále dojít k zablokování. Algoritmy, které se vyhýbají vzájemnému vyloučení, se nazývají neblokující synchronizační algoritmy.
  • Podmínky pozastavení a čekání nebo držení zdrojů mohou být odstraněny tím, že procesy vyžadují, aby si před spuštěním (nebo před zahájením konkrétní sady operací) vyžádaly všechny zdroje, které budou potřebovat. Tyto předběžné znalosti je často obtížné uspokojit a v každém případě jde o neefektivní využívání zdrojů. Dalším způsobem je požadovat, aby procesy požadovaly prostředky pouze tehdy, když žádné nemají; Nejprve musí uvolnit všechny své aktuálně držené zdroje, než budou od začátku požadovat všechny zdroje, které budou potřebovat. I to je často nepraktické. Je tomu tak proto, že prostředky mohou být přiděleny a zůstávají delší dobu nevyužité. Také proces vyžadující populární zdroj může muset čekat donekonečna, protože takový zdroj může být vždy přidělen nějakému procesu, což má za následek hladovění zdrojů . (Tyto algoritmy, jako jsou serializační tokeny , jsou známé jako algoritmy typu vše nebo nic .)
  • Podmínky bez preemption může být také obtížné nebo nemožné se jim vyhnout, protože proces musí být schopen mít zdroj po určitou dobu, nebo může být výsledek zpracování nekonzistentní nebo může dojít k mlácení . Neschopnost vynutit preemption však může interferovat s algoritmem priority . Prevence zdroje „uzamčeného“ obecně znamená vrácení a je třeba se mu vyhnout, protože je velmi nákladný v režii. Algoritmy, které umožňují preempci, zahrnují algoritmy bez zámku a bez čekání a optimistické řízení souběžnosti . Pokud proces obsahuje určité prostředky a požaduje jiný zdroj (zdroje), které mu nelze okamžitě přidělit, může být podmínka odstraněna uvolněním všech aktuálně držených prostředků tohoto procesu.
  • Konečnou podmínkou je podmínka kruhového čekání . Přístupy, které se vyhýbají cyklickému čekání, zahrnují deaktivaci přerušení během kritických sekcí a použití hierarchie k určení částečného řazení zdrojů. Pokud neexistuje žádná zjevná hierarchie, byla k určení řazení použita i adresa paměti prostředků a prostředky jsou požadovány ve vzrůstajícím pořadí výčtu. Lze také použít řešení společnosti Dijkstra .

Livelock

„Livelock“ přeadresuje tady. Videohru najdete v části Livelock (videohra) .

Livelock je podobný zablokování, s výjimkou, že stavy procesů zapojených do livelock neustále mění, pokud jde o sobě žádný postupující.

Termín vytvořil Edward A. Ashcroft v dokumentu z roku 1975 v souvislosti se zkoumáním rezervačních systémů leteckých společností. Livelock je zvláštní případ hladovění zdrojů ; obecná definice pouze uvádí, že konkrétní proces neprobíhá.

Livelock je riziko u některých algoritmů, které detekují a zotavují se z zablokování . Pokud provede akci více než jeden proces, lze algoritmus detekce zablokování opakovaně spustit. Tomu se lze vyhnout tím, že zajistíme, aby akce prováděl pouze jeden proces (zvolený libovolně nebo podle priority).

Distribuovaná zablokování

Distribuované zablokování může v distribuovaných systémech nastat při použití distribuovaných transakcí nebo řízení souběžnosti .

Distribuované zablokování lze detekovat buď vytvořením globálního grafu čekání z místních grafů čekání na detektor zablokování, nebo distribuovaným algoritmem, jako je honění hran .

Fantomová zablokování jsou zablokování, která jsou v distribuovaném systému falešně detekována kvůli interním zpožděním systému, ale ve skutečnosti neexistují.

Pokud například proces uvolní zdroj R1 a vydá požadavek na R2 a první zpráva bude ztracena nebo zpožděna, koordinátor (detektor zablokování) by mohl nepravdivě uzavřít zablokování (pokud by požadavek na R2 s R1 měl za následek zablokování).

Viz také

Reference

Další čtení

externí odkazy