Menu
CAS belongs to the read-modify-write (RMW) family, a set of algorithms that allow you to perform complex transactions atomically.
Specifically, Wikipedia says that
CAS is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms. [...] CAS can implement more of these algorithms than atomic read, write, or fetch-and-add, and assuming a fairly large amount of memory, [...] it can implement all of them.
https://en.wikipedia.org/wiki/Compare-and-swap#Overview
So it seems that a CAS algorithm is the "one size fits all" product of its category. Why is that so? What do other RMW algorithms lack of? If CAS is the best tool, what are the other algorithms for?
454
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of that memory location to a new given value.
The compare-and-swap (CAS) instruction is an uninterruptible instruction that reads a memory location, compares the read value with an expected value, and stores a new value in the memory location when the read value matches the expected value. Otherwise, nothing is done.
> CAS is "lock free" only in the sense that it doesn't require the processor to stop the world in order to flip the mutex boolean.
In this paper, we propose a new lightweight locking technique: CAS-Lock (cascaded locking) which nullifies both SAT and bypass attacks, while simultaneously maintaining nontrivial output corruptibility.
CAS belongs to a class of objects called "consensus objects", each of which has a consensus number; the maximum number of threads for which a given consensus object can solve the consensus problem.
The consensus problem goes like this: for some number of threads n, propose some value p and decide on one of the proposed values d such that n threads agrees on d.
CAS is the most "powerful" consensus object because its consensus number is infinite. That is, CAS can be used to solve the consensus problem among a theoretically infinite number of threads. It even does it in a wait-free manner.
This can't be done with atomic registers, test-and-set, fetch-add, stacks since they all have finite consensus numbers. There are proofs for these consensus numbers but that is another story...
The significance of all of this is that it can be proven that there exists a wait-free implementation of an object for n threads using a consensus object with a consensus number of at least n. CAS is especially powerful because you can use it to implement wait-free objects for an arbitrary number of threads.
As to why other RMW operations are useful? Some problems in multiprocessing don't really involve solving the consensus problem for some arbitrary number of threads. For example, mutual exclusion can be solved using less powerful RMW operations like test-and-set (a simple TAS lock), fetch-add (ticket lock) or atomic swap (CLH lock).
More information on consensus for shared memory at Wikipedia Consensus (computer_science) section: In_shared-memory_systems
Also, there's a whole chapter on consensus and universal constructions in Herlihy and Shavit's The Art of Multiprocessor Programming (WorldCat) that I highly recommend.
86
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
