Compare and Swap (CAS)

CAS is a technique used to obtain synchronization during multiple writes where each write value depends upon the current state of the shared variable.

It basically means that a variable will first be compared with a value to see if it has changed.

If it has changed, then it means its value has been updated by some other thread and hence swap is not possible. In such a case, current value of the shared variable is obtained and new value is calculated from it.

If it has not changed, then it means that its value has not been modified by any other thread and so it can be swapped.

Coding-wise, it can be implemented as follows:

The whole compare and swap operation is an atomic one (that’s why synchronized keyword is used) guaranteeing that swap by one thread does not concurrently happen during swap by another thread (if both discovered that the variable’s value had not changed and both try to update).

If a thread is able to successfully swap, it proceeds, else it has to retry.

The above suffers from ABA problem (means value becomes A again after becoming B for a short while, hence the name ABA). If value becomes A again after becoming B, then the thread has no means of knowing that the value was indeed changed between. For some threads it may not be an issue but for others it may be. To break this, double-length CAS is used. DL-CAS uses a counter which is incremented with each swap and compares both counter and the variable to check for change. Hence even if the value becomes same after several changes, the counter value would have increased and the compare would fail.

CAS based algorithms are called lock-free, because threads do not ever have to wait for a lock (sometimes called a mutex or critical section, depending on the terminology of your threading platform). Either the CAS operation succeeds or it doesn't, but in either case, it completes in a predictable amount of time. If the CAS fails, the caller can retry the CAS operation or take other action as it sees fit.

For example, a lock-free counter can be implemented as follows:

(This approach guarantees that every call to increment will increment the counter and not fall prey to two threads reading same value, incrementing to same value and then writing the same value resulting in a total increment of 1 even though increment() was called twice)

So, in summary, CAS has one benefit - “It avoids thread locking thus eliminating the whole OS infrastructure of waiting and notification. This also avoids deadlock situations. Downside is that the CAS function has to be called several times to complete the operation but that is very lightweight as compared to thread waiting/notification.”

This single benefit has shown to increase throughput of multithreaded programs by a significant amount.

The atomic variable classes in Java 5 all expose a compare-and-set primitive (similar to compare-and-swap), which is implemented using the fastest native construct available on the platform (compare-and-swap, load linked/store conditional, or, in the worst case, spin locks). Nine flavors of atomic variables are provided in the java.util.concurrent.atomic package (AtomicInteger; AtomicLong; AtomicReference; AtomicBoolean; array forms of atomic integer; long; reference; and atomic marked reference and stamped reference classes, which atomically update a pair of values).

Nearly all the classes in the java.util.concurrent package use atomic variables instead of synchronization, either directly or indirectly