- Double Compare And Swap
Double Compare And Swap (DCAS or CAS2) is an
atomic primitive proposed to support certainconcurrent programming techniques. DCAS takes two memory locations and writes new values into them only if they match pre-supplied "expected" values; as such, it is an extension ofcompare-and-swap (CAS).In his doctoral thesis, Greenwald recommended adding DCAS to modern hardware, showing it could be used to create easy-to-apply yet efficient
software transactional memory (STM). More recently, however, it has been shown that an STM can be implemented with comparable properties using only CAS.The major advantage of DCAS is the ability to implement atomic
deque s (i.e.doubly-linked list s) [ [http://www.google.com/search?q=cache:7LkV4ABc5b0J:research.sun.com/scalable/Papers/TCS02.pdf ] ] .DCAS is no
silver bullet : implementinglock-free and wait-free algorithms using it is typically just as complex and error-prone as for CAS. As such, it seems unlikely that DCAS will ever be supported natively on any modern platform. Indeed,as of 2006 , it's not supported by any widespread CPUs. For a while Motorola included it in the instruction set for its68k series [ [http://68k.hax.com/CAS2 CAS2] ] ; however its relative slowness [ [http://www-dsg.stanford.edu/papers/non-blocking-osdi/node15.html Experimental Implementation] ] led to programmer apathy. It is no longer included in the instruction set. CAS remains popular.Sun's new
Rock processor (shipping second half 2009) which supports hardware scouts and best effort hardware transactional memory also supports DCAS, which they claim provides algorithmic power [(Mark Moir) [http://blogs.sun.com/HPC/entry/video_transactional_memory_on_rock Sun HPC Watercooler] ] .References
* M. Greenwald. "Non-Blocking Synchronization and System Design". Stanford University Technical Report STAN-CS-TR-99-1624 [http://elib.stanford.edu/TR/STAN:CS-TR-99-1624] .Dead link|date=September 2008
* "DCAS is not a silver bullet for nonblocking algorithm design". 16th annual ACM symposium on Parallelism in algorithms and architectures, 2004, pp. 216–224 [http://portal.acm.org/citation.cfm?id=1007945] .External links
* [http://www.osdata.com/topic/language/asm/coproc.htm Multiprocessor and Coprocessor Instructions in Assembly Language]
* [http://freepatentsonline.com/4584640.html US Patent 4584640 "Method and apparatus for a compare and swap instruction"]
Wikimedia Foundation. 2010.