View source for Double compare-and-swap

'''Double compare-and-swap''' ('''DCAS''' or '''CAS2''') is an [[atomic primitive]] proposed to support certain [[concurrent programming]] techniques. DCAS takes two not necessarily contiguous memory locations and writes new values into them only if they match pre-supplied "expected" values; as such, it is an extension of the much more popular [[compare-and-swap]] (CAS) operation.

DCAS is sometimes confused with the double-width compare-and-swap ('''DWCAS''') implemented by instructions such as x86 CMPXCHG16B. DCAS, as discussed here, handles two discontiguous memory locations, typically of pointer size, whereas DWCAS handles two adjacent pointer-sized memory locations.

In his doctoral thesis, Michael Greenwald recommended adding DCAS to modern hardware, showing it could be used to create easy-to-apply yet efficient [[software transactional memory]] (STM). Greenwald points out that an advantage of DCAS vs CAS is that higher-order (multiple item) CAS''n'' can be implemented in O(''n'') with DCAS, but requires O(''n'' log ''p'') time with unary CAS, where ''p'' is the number of contending processes.<ref>M. Greenwald. "Non-Blocking Synchronization and System Design". Stanford University Technical Report STAN-CS-TR-99-1624 [http://infolab.stanford.edu/TR/CS-TR-99-1624.html]. (p. 10 in particular)</ref>

One of the advantages of DCAS is the ability to implement atomic [[deque]]s (i.e. [[doubly linked list]]s) with relative ease.<ref>Ole Agesen, David L. Detlefs, Christine H. Flood, Alexander T. Garthwaite, Paul A. Martin, Mark Moir, Nir N. Shavit, and Guy L. Steele Jr. "DCAS-Based Concurrent Deques." Theory of Computing Systems 35, no. 3 (2002): 349-386.</ref>
More recently, however, it has been shown that an STM can be implemented with comparable properties{{clarify|date=February 2015}} using only CAS.<ref name="Fraser2004">Keir Fraser (2004), "Practical lock-freedom" [http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf UCAM-CL-TR-579.pdf]</ref> In general however, DCAS is not a [[silver bullet]]: implementing [[lock-free and wait-free algorithms]] using it is typically just as complex and error-prone as for CAS.<ref>Simon Doherty et al., "DCAS is not a silver bullet for nonblocking algorithm design". 16th annual ACM symposium on Parallelism in algorithms and architectures, 2004, pp.&nbsp;216–224  [http://portal.acm.org/citation.cfm?id=1007945].</ref>

Motorola at one point included DCAS in the instruction set for its [[68k]] series;<ref>[http://68k.hax.com/CAS2 CAS2]</ref> however, the slowness of DCAS relative to other primitives (apparently due to cache handling issues) led to its avoidance in practical contexts.<ref>Greenwald, Michael, and David Cheriton. "The synergy between non-blocking synchronization and operating system structure." OSDI '96 Proceedings of the second USENIX symposium on Operating systems design and implementation (1996): 123-136. (particularly section 7.1 "Experimental Implementation")</ref> {{Asof|2015}}, DCAS is not natively supported by any widespread CPUs in production.

The generalization of DCAS to more than two addresses is sometimes called MCAS (multi-word CAS); MCAS can be implemented by a nestable [[LL/SC]], but such a primitive is not directly available in hardware.<ref name="Fraser2004"/> MCAS can be implemented in software in terms of DCAS, in various ways.<ref>{{cite conference |citeseerx=10.1.1.13.7938 |title=A Practical Multi-Word Compare-And-Swap Operation |first1= Timothy L. |last1=Harris |first2= Keir |last2=Fraser |first3=Ian A. |last3=Pratt |year=2002 |conference=Proc. Int'l Symp. Distributed Computing}}</ref> In 2013, Trevor Brown, [[Faith Ellen]], and Eric Ruppert have implemented in software a multi-address LL/SC extension (which they call LLX/SCX) that while being more restrictive than MCAS<ref>Trevor Brown, Faith Ellen, and Eric Ruppert. "Pragmatic primitives for non-blocking data structures." In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pp. 13-22. ACM, 2013.</ref> enabled them, via some automated code generation, to implement one of the best performing concurrent [[binary search tree]] (actually a [[chromatic tree]]), slightly beating the [[JDK]] CAS-based [[skip list]] implementation.<ref>Trevor Brown, Faith Ellen, and Eric Ruppert. "A general technique for non-blocking trees." In Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 329-342. ACM, 2014.</ref>

In general, DCAS can be provided by a more expressive hardware [[transactional memory]].<ref>Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum, and Marek Olszewski. (2009) "Early experience with a commercial hardware transactional memory implementation." Sun Microsystems technical report (60 pp.) SMLI TR-2009-180. A short version appeared at ASPLOS’09 {{doi|10.1145/1508244.1508263}}. The full-length report discusses how to implement DCAS using HTM in section 5.</ref> IBM [[POWER8]] and Intel [[Intel TSX]] provide working implementations of transactional memory. [[Sun Microsystems|Sun]]'s cancelled [[Rock processor]] would have supported it as well.

== References ==
<references />

==External links==
* [http://freepatentsonline.com/4584640.html US Patent 4584640 ''Method and apparatus for a compare and swap instruction'']

[[Category:Concurrency control]]