Neblokující algoritmus - Non-blocking algorithm

Nesmí být zaměňována s Neblokující I / O.

v počítačová věda, an algoritmus je nazýván neblokující pokud selhání nebo suspenze ze všech vlákno nemůže způsobit poruchu nebo pozastavení jiného vlákna;[1] pro některé operace poskytují tyto algoritmy užitečnou alternativu k tradičním blokování implementací. Neblokující algoritmus je bez zámku pokud je zaručen celý systém pokrok, a bez čekání pokud je také zaručen postup podle vlákna. „Neblokování“ bylo v literatuře používáno jako synonymum „bez zámku“ až do zavedení svobody v obstrukci v roce 2003.[2]

Slovo „neblokující“ bylo tradičně používáno k popisu telekomunikační sítě které by mohly směrovat spojení přes sadu relé „bez nutnosti znovu uspořádat stávající hovory“, viz Clos síť. Také pokud telefonní ústředna „není vadná, může se vždy připojit“, viz neblokující přepínač minimálního rozsahu.

Motivace

Hlavní článek: Nevýhody zámků

Tradiční přístup k vícevláknovému programování je použití zámky synchronizovat přístup ke sdílenému zdroje. Synchronizační primitiva, jako je mutexy, semafory, a kritické sekce jsou všechny mechanismy, kterými může programátor zajistit, aby se určité části kódu nespouštěly souběžně, pokud by to poškodilo struktury sdílené paměti. Pokud se jedno vlákno pokusí získat zámek, který je již držen jiným vláknem, vlákno se zablokuje, dokud není zámek volný.

Blokování vlákna může být nežádoucí z mnoha důvodů. Zjevným důvodem je, že zatímco vlákno je blokováno, nemůže nic dosáhnout: pokud blokované vlákno provádělo vysokou prioritu nebo reálný čas zastavit jeho postup by bylo velmi nežádoucí.

Jiné problémy jsou méně zřejmé. Například určité interakce mezi zámky mohou vést k chybovým podmínkám, jako je zablokování, živý zámek, a prioritní inverze. Použití zámků také zahrnuje kompromis mezi hrubozrnným zamykáním, což může významně omezit příležitosti rovnoběžnost a jemnozrnné zamykání, které vyžaduje pečlivější design, zvyšuje režii zamykání a je náchylnější k chybám.

Na rozdíl od blokovacích algoritmů neblokující algoritmy těmito nevýhodami netrpí a navíc jsou bezpečné pro použití v obsluhy přerušení: i když preempted vlákno nelze obnovit, pokrok je stále možný bez něj. Naproti tomu ke globálním datovým strukturám chráněným vzájemným vyloučením nelze bezpečně přistupovat v obslužném programu přerušení, protože preempovaným vláknem může být ten, který drží zámek - ale to lze snadno napravit maskováním požadavku na přerušení během kritické sekce.[3]

K vylepšení výkonu lze použít bezzámkovou datovou strukturu. Bezzámková datová struktura zvyšuje čas strávený paralelním prováděním spíše než sériovým prováděním, což zvyšuje výkon na vícejádrový procesor, protože přístup ke sdílené datové struktuře není nutné serializovat, aby zůstal koherentní.[4]

Implementace

Až na několik výjimek se používají neblokující algoritmy atomový read-modify-write primitiva, která hardware musí poskytovat, z nichž nejpozoruhodnější je porovnat a vyměnit (CAS). Kritické sekce jsou téměř vždy implementovány pomocí standardních rozhraní nad těmito primitivy (v obecném případě budou kritické sekce blokovány, i když jsou implementovány s těmito primitivy). Donedávna musely být všechny neblokující algoritmy psány „nativně“ s podkladovými primitivy, aby se dosáhlo přijatelného výkonu. Avšak rozvíjející se pole softwarová transakční paměť slibuje standardní abstrakce pro psaní efektivního neblokujícího kódu.[5][6]

Hodně výzkumu bylo také provedeno v poskytování základních datové struktury jako hromádky, fronty, sady, a hash tabulky. Ty umožňují programům snadnou asynchronní výměnu dat mezi vlákny.

Některé neblokující datové struktury jsou navíc dostatečně slabé na to, aby mohly být implementovány bez speciálních atomových primitiv. Mezi tyto výjimky patří:

  • single-reader single-writer ring buffer FIFO, s velikostí, která rovnoměrně rozděluje přetečení jednoho z dostupných celočíselných typů bez znaménka, může být bezpodmínečně implementováno bezpečně pouze pomocí paměťové bariéry
  • Číst-kopírovat-aktualizovat s jedním spisovatelem a libovolným počtem čtenářů. (Čtečky jsou bez čekání; zapisovač je obvykle bez zámku, dokud nepotřebuje získat paměť).
  • Číst-kopírovat-aktualizovat s více autory a libovolným počtem čtenářů. (Čtečky jsou bez čekání; více spisovatelů obvykle serializuje se zámkem a není bez překážek).

Několik knihoven interně používá bezblokové techniky,[7][8][9] ale je obtížné napsat správný kód bez zámku.[10][11][12][13]

Čekejte svobodu

Svoboda čekání je nejsilnější neblokující zárukou pokroku kombinující zaručenou propustnost celého systému s hladovění -svoboda. Algoritmus je bez čekání, pokud má každá operace omezený počet kroků, které algoritmus provede před dokončením operace.[14]Tato vlastnost je zásadní pro systémy v reálném čase a je vždy příjemné ji mít, pokud náklady na výkon nejsou příliš vysoké.

Ukázalo se to v 80. letech[15] že všechny algoritmy lze implementovat bez čekání a lze volat mnoho transformací ze sériového kódu univerzální konstrukce, byly prokázány. Výsledný výkon však obecně neodpovídá ani naivním blokovacím vzorům. Několik článků od té doby zlepšilo výkon univerzálních konstrukcí, ale přesto je jejich výkon hluboko pod blokujícími návrhy.

Několik článků zkoumalo obtížnost vytváření algoritmů bez čekání. Například to bylo ukázáno[16] že široce dostupný atom podmiňovací způsob primitiva, CAS a LL / SC, nemůže poskytovat implementace mnoha běžných datových struktur bez hladovění, aniž by lineárně rostly náklady na paměť v počtu vláken.

V praxi však tyto dolní hranice nepředstavují skutečnou překážku, protože utrácení řádku mezipaměti nebo výhradní rezervační granule (až 2 kB na ARM) úložiště na vlákno ve sdílené paměti se pro praktické systémy nepovažuje za příliš nákladné (obvykle množství logicky vyžadované úložiště je slovo, ale fyzicky se CAS operace na stejném řádku mezipaměti srazí a operace LL / SC ve stejné výhradní rezervaci granule se srazí, takže množství úložiště fyzicky vyžadováno[Citace je zapotřebí ] je lepší).

Algoritmy bez čekání byly do roku 2011 vzácné, a to jak ve výzkumu, tak v praxi. V roce 2011 však Kogan a Petranku[17] představil frontu bez čekání na CAS primitivní, obecně dostupné na běžném hardwaru. Jejich konstrukce rozšířila frontu Michael a Scott bez zámků,[18] což je efektivní fronta často používaná v praxi. Navazující práce Kogana a Petranku[19] poskytl metodu pro rychlé zrychlení bez čekání a použil tuto metodu k tomu, aby byla fronta bez čekání prakticky tak rychlá jako její protějšek bez zámků. Následující příspěvek Timnat a Petranku[20] poskytl automatický mechanismus pro generování datových struktur bez čekání z těch bez zámků. Implementace bez čekání jsou nyní k dispozici pro mnoho datových struktur.

Svoboda zámku

Svoboda zámku umožňuje hladovění jednotlivých vláken, ale zaručuje propustnost celého systému. Algoritmus je bez zámku, pokud při dostatečně dlouhém běhu podprocesů programu alespoň jedno z podprocesů dosáhne pokroku (pro nějakou rozumnou definici průběhu). Všechny algoritmy bez čekání jsou bez zámků.

Zejména pokud je jedno vlákno pozastaveno, pak algoritmus bez zámku zaručuje, že zbývající vlákna mohou stále dělat pokrok. Pokud tedy mohou dvě vlákna bojovat o stejný zámek mutex nebo spinlock, pak algoritmus je ne bez zámku. (Pokud pozastavíme jedno vlákno, které drží zámek, druhé vlákno se zablokuje.)

Algoritmus je bez zámku, pokud nekonečně často operace některých procesorů uspěje v konečném počtu kroků. Například pokud se N procesory pokoušejí provést operaci, některé z N procesů uspějí v dokončení operace v konečném počtu kroků a další mohou selhat a zkusit to znovu. Rozdíl mezi bez čekání a bez zámku je v tom, že je zaručeno, že operace bez čekání u každého procesu uspějí v konečném počtu kroků bez ohledu na ostatní procesory.

Obecně platí, že bezblokovací algoritmus může běžet ve čtyřech fázích: dokončení vlastní operace, pomoc při překážející operaci, přerušení překážkové operace a čekání. Dokončení vlastní operace je komplikováno možností souběžné pomoci a potratu, ale vždy je nejrychlejší cestou k dokončení.

Rozhodnutí o tom, kdy pomoci, potratit nebo počkat, až dojde k překážce, je odpovědností a správce sporu. To může být velmi jednoduché (asistovat operacím s vyšší prioritou, zrušit operace s nižší prioritou), nebo může být optimalizováno pro dosažení lepší propustnosti nebo snížit latenci prioritních operací.

Správná souběžná pomoc je obvykle nejsložitější částí bezblokového algoritmu a její provedení je často velmi nákladné: asistující vlákno se nejen zpomalí, ale díky mechanice sdílené paměti se zpomalí také vlákno, kterému je asistována. , pokud stále běží.

Svoboda překážek

Svoboda překážek je nejslabší přirozenou neblokující zárukou pokroku. Algoritmus je bez překážek, pokud v kterémkoli okamžiku dokončí svou operaci jedno vlákno provedené izolovaně (tj. Se všemi zablokovanými vlákny pozastavenými) pro omezený počet kroků.[14] Všechny algoritmy bez zámku jsou bez překážek.

Svoboda překážek vyžaduje pouze to, aby bylo možné zrušit jakoukoli částečně dokončenou operaci a vrátit provedené změny. Zrušení souběžné pomoci může často vést k mnohem jednodušším algoritmům, které lze snáze ověřit. Zabránění nepřetržitému fungování systému živé zamykání je úkolem správce sporu.

Některé algoritmy bez překážek používají v datové struktuře dvojici „značek konzistence“. Procesy načtení datové struktury nejprve načtou jeden marker konzistence, poté načtou relevantní data do interní vyrovnávací paměti, poté načtou druhý marker a poté porovnají markery. Data jsou konzistentní, pokud jsou oba markery identické. Značky mohou být neidentické, když je čtení přerušeno jiným procesem aktualizujícím datovou strukturu. V takovém případě proces zahodí data ve vnitřní vyrovnávací paměti a pokusí se znovu.

Viz také

Reference

  1. ^ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Souběžnost Java v praxi. Upper Saddle River, NJ: Addison-Wesley. p.41. ISBN  9780321349606.
  2. ^ Herlihy, M .; Luchangco, V .; Moir, M. (2003). Synchronizace bez překážek: Oboustranné fronty jako příklad (PDF). 23 Mezinárodní konference o distribuovaných výpočetních systémech. p. 522.
  3. ^ Butler W. Lampson; David D. Redell (Únor 1980). „Zkušenosti s procesy a monitory v Mesa“. Komunikace ACM. 23 (2): 105–117. CiteSeerX  10.1.1.142.5765. doi:10.1145/358818.358824.
  4. ^ Guillaume Marçais a Carl Kingsford.„Rychlý přístup bez zámku pro efektivní paralelní počítání výskytů k-merů“.Bioinformatics (2011) 27 (6): 764-770.doi:10.1093 / bioinformatika / btr011„Počítadlo medúzy“.
  5. ^ Harris, Tim; Fraser, Keir (26. listopadu 2003). „Jazyková podpora pro nenáročné transakce“ (PDF). Oznámení ACM SIGPLAN. 38 (11): 388. CiteSeerX  10.1.1.58.8466. doi:10.1145/949343.949340.
  6. ^ Harris, Tim; Marlow, S .; Peyton-Jones, S .; Herlihy, M. (15. – 17. Června 2005). Msgstr "Transakce s komponovatelnou pamětí". Sborník sympozia ACM SIGPLAN z roku 2005 o zásadách a praxi paralelního programování, PPoPP '05: Chicago, Illinois. New York, NY: ACM Press. str. 48–60. doi:10.1145/1065944.1065952. ISBN  978-1-59593-080-4.
  7. ^ libcds - C ++ knihovna bezzámkových kontejnerů a bezpečné schéma rekultivace paměti
  8. ^ liblfds - Knihovna datových struktur bez zámku, napsaná v jazyce C.
  9. ^ Souběžná souprava - Knihovna C pro návrh a implementaci neblokujícího systému
  10. ^ Herb Sutter. „Kód bez zámku: falešný smysl pro bezpečnost“. Archivovány od originál dne 01.09.2015.
  11. ^ Herb Sutter. „Psaní kódu bez zámku: opravená fronta“. Archivovány od originál dne 2008-12-05.
  12. ^ Herb Sutter. „Psaní generalizované souběžné fronty“.
  13. ^ Herb Sutter. „Potíže se zámky“.
  14. ^ A b Anthony Williams.„Bezpečnost: vypnuto: Jak si nezastřelit nohu pomocí atomů C ++“.2015.p. 20.
  15. ^ Herlihy, Maurice P. (1988). Výsledky nemožnosti a univerzálnosti synchronizace bez čekání. Proc. 7. výroční ACM Symp. o zásadách distribuovaného výpočtu. 276–290. doi:10.1145/62546.62593. ISBN  0-89791-277-2.
  16. ^ Fich, Faith; Hendler, Danny; Shavit, Nir (2004). O inherentní slabosti primitivů podmíněné synchronizace. Proc. 23. výroční ACM Symp.on Principles of Distributed Computing (PODC). str. 80–87. doi:10.1145/1011767.1011780. ISBN  1-58113-802-4.
  17. ^ Kogan, Alex; Petrank, Erez (2011). Fronty bez čekání s více enqueuery a dequeuery (PDF). Proc. 16. ACM SIGPLAN Symp. o zásadách a praxi paralelního programování (PPOPP). str. 223–234. doi:10.1145/1941553.1941585. ISBN  978-1-4503-0119-0.
  18. ^ Michael, Maged; Scott, Michael (1996). Jednoduché, rychlé a praktické neblokující a blokující souběžné algoritmy fronty. Proc. 15. výroční ACM Symp. o zásadách distribuovaného výpočtu (PODC). 267–275. doi:10.1145/248052.248106. ISBN  0-89791-800-2.
  19. ^ Kogan, Alex; Petrank, Erez (2012). Metoda pro vytváření rychlých datových struktur bez čekání. Proc. 17. ACM SIGPLAN Symp. o zásadách a praxi paralelního programování (PPOPP). 141–150. doi:10.1145/2145816.2145835. ISBN  978-1-4503-1160-1.
  20. ^ Timnat, Shahar; Petrank, Erez (2014). Praktická simulace bez čekání pro datové struktury bez zámku. Proc. 17. ACM SIGPLAN Symp. o zásadách a praxi paralelního programování (PPOPP). str. 357–368. doi:10.1145/2692916.2555261. ISBN  978-1-4503-2656-8.

externí odkazy