Editing Compare-and-swap (section)

==Extensions==
Since CAS operates on a single [[pointer (computer programming)|pointer]]-sized memory location, while most [[lock-free and wait-free algorithms]] need to modify multiple locations, several extensions have been implemented.

; [[Double compare-and-swap]] (DCAS): Compares two unrelated memory locations with two expected values, and if they're equal, sets both locations to new values. The generalization of DCAS to multiple (non-adjacent) words is called MCAS or CASN. DCAS and MCAS are of practical interest in the convenient (concurrent) implementation of some data structures like [[deque]]s or [[binary search tree]]s.<ref>Simon Doherty et al., "[http://people.csail.mit.edu/shanir/publications/DCAS.pdf 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. {{doi|10.1145/1007912.1007945}}</ref><ref name="Fraser2004">Keir Fraser (2004), "Practical lock-freedom" [https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf UCAM-CL-TR-579.pdf]</ref> DCAS and MCAS may be implemented however using the 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> present in some recent processors such as IBM [[POWER8]] or in Intel processors supporting [[Transactional Synchronization Extensions]] (TSX).
; Double-wide compare-and-swap: Operates on two adjacent pointer-sized locations (or, equivalently, one location twice as big as a pointer). On later x86 processors, the CMPXCHG8B and CMPXCHG16B instructions<ref>{{cite web |title=Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M |url=http://www.intel.com/Assets/en_US/PDF/manual/253666.pdf |accessdate=2007-12-15}}</ref> serve this role, although early 64-bit AMD CPUs did not support CMPXCHG16B  (modern AMD CPUs do). Some Intel motherboards from the [[Core 2]] era also hamper its use, even though the processors support it. These issues came into the spotlight at the launch of [[Windows 8.1]] because it required hardware support for CMPXCHG16B.<ref>{{Cite news |last=Chacos |first=Brad |date=October 29, 2013 |title=New Windows 8.1 requirements strand some users on Windows 8 |url=https://www.pcworld.com/article/448350/new-windows-8-1-requirements-strand-some-users-on-windows-8.html |url-status=live |archive-url=https://web.archive.org/web/20240116164612/https://www.pcworld.com/article/448350/new-windows-8-1-requirements-strand-some-users-on-windows-8.html |archive-date=January 16, 2024 |work=[[PC World]]}}</ref>
; Single compare, double swap: Compares one pointer but writes two. The Itanium's cmp8xchg16 instruction implements this,<ref>{{cite web |title=Intel Itanium Architecture Software Developer's Manual Volume 3: Instruction Set Reference |url=http://download.intel.com/design/Itanium/manuals/24531905.pdf |accessdate=2007-12-15}}</ref> where the two written pointers are adjacent.
; Multi-word compare-and-swap: Is a generalisation of normal compare-and-swap. It can be used to atomically swap an arbitrary number of arbitrarily located memory locations. Usually, multi-word compare-and-swap is implemented in software using normal double-wide compare-and-swap operations.<ref>{{cite web |title=A Practical Multi-Word Compare-and-Swap Operation |url=https://www.cl.cam.ac.uk/research/srg/netos/papers/2002-casn.pdf |accessdate=2009-08-08}}</ref>  The drawback of this approach is a lack of scalability.
; Persistent compare-and-swap: Is a combination of persist operation and the normal compare-and-swap. It can be used to atomically compare-and-swap a value and then persist the value, so there is no gap between concurrent visibility and crash visibility. The extension solves the [[Persistent memory#The_read-of-non-persistent-write_problem|read-of-non-persistent-write problem]].<ref>{{Cite book|chapter-url=https://doi.org/10.1145/3323165.3323166|chapter=Persistent Atomics for Implementing Durable Lock-Free Data Structures for Non-Volatile Memory (Brief Announcement)|first1=William|last1=Wang|first2=Stephan|last2=Diestelhorst|title=The 31st ACM Symposium on Parallelism in Algorithms and Architectures|date=June 17, 2019|publisher=Association for Computing Machinery|pages=309–311|via=ACM Digital Library|doi=10.1145/3323165.3323166|isbn=9781450361842|s2cid=195064876}}</ref>