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:
- A memory location V where value has to be replaced
- Old value A which was read by thread last time
- 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 !!
Thanks for the detailed post.
Is there a specific exception that is raised when a competing thread fails to update an atomic variable, since the case needs to be handled at code level for a retry. If not, how does the competing thread updates an atomic variable on first failure?
How can we prove java.util.ArrayList is not thread safe with programmatically?
Suppose Thread1 and Thread2 both comes and found A = V true.
Then both the threads will try to set new value.
So resulting output will be 11 instead of 12 Right ?
No. As I said in first para itself, it’s atomic operation. If thread A comes first then it will complete its operation; only then B can try.
So, if thread B is waiting for thread A to complete its operation how it is good then using synchronized keyword ?
Please read again section “Compare and Swap Algorithm”. Its an atomic operation. Advantage is that there is no wait-notify logic in application code, so no overhead. This atomicity is maintained at OS layer.
I got that in first sentence it is atomic it will be done successfully or it will fail.
My concern was if it is not synchronized or lock is not taken it may result that both threads read same value and both threads go for update. Basic Semaphore problem.
Also, I didn’t understand if its atomic why compare , set it directly.
Never mind Thanks
Dins, you are not reading carefully or not understanding!
The point of using CAS (Compare-And-Set) is to offer an _alternative_ to locking. There is no lock. There is no synchronized block. That is the point.
Instead, application code must check that CAS operation was successful — and retry if not. Only one will succeed, other will fail & adjust it’s work to try again. Often this results in a more performant algorithm with less contention.
CAS is common in modern concurrency, it does require differently structured algorithms from ‘synchronized’ however. When the CAS fails to apply the intended work, it must re-read the now updated & try again with a new update.
Good Explanation —
I want to know java already has volatile variables which gives data consistency in multiple threading, then why Atomic variables are introduced? What is the main difference between Volatile and Atomic variables?
The effect of the volatile keyword is approximately same that each individual read or write operation on that variable is atomic. However, an operation that requires more than one read/write operations, such as i++, which is equivalent to i = i + 1, which does one read and one write — is not atomic, since another thread may write to i between the read and the write.
tricky concept explained in detail with such simplicity,thank you:)
CAS is fast — much faster than a synchronized block. It’s a building-block for higher level locking & concurrency operations.
For performance-critical code, we should consider & often prefer CAS-based approaches due to their superior performance over ‘synchronized’.
Can’t be more agree with you.
Lokesh,
There is a possibility that 2 threads which are trying to get the incremented value – reach the below statement at same time – which checks for if A = V
– and this statement hold true for both threads .
How this scenario gets handled???
“A = V” will never be true for both threads if first thread modified the value at V. Remember all 3 operations are done as a atomic operation.
Hi Lokesh,
I have two doubts here..
1) You used three variables in total in the example. One variable V is for actual data location where the data lives in the memory.Second is A which is a temporary variable to read the value at V from memory and store for comparison(which is called “current” technically). Third is B which is again a temporary variable to increment the value which has been read(A) and replace the original value in the memory(which is called “next” technically). Does compareAndSet(int current, int next) method in say AtomicInteger class do the same? I mean use all the three locations?
2) You mentioned that all those three operations, i.e. reading V, doing if(V==A) and V==B are atomic. Something can’t be atomic by itself yes? For example to make a block of code atomic, we use Synchronized blocks or classes in java.util.concurrent.locks package. And it is interesting that you mentioned that atomicity is maintained at OS level. Can you please provide an insight into how actually it is done of possible? If both threads read V==A at the same time case. Thanks in advance. Your article is very helpful btw 🙂
Hi Lokesh,
Thank you for such a nice explanation about CAS.
I have a query on this statement, “But the losers are not punished by suspension of thread. They are free to retry the operation or simply do nothing”.
– What determines whether a thread will retry or do nothing? By ‘operation failed…’ do you an exception is thrown?
It solely depend on thread itself that it will retry or not. e.g. Java AtomicXXX will retry if failed in first attempt. Operation failed means the value which thread was trying to update, didn’t updated; in other words, update operation failed.
Hi Pankaj,
Let me again thank you for simplify CAS. Please clarify some of my queries on CAS
1. “Now thread 2, again retry this operation with values” – In a Concurrent Multi-Thread scenario all the threads(except 1) operation fails and all of them try to re-attempt, which directly increases there ideal time ?
2. What do you think about “CAS” not created as a keyword like “Volatile”?