Java Compare and Swap Example – CAS Algorithm

One of the best additions in java 5 was Atomic operations supported in classes such as AtomicInteger, AtomicLong etc. These classes help you in minimizing the need of complex (un-necessary) multi-threading code for some basic operations such as increment or decrement a value which is shared among multiple threads. These classes internally rely on an algorithm named CAS (compare and swap). In this article, I am going to discuss this concept in detail.

1. Optimistic and Pessimistic Locking

Traditional locking mechanisms, e.g. using synchronized keyword in java, is said to be pessimistic technique of locking or multi-threading. It asks you to first guarantee that no other thread will interfere in between certain operation (i.e. lock the object), and then only allow you access to any instance/method.

It’s much like saying “please close the door first; otherwise some other crook will come in and rearrange your stuff”.

Though above approach is safe and it does work, but it put a significant penalty on your application in terms of performance. Reason is simple that waiting threads can not do anything unless they also get a chance and perform the guarded operation.

There exist one more approach which is more efficient in performance, and it optimistic in nature. In this approach, you proceed with an update, being hopeful that you can complete it without interference. This approach relies on collision detection to determine if there has been interference from other parties during the update, in which case the operation fails and can be retried (or not).

The optimistic approach is like the old saying, “It is easier to obtain forgiveness than permission”, where “easier” here means “more efficient”.

Compare and Swap is a good example of such optimistic approach, which we are going to discuss next.

2. Compare and Swap Algorithm

This algorithm compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value. This is done as a single atomic operation. The atomicity guarantees that the new value is calculated based on up-to-date information; if the value had been updated by another thread in the meantime, the write would fail. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple Boolean response (this variant is often called compare-and-set), or by returning the value read from the memory location (not the value written to it).

There are 3 parameters for a CAS operation:

1. A memory location V where value has to be replaced
2. Old value A which was read by thread last time
3. New value B which should be written over V

CAS says “I think V should have the value A; if it does, put B there, otherwise don’t change it but tell me I was wrong.” CAS is an optimistic technique—it proceeds with the update in the hope of success, and can detect failure if another thread has updated the variable since it was last examined.

3. Java Compare and Swap Example

Let’s understand the whole process with an example. Assume V is a memory location where value “10” is stored. There are multiple threads who want to increment this value and use the incremented value for other operations, a very practical scenario. Let’s break the whole CAS operation in steps:

1) Thread 1 and 2 want to increment it, they both read the value and increment it to 11.

V = 10, A = 0, B = 0

2) Now thread 1 comes first and compare V with it’s last read value:

V = 10, A = 10, B = 11

if     A = V
   V = B
 else
   operation failed
   return V

Clearly the value of V will be overwritten as 11, i.e. operation was successful.

3) Thread 2 comes and try the same operation as thread 1

V = 11, A = 10, B = 11

if     A = V
   V = B
 else
   operation failed
   return V

4) In this case, V is not equal to A, so value is not replaced and current value of V i.e. 11 is returned. Now thread 2, again retry this operation with values:

V = 11, A = 11, B = 12

And this time, condition is met and incremented value 12 is returned to thread 2.

In summary, when multiple threads attempt to update the same variable simultaneously using CAS, one wins and updates the variable’s value, and the rest lose. But the losers are not punished by suspension of thread. They are free to retry the operation or simply do nothing.

Thats all for this simple but important concept related to atomic operations supported in java.

Happy Learning !!