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.

(Note that DCAS Double Compare and Swap is sometimes confused with the double-width compare-and-swap implemented by instructions such as x86 CMPXCHG16B. The double compare and swap discussed here handles two discontiguous memory locations, typically of pointer size, whereas the double-width compare-and-swap handles two adjacent pointer sized memory locations, e.g. CMPXCHG16B on a machine with 8B pointers, or CMPXCHG8B on a machine with 4B pointers.)

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.^{[citation needed]}

One of the advantages of DCAS is the ability to implement atomic deques (i.e. doubly linked lists).^[1]. 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. As such, it seems unlikely that DCAS will ever be supported natively on any modern platform. Indeed, as of 2006^[update], it is not supported by any widespread CPUs.

Motorola at one point included DCAS 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, but CAS remains popular.

Sun's cancelled Rock processor would have supported DCAS, which they claimed provides algorithmic power^[4].

References

1. ^ [1]
2. ^ CAS2
3. ^ Experimental Implementation
4. ^ (Mark Moir) Sun HPC Watercooler

• M. Greenwald. "Non-Blocking Synchronization and System Design". Stanford University Technical Report STAN-CS-TR-99-1624 [2].
• "DCAS is not a silver bullet for nonblocking algorithm design". 16th annual ACM symposium on Parallelism in algorithms and architectures, 2004, pp. 216–224 [3].

External links

• Multiprocessor and Coprocessor Instructions in Assembly Language
• US Patent 4584640 Method and apparatus for a compare and swap instruction