Zablokování - Deadlock - Wikipedia

Nesmí být zaměňována s Deathlok nebo Dreadlock.
Tento článek je o konceptu počítačové vědy. Pro další použití viz Zablokování (disambiguation).
"Livelock" přeadresuje tady. Informace o videohře viz Livelock (videohra).

Oba procesy potřebují prostředky, aby mohly pokračovat v provádění. P1 vyžaduje další zdroj R1 a má zdroj 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), přičemž se řídí pravidlem před a vlevo. K zablokování dochází, když všechny procesy uzamknou zdroj současně (černé čáry). Zablokování lze vyřešit porušením symetrie.

v souběžné výpočty, a zablokování je stav, ve kterém každý člen skupiny čeká na jiného člena, včetně sebe, aby provedl akci, jako je odeslání zprávy nebo běžnější uvolnění zámek.[1] Zablokování je běžný problém v multiprocesing systémy, paralelní výpočty, a distribuované systémy, kde se softwarové a hardwarové zámky používají k rozhodování o sdílených zdrojích a jejich implementaci synchronizace procesu.[2]

V operační systém, zablokování nastane, když a proces nebo vlákno vstoupí do čekání Stát protože požadováno systémový zdroj je zadržen jiným čekajícím procesem, který zase čeká na jiný zdroj zadržený jiným čekajícím procesem. Pokud proces není schopen donekonečna měnit svůj stav, protože zdroje, které požaduje, používá jiný čekající proces, pak se říká, že je systém v mrtvém bodě.[3]

V komunikační systém, zablokování dochází hlavně kvůli ztraceným nebo poškozeným signálům, spíše než kvůli sporu o zdroje.[4]

Dva procesy soutěží o dva zdroje v opačném pořadí.
  1. Prochází jediný 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

Situace zablokování zdroje může nastat tehdy a jen tehdy, pokud všechny následující podmínky platí současně v systému:[5]

  1. Vzájemné vyloučení: Alespoň jeden prostředek musí být uchováván v režimu, který nelze sdílet. Jinak by procesům nebylo zabráněno v použití zdroje, pokud je to nutné. Pouze jeden proces může použít prostředek v daném okamžiku.[6]
  2. Počkejte a počkejte nebo držení zdrojů: proces aktuálně drží alespoň jeden zdroj a požaduje další zdroje, které jsou zadržovány jinými procesy.
  3. Ne preempce: zdroj může být uvolněn pouze dobrovolně procesem, který jej drží.
  4. Kruhové čekání: každý proces musí čekat na zdroj, který je držen jiným procesem, který zase čeká, až první proces uvolní zdroj. Obecně platí, že soubor čekajících procesů, P = {P1, P2, …, PN}, takhle P1 čeká na zdroj v držení P2, P2 čeká na zdroj v držení P3 a tak dále, dokud PN čeká na zdroj v držení P1.[3][7]

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

I když tyto podmínky jsou dostatečné k vytvoření zablokování v systémech prostředků s jednou instancí, naznačují pouze možnost zablokování v systémech, které mají více instancí prostředků.[8]

Zablokování

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

Ignorování zablokování

V tomto přístupu se předpokládá, že k zablokování nikdy nedojde. Toto je také aplikace Pštrosí algoritmus.[10][11] Tento přístup původně používal MINIX a UNIX.[7] Používá se, 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 zablokování existuje formálně prokázáno nikdy nenastane. Příkladem je rámec RTIC.[12]

Detekce

Pod detekcí zablokování může dojít k zablokování. Poté se prozkoumá stav systému, aby se zjistilo, že došlo k zablokování, a následně se opraví. Je použit algoritmus, který sleduje alokaci prostředků a stavy procesů, vrací se zpět a restartuje jeden nebo více procesů, aby odstranil detekované zablokování. Detekce zablokování, ke kterému již došlo, je snadno možná, protože prostředky, které každý proces uzamkl nebo aktuálně požaduje, jsou známy plánovači prostředků operačního systému.[11]

Po zjištění zablokování je možné jej opravit pomocí jedné z následujících metod:[Citace je zapotřebí ]

  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 soutěžící procesy zapojený do slepé uličky. Tím je zajištěno, že zablokování bude vyřešeno s jistotou a rychlostí.[Citace je zapotřebí ] Ale výdaje jsou vysoké, protože částečné výpočty budou ztraceny. Nebo by se dalo zvolit přerušení jednoho procesu po druhém, 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ě.[Citace je zapotřebí ] Při výběru kandidáta na ukončení je třeba vzít v úvahu několik faktorů, jako je priorita a věk procesu.[Citace je zapotřebí ]
  2. Předpoklad zdroje: zdroje přidělené různým procesům mohou být postupně preempovány a přidělovány jiným procesům, dokud nedojde k narušení zablokování.[13]

Prevence

Hlavní článek: Algoritmy prevence zablokování
(A) Dva procesy soutěžící o jeden zdroj podle zásady „kdo dřív přijde, je dřív na řadě“. (B) Zablokování nastane, když oba procesy uzamknou zdroj současně. (C) Zablokování může být vyřešen porušením symetrie zámků. (D) Zablokování může být zabráněno porušením symetrie zajišťovacího mechanismu.

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

  • Demontáž vzájemné vyloučení podmínka znamená, že žádný proces nebude mít výhradní přístup ke zdroji. To se ukazuje jako nemožné pro zdroje, které nemohou být zařazen. Ale i při zařazení zdrojů mohlo dojít k zablokování. Algoritmy, které se vyhýbají vzájemnému vyloučení, se nazývají neblokující synchronizace algoritmy.
  • The vydrž a počkej nebo držení zdrojů podmínky lze odstranit požadavkem, aby procesy vyžadovaly všechny zdroje, které budou potřebovat před spuštěním (nebo před zahájením konkrétní sady operací). Tyto pokročilé 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 vyžadovat, aby procesy požadovaly prostředky, pouze pokud žádné nemají; Nejprve musí uvolnit všechny své aktuálně držené zdroje, než si od začátku vyžádají všechny zdroje, které budou potřebovat. I to je často nepraktické. Je to tak proto, že zdroje mohou být přiděleny a po dlouhou dobu zůstanou nevyužité. Proces vyžadující populární zdroj může také muset čekat neomezeně dlouho, protože takový prostředek může být vždy přidělen nějakému procesu, což má za následek hladovění zdrojů.[14] (Tyto algoritmy, jako např serializační tokeny, jsou známé jako algoritmy typu „vše nebo nikdo“.)
  • The Ne preempce podmínce může být také obtížné nebo nemožné se 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 mlácení může nastat. Neschopnost prosadit preempci však může narušit a přednost algoritmus. Předpoklad „uzamčeného“ zdroje obecně znamená a vrácení zpět a je třeba se mu vyhnout, protože je to velmi nákladné z režie. Algoritmy, které umožňují preempci, zahrnují algoritmy bez zámku a bez čekání a optimistické řízení souběžnosti. Pokud proces obsahující některé zdroje a požaduje jiné zdroje, které k němu nelze okamžitě přidělit, může být podmínka odstraněna uvolněním všech aktuálně zadržovaných prostředků daného procesu.
  • Konečnou podmínkou je kruhové čekání stav. Přístupy, které zabraňují kruhovému čekání, zahrnují deaktivaci přerušení během kritických sekcí a použití hierarchie k určení částečné objednání zdrojů. Pokud neexistuje žádná zřejmá hierarchie, byla k určení řazení použita i adresa paměti prostředků a prostředky jsou požadovány v rostoucím pořadí výčtu.[3] Dijkstraovo řešení lze také použít.

Livelock

A živý zámek je podobný zablokování, kromě toho, že stavy procesů zapojených do zablokování se navzájem neustále mění, žádný nepostupuje.

Termín vytvořil Edward A. Ashcroft v článku z roku 1975[15] v souvislosti s přezkoumáním rezervačních systémů leteckých společností.[16] Livelock je speciální případ hladovění zdrojů; obecná definice pouze uvádí, že určitý proces neprobíhá.[17]

Livelock je pro některé riziko algoritmy které detekují a zotavují se z zablokování. Pokud přijme opatření více než jeden proces, algoritmus detekce zablokování lze opakovaně spustit. Tomu se lze vyhnout zajištěním toho, že pouze jeden proces (zvolený libovolně nebo podle priority) provede akci.[18]

Distribuované zablokování

Distribuované zablokování může nastat v distribuované systémy když distribuované transakce nebo řízení souběžnosti se používá.

Distribuované zablokování lze zjistit buď vytvořením globálního čekat na graf z místních grafů čekání na zablokování detektoru nebo a distribuovaný algoritmus jako pronásledová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í.

Například pokud proces uvolní prostředek R1 a vydá žádost o R2a první zpráva je ztracena nebo zpožděna, mohl by koordinátor (detektor zablokování) falešně uzavřít zablokování (pokud je žádost o R2 zatímco má R1 způsobí zablokování).

Viz také

Reference

  1. ^ Coulouris, George (2012). Koncepty a design distribuovaných systémů. Pearson. p. 716. ISBN  978-0-273-76059-7.
  2. ^ Padova, David (2011). Encyclopedia of Parallel Computing. Springer. p. 524. ISBN  9780387097657. Citováno 28. ledna 2012.
  3. ^ A b C Silberschatz, Abraham (2006). Principy operačního systému (7. vydání). Wiley-Indie. p. 237. ISBN  9788126509621. Citováno 29. ledna 2012.
  4. ^ Schneider, G. Michael (2009). Pozvánka na informatiku. Cengage Learning. p. 271. ISBN  978-0324788594. Citováno 28. ledna 2012.
  5. ^ Silberschatz, Abraham (2006). Principy operačního systému (7 ed.). Wiley-Indie. p. 239. ISBN  9788126509621. Citováno 29. ledna 2012.
  6. ^ „ECS 150 jaro 1999: čtyři nezbytné a dostatečné podmínky pro zablokování“. nob.cs.ucdavis.edu. Archivováno z původního dne 29. dubna 2018. Citováno 29. dubna 2018.
  7. ^ A b C Shibu, K. (2009). Úvod do vestavěných systémů (1. vyd.). Tata McGraw-Hill Education. p. 446. ISBN  9780070145894. Citováno 28. ledna 2012.
  8. ^ „Operační systémy: zablokování“. www.cs.uic.edu. Citováno 25. dubna 2020. Pokud kategorie prostředků obsahuje více než jednu instanci, pak přítomnost cyklu v grafu přidělení prostředků naznačuje možnost zablokování, ale nezaručuje ji. Zvažte například obrázky 7.3 a 7.4 níže:
  9. ^ Silberschatz, Abraham (2006). Principy operačního systému (7 ed.). Wiley-Indie. p. 237. ISBN  9788126509621. Citováno 29. ledna 2012.
  10. ^ A b Stuart, Brian L. (2008). Principy operačních systémů (1. vyd.). Cengage Learning. p. 446. ISBN  9781418837693. Citováno 28. ledna 2012.
  11. ^ A b Tanenbaum, Andrew S. (1995). Distribuované operační systémy (1. vyd.). Pearson Education. p. 117. ISBN  9788177581799. Citováno 28. ledna 2012.
  12. ^ https://rtic.rs/0.5/book/en/
  13. ^ „IBM Knowledge Center“. www.ibm.com. Archivováno z původního dne 19. března 2017. Citováno 29. dubna 2018.
  14. ^ Silberschatz, Abraham (2006). Principy operačního systému (7 ed.). Wiley-Indie. p. 244. ISBN  9788126509621. Citováno 29. ledna 2012.
  15. ^ Ashcroft, E.A. (1975). Msgstr "Prokazování tvrzení o paralelních programech". Journal of Computer and System Sciences. 10: 110–135. doi:10.1016 / S0022-0000 (75) 80018-3.
  16. ^ Kwong, Y. S. (1979). "O absenci živých zámků v paralelních programech". Sémantika souběžného výpočtu. Přednášky z informatiky. 70. 172–190. doi:10.1007 / BFb0022469. ISBN  3-540-09511-X.
  17. ^ Anderson, James H .; Yong-jik Kim (2001). „Vzájemné vyloučení sdílené paměti: hlavní trendy výzkumu od roku 1986“. Archivováno z původního dne 25. května 2006.
  18. ^ Zöbel, Dieter (říjen 1983). "Problém zablokování: klasifikační bibliografie". Recenze operačních systémů ACM SIGOPS. 17 (4): 6–15. doi:10.1145/850752.850753. ISSN  0163-5980. S2CID  38901737.

Další čtení

externí odkazy