Vzájemné vyloučení - Mutual exclusion

Pro koncept v logice a teorii pravděpodobnosti viz Vzájemná exkluzivita .

Dva uzly a souběžné odebrání způsobí, že uzel nebude odebrán.

V informatice je vzájemné vyloučení vlastností řízení souběžnosti , které je zavedeno za účelem prevence rasových podmínek . Je to požadavek, aby jeden podproces spuštění nikdy nevstoupil do kritické sekce, zatímco souběžný podproces provádění již přistupuje ke kritické sekci, což se týká časového intervalu, během kterého vlákno spuštění přistupuje ke sdílenému prostředku , například [Sdílené datové objekty , sdílené zdroje, sdílená paměť].

Sdílený prostředek je datový objekt, který se pokoušejí upravit dvě nebo více souběžných vláken (kde jsou povoleny dvě souběžné operace čtení, ale nejsou povoleny žádné dvě operace souběžného zápisu ani jedno čtení a jeden zápis, protože to vede k nekonzistenci dat). Algoritmus vzájemného vyloučení zajišťuje, že pokud proces již provádí operaci zápisu na datový objekt [kritická část], žádný jiný proces/vlákno nesmí přistupovat/upravovat stejný objekt, dokud první proces nedokončí zápis na datový objekt [kritická sekce] a uvolnil objekt pro další procesy ke čtení a zápisu.

Požadavek vzájemného vyloučení poprvé identifikoval a vyřešil Edsger W. Dijkstra ve svém klíčovém článku z roku 1965 „Řešení problému v řízení souběžného programování“, který je připisován jako první téma při studiu souběžných algoritmů .

Jednoduchý příklad toho, proč je vzájemné vyloučení v praxi důležité, lze vizualizovat pomocí jednotlivě propojeného seznamu čtyř položek, kde mají být odstraněny druhé a třetí. Odebrání uzlu, který leží mezi 2 dalšími uzly, se provádí změnou dalšího ukazatele předchozího uzlu tak, aby směřoval na další uzel (jinými slovy, pokud se uzel odebírá, pak se další ukazatel uzlu změní na bod na uzel , čímž se z propojeného seznamu odstraní jakýkoli odkaz na uzel ). Když je takový propojený seznam sdílen mezi více vlákny provádění, dvě vlákna provádění se mohou pokusit odebrat dva různé uzly současně, přičemž jedno vlákno spuštění změní další ukazatel uzlu na bod na uzel , zatímco jiné vlákno spuštění změní další ukazatel uzlu na bod na uzel . Ačkoli jsou obě operace odebrání úspěšně dokončeny, není dosaženo požadovaného stavu propojeného seznamu: uzel zůstane v seznamu, protože další ukazatel uzlu ukazuje na uzel .

Tomuto problému (nazývanému závodní podmínka ) se lze vyhnout použitím požadavku vzájemného vyloučení, aby bylo zajištěno, že nemůže dojít k současné aktualizaci stejné části seznamu.

Termín vzájemné vyloučení se také používá ve vztahu k současnému zápisu adresy paměti jedním vláknem, zatímco s výše uvedenou adresou paměti manipuluje nebo čte jedno nebo více dalších vláken.

Popis problému

Problém, který řeší vzájemné vyloučení, je problém sdílení zdrojů: jak může softwarový systém řídit přístup více procesů ke sdílenému zdroji, když každý proces potřebuje při své práci výhradní kontrolu nad tímto zdrojem? Řešení vzájemného vyloučení tohoto zpřístupní sdílený prostředek pouze v případě, že je proces v konkrétním segmentu kódu, který se nazývá kritická část . Řídí přístup ke sdílenému zdroji tím, že řídí každé vzájemné provádění té části svého programu, kde by byl zdroj použit.

Úspěšné řešení tohoto problému musí mít alespoň tyto dvě vlastnosti:

  • Musí implementovat vzájemné vyloučení : v kritické části může být současně pouze jeden proces.
  • Musí být bez zablokování : pokud se procesy pokoušejí vstoupit do kritické sekce, jeden z nich to nakonec musí být schopen úspěšně, za předpokladu, že žádný proces nezůstane v kritické sekci trvale.

Volnost zablokování lze rozšířit implementací jedné nebo obou těchto vlastností:

  • Lockout-free zaručuje, že jakýkoli proces, který si přeje vstoupit do kritické sekce, to nakonec bude moci udělat. To se liší od vyhýbání se zablokování, které vyžaduje, aby nějaký proces čekání mohl získat přístup do kritické sekce, ale nevyžaduje, aby se každý proces obrátil. Pokud mezi sebou dva procesy nepřetržitě obchodují se zdrojem, třetí proces by mohl být zablokován a došlo by k hladovění zdrojů , přestože systém není ve slepé uličce. Pokud je systém bez výluk, zajišťuje, že se každý proces může v určitém okamžiku v budoucnu obrátit.
  • K ohraničené čekání vlastnost dává přesnější závazek než zablokování volnosti. Lockout-freedom zajišťuje, že se každý proces může nakonec dostat do kritické sekce: neposkytuje žádnou záruku, jak dlouho bude čekat. V praxi by proces mohl předběhnout libovolný nebo neomezený počet opakování jinými procesy s vyšší prioritou, než se dostane na řadu. V rámci vlastnosti čekání vázané na k má každý proces konečnou maximální dobu čekání. Funguje to tak, že nastavíte limit, kolikrát se mohou ostatní procesy zkrátit, takže žádný proces nemůže vstoupit do kritické sekce více než k, zatímco jiný čeká.

Program každého procesu lze rozdělit do čtyř sekcí, což má za následek čtyři stavy. Prováděcí cykly programu prostřednictvím těchto čtyř stavů v uvedeném pořadí:

cyklus sekcí jednoho procesu
Nekritická sekce
Provoz je mimo kritický úsek; proces nepoužívá ani nepožaduje sdílený prostředek.
Zkouší
Proces se pokusí vstoupit do kritické sekce.
Kritická sekce
Procesu je povolen přístup ke sdílenému prostředku v této části.
Výstup
Proces opouští kritickou část a zpřístupňuje sdílený prostředek jiným procesům.

Pokud si proces přeje vstoupit do kritické sekce, musí nejprve spustit testovací sekci a počkat, až získá přístup do kritické sekce. Poté, co proces provede svou kritickou část a dokončí práci se sdílenými prostředky, musí spustit výstupní sekci, aby je uvolnil pro použití jinými procesy. Proces se pak vrátí do nekritické části.

Prosazování vzájemného vyloučení

Hardwarová řešení

V systémech s jedním procesorem je nejjednodušším řešením, jak dosáhnout vzájemného vyloučení, zakázat přerušení během kritické části procesu. Tím se zabrání spuštění jakýchkoli rutin služeb přerušení (což účinně zabrání předvolení procesu ). Přestože je toto řešení efektivní, vede k mnoha problémům. Pokud je kritická sekce dlouhá, systémové hodiny se budou unášet při každém spuštění kritické sekce, protože přerušení časovače již není obsluhováno, takže čas sledování je během kritické sekce nemožný. Také, pokud se proces zastaví během jeho kritické sekce, ovládání se nikdy nevrátí do jiného procesu, čímž se účinně zastaví celý systém. Elegantnější metodou pro dosažení vzájemného vyloučení je zaneprázdněné čekání .

Zaneprázdněné čekání je účinné pro systémy s jedním i více procesory . Vzájemné vyloučení zajišťuje použití sdílené paměti a instrukce atomového testu a nastavení . Proces lze testovat a nastavovat na místě ve sdílené paměti, a protože operace je atomová, příznak může nastavit pouze jeden proces. Jakýkoli proces, který je neúspěšný při nastavování příznaku, může buď pokračovat v dalších úkolech a zkusit to znovu později, uvolnit procesor jinému procesu a zkusit to znovu později, nebo pokračovat ve smyčce a kontrolovat příznak, dokud nebude úspěšný v jeho získání. Předvolba je stále možná, takže tato metoda umožňuje systému nadále fungovat - i když se proces zastaví, zatímco držíte zámek.

K zajištění vzájemného vyloučení datových struktur lze použít několik dalších atomových operací; Nejpozoruhodnější z nich je srovnání a výměna (CAS). CAS lze použít k dosažení vzájemného vyloučení bez čekání pro jakoukoli sdílenou datovou strukturu vytvořením propojeného seznamu, kde každý uzel představuje požadovanou operaci, která má být provedena. CAS se pak používá ke změně ukazatelů v propojeném seznamu během vkládání nového uzlu. Ve svém CAS může být úspěšný pouze jeden proces; všechny ostatní procesy, které se pokoušejí přidat uzel současně, to budou muset zkusit znovu. Každý proces si pak může ponechat lokální kopii datové struktury a při procházení propojeného seznamu může provádět každou operaci ze seznamu na své lokální kopii.

Softwarová řešení

Kromě řešení podporovaných hardwarem existují i ​​některá softwarová řešení, která využívají zaneprázdněné čekání k dosažení vzájemného vyloučení. Mezi příklady patří:

Tyto algoritmy nefungují, pokud je na platformě, která je spouští, použito spuštění mimo pořadí . Programátoři musí určit přísné řazení operací paměti v rámci vlákna.

Často je vhodnější použít synchronizační zařízení poskytovaná vícevláknovou knihovnou operačního systému , která bude využívat výhod hardwarových řešení, pokud je to možné, ale bude používat softwarová řešení, pokud žádná hardwarová řešení neexistují. Když je například použita knihovna zámku operačního systému a vlákno se pokusí získat již získaný zámek, operační systém by mohl vlákno pozastavit pomocí kontextového přepínače a vyměnit ho za jiné vlákno, které je připraveno ke spuštění, nebo by mohlo pokud není k dispozici jiné vlákno, které lze spustit, tento procesor do stavu nízké spotřeby. Většina moderních metod vzájemného vyloučení se proto pokouší snížit čekací dobu a zaneprázdněné čekání pomocí přepínání front a kontextu. Pokud však lze prokázat, že čas strávený pozastavením vlákna a jeho obnovením je vždy delší než čas, který je třeba počkat, než se vlákno stane připraveným ke spuštění poté, co byl v konkrétní situaci zablokován, pak jsou spinlocky přijatelné řešení (pouze pro tuto situaci).

Vázaný na problém vzájemného vyloučení

Jeden binární test a sada registrů je dostatečný k tomu, aby poskytl řešení problému vzájemného vyloučení bez zablokování. Ale řešení postavené na registru test & set může případně vést k vyhladovění některých procesů, které se zachytí ve zkušební sekci. Ve skutečnosti jsou nutné odlišné stavy paměti, aby se zabránilo uzamčení. Aby se zabránilo neomezenému čekání, je zapotřebí n různých stavů paměti.

Obnovitelné vzájemné vyloučení

Většina algoritmů pro vzájemné vyloučení je navržena s předpokladem, že během procesu uvnitř kritické sekce nedojde k žádnému selhání. Ve skutečnosti však mohou být takové poruchy běžné. Například náhlá ztráta napájení nebo vadné propojení může způsobit, že se v procesu v kritické části objeví neopravitelná chyba nebo jinak nebude možné pokračovat. Pokud k takové chybě dojde, konvenční algoritmy vzájemného vyloučení, které netolerují selhání, mohou zablokovat nebo jinak selhat vlastnosti životnosti klíčů. K řešení tohoto problému bylo navrženo několik řešení využívajících mechanismy obnovy po selhání.

Typy zařízení pro vzájemné vyloučení

Výše popsaná řešení lze použít k vytvoření níže uvedených synchronizačních primitiv:

Mnoho forem vzájemného vyloučení má vedlejší účinky. Například klasické semafory umožňují zablokování , ve kterém jeden proces získá semafor, jiný proces druhý semafor a pak oba čekají na vydání druhého semaforu. Mezi další běžné vedlejší efekty patří hladovění , kdy proces nikdy nedostane dostatečné prostředky k dokončení; inverze priority , ve které vlákno s vyšší prioritou čeká na vlákno s nižší prioritou; a vysokou latencí, kdy reakce na přerušení není rychlá.

Většina výzkumu je zaměřena na eliminaci výše uvedených efektů, často s cílem zaručit neblokující pokrok . Není známo dokonalé schéma. Blokování systémových volání slouží k uspání celého procesu. Dokud se taková volání nestala bezpečnou pro vlákna , neexistoval žádný správný mechanismus pro uspání jednoho vlákna v rámci procesu (viz hlasování ).

Viz také

Reference

Další čtení

  • Michel Raynal: Algoritmy pro vzájemné vyloučení , MIT Press, ISBN  0-262-18119-3
  • Sunil R. Das, Pradip K. Srimani: Distribuované algoritmy vzájemného vyloučení , IEEE Computer Society, ISBN  0-8186-3380-8
  • Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing , Prentice Hall, ISBN  0-13-016164-0
  • Gadi Taubenfeld, synchronizační algoritmy a souběžné programování , Pearson/Prentice Hall, ISBN  0-13-197259-6

externí odkazy