Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Double Compare And Swap
From Wikipedia, the free encyclopedia
Double Compare And Swap (DCAS or CAS2) is an atomic primitive proposed to support certain concurrent 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 of compare-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. 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 deques (i.e. doubly-linked lists)[1].
DCAS is no silver bullet: implementing lock-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 its 68k series[2], however its relative slowness[3] led to programmer apathy. It is no longer included in the instruction set. CAS remains popular.
- M. Greenwald. "Non-Blocking Synchronization and System Design". Stanford University Technical Report STAN-CS-TR-99-1624 [4].
- "DCAS is not a silver bullet for nonblocking algorithm design". 16th annual ACM symposium on Parallelism in algorithms and architectures, 2004, pp. 216 - 224 [5].
- http://www.osdata.com/topic/language/asm/coproc.htm
- US Patent 4584640 Method and apparatus for a compare and swap instruction
 |
This computer-related article is a stub. You can help Wikipedia by expanding it. |