Dvojité porovnání a výměna - Double compare-and-swap

Dvojité porovnání a výměna (DCAS nebo CAS2) je atomový primitiv navrhuje podpořit určité souběžné programování techniky. DCAS vezme dvě ne nutně sousedící místa v paměti a zapíše do nich nové hodnoty, pouze pokud odpovídají předem dodaným „očekávaným“ hodnotám; jako takový je rozšířením mnohem populárnějšího porovnat a vyměnit (CAS) operace.

DCAS je někdy zaměňován s dvojitou šířkou porovnávat a vyměňovat (DWCAS) implementováno podle pokynů, jako je x86 CMPXCHG16B. DCAS, jak je zde diskutováno, zpracovává dvě diskontinuální místa v paměti, obvykle velikosti ukazatele, zatímco DWCAS zpracovává dvě sousední místa v paměti velikosti ukazatele.

Michael Greenwald ve své disertační práci doporučil přidat DCAS k modernímu hardwaru a ukázal, že jej lze použít k vytvoření snadno použitelného, ​​ale efektivního softwarová transakční paměť (STM). Greenwald poukazuje na to, že výhodou DCAS vs CAS je ten CAS vyššího řádu (více položek)n lze implementovat v O (n) s DCAS, ale vyžaduje O (n log str) čas s unárním CAS, kde str je počet soupeřících procesů.[1]

Jednou z výhod DCAS je schopnost implementovat atomové deques (tj. dvojnásobně propojené seznamy ) relativně snadno.[2]V poslední době se však ukázalo, že STM lze implementovat se srovnatelnými vlastnostmi[je zapotřebí objasnění ] pouze pomocí CAS.[3] Obecně však DCAS není stříbrná kulka: implementace algoritmy bez zámku a bez čekání jeho použití je obvykle stejně složité a náchylné k chybám jako pro CAS.[4]

Motorola v jednom okamžiku zahrnovala DCAS do instrukční sady pro svůj 68 tis série;[5] pomalost DCAS vzhledem k jiným primitivům (zjevně kvůli problémům s manipulací s mezipamětí) však vedla k jeho vyhýbání v praktických kontextech.[6] Od roku 2015„DCAS není nativně podporován žádným rozšířeným CPU ve výrobě.

Zobecnění DCAS na více než dvě adresy se někdy nazývá MCAS (multi-word CAS); MCAS lze implementovat pomocí nestable LL / SC, ale takový primitiv není přímo k dispozici v hardwaru.[3] MCAS lze implementovat do softwaru z hlediska DCAS různými způsoby.[7] V roce 2013 Trevor Brown, Faith Ellen a Eric Ruppert implementovali do softwaru více adresovou příponu LL / SC (kterou nazývají LLX / SCX), která je sice přísnější než MCAS[8] jim umožnilo prostřednictvím automatického generování kódu implementovat jeden z nejlépe fungujících souběžných systémů binární vyhledávací strom (ve skutečnosti chromatický strom ), mírně porazil JDK Založené na CAS přeskočit seznam implementace.[9]

Obecně lze DCAS poskytnout expresivnějším hardwarem transakční paměť.[10] IBM SÍLA8 a Intel Intel TSX poskytovat pracovní implementace transakční paměti. slunce je zrušen Rockový procesor by to také podpořilo.

Reference

  1. ^ M. Greenwald. "Synchronizace bez blokování a návrh systému". Technická zpráva Stanfordské univerzity STAN-CS-TR-99-1624 [1]. (zejména str. 10)
  2. ^ Ole Agesen, David L. Detlefs, Christine H. Flood, Alexander T. Garthwaite, Paul A. Martin, Mark Moir, Nir N. Shavit a Guy L. Steele Jr. „Souběžné dekády založené na DCAS.“ Theory of Computing Systems 35, č. 3 (2002): 349-386.
  3. ^ A b Keir Fraser (2004), „Praktická svoboda zámku“ UCAM-CL-TR-579.pdf
  4. ^ Simon Doherty a kol., „DCAS není stříbrná kulka pro návrh neblokujícího algoritmu“. 16. ročník sympozia ACM o paralelismu v algoritmech a architekturách, 2004, s. 216–224 [2].
  5. ^ CAS2
  6. ^ Greenwald, Michael a David Cheriton. „Synergie mezi neblokující synchronizací a strukturou operačního systému.“ OSDI '96 Proceedings of the second USENIX symposium on Operating systems design and implementation (1996): 123-136. (zejména část 7.1 „Experimentální implementace“)
  7. ^ Harris, Timothy L .; Fraser, Keir; Pratt, Ian A. (2002). Praktická víceslovná operace srovnávání a výměny. Proc. Int'l Symp. Distribuované výpočty. CiteSeerX  10.1.1.13.7938.
  8. ^ Trevor Brown, Faith Ellen a Eric Ruppert. „Pragmatická primitiva pro neblokující datové struktury.“ In Proceedings of the ACM symposium 2013 on Principles of distributed computing, pp. 13-22. ACM, 2013.
  9. ^ Trevor Brown, Faith Ellen a Eric Ruppert. „Obecná technika pro neblokující stromy.“ V Sborníku 19. sympozia ACM SIGPLAN o zásadách a praxi paralelního programování, s. 329-342. ACM, 2014.
  10. ^ Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum a Marek Olszewski. (2009) „První zkušenosti s implementací komerční hardwarové transakční paměti.“ Technická zpráva společnosti Sun Microsystems (60 stran) SMLI TR-2009-180. Krátká verze se objevila na ASPLOS’09 doi:10.1145/1508244.1508263. Celá zpráva pojednává o tom, jak implementovat DCAS pomocí HTM v části 5.

externí odkazy