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.
Sun's new Rock processor (shipping 2nd half 2009) which supports hardware scouts and best effort hardware transactional memory does also support DCAS which they claim provides algorithmic power (Mark Moir)[4].
[edit] References
- M. Greenwald. "Non-Blocking Synchronization and System Design". Stanford University Technical Report STAN-CS-TR-99-1624 [5].
- "DCAS is not a silver bullet for nonblocking algorithm design". 16th annual ACM symposium on Parallelism in algorithms and architectures, 2004, pp. 216 - 224 [6].
