HowToDoInJava

  • Python
  • Java
  • Spring Boot
  • Dark Mode
Home / Java / Multi-threading / Java Compare and Swap Example – CAS Algorithm

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 !!

Was this post helpful?

Let us know if you liked the post. That’s the only way we can improve.

Share this:

  • Twitter
  • Facebook
  • LinkedIn
  • Reddit

About Lokesh Gupta

A family guy with fun loving nature. Love computers, programming and solving everyday problems. Find me on Facebook and Twitter.

Feedback, Discussion and Comments

  1. csharma

    July 10, 2017

    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?

  2. basha.a

    June 9, 2016

    How can we prove java.util.ArrayList is not thread safe with programmatically?

  3. Dins

    June 8, 2015

    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 ?

    • Lokesh Gupta

      June 9, 2015

      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.

      • Dins

        June 9, 2015

        So, if thread B is waiting for thread A to complete its operation how it is good then using synchronized keyword ?

        • Lokesh Gupta

          June 9, 2015

          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.

          • Dins

            June 9, 2015

            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

            • Tom W

              June 12, 2015

              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.

  4. Sandip

    March 13, 2015

    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?

    • Lokesh Gupta

      March 15, 2015

      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.

  5. arun sundar s

    November 2, 2014

    tricky concept explained in detail with such simplicity,thank you:)

  6. Tom W

    June 15, 2014

    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’.

    • Lokesh Gupta

      June 15, 2014

      Can’t be more agree with you.

  7. Gagan Gupta

    June 14, 2014

    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???

    • Lokesh Gupta

      June 14, 2014

      “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.

      • shiva

        December 8, 2015

        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 🙂

  8. Ankush

    June 14, 2014

    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?

    • Lokesh Gupta

      June 14, 2014

      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.

  9. HIMANSU NAYAK

    June 13, 2014

    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”?

Comments are closed on this article!

Search Tutorials

Java Concurrency Tutorial

  • Java Concurrency – Introduction
  • Concurrency Evolution
  • Thread Safety
  • Concurrency vs. Parallelism
  • Compare and Swap [CAS]
  • synchronized keyword
  • Object vs. Class Level Locking
  • Runnable vs. Thread
  • wait(), notify() and notifyAll()
  • Yield() vs. Join()
  • Sleep() vs. Wait()
  • Lock vs. Monitor
  • Callable + Future
  • UncaughtExceptionHandler
  • Throttling Task Submission
  • Executor Best Practices
  • Inter-thread Communication
  • Write and Resolve Deadlock

Java Concurrency Utilities

  • AtomicInteger
  • Lock
  • ThreadFactory
  • ThreadLocal
  • ExecutorService
  • ThreadPoolExecutor
  • FixedSizeThreadPoolExecutor
  • ScheduledThreadPoolExecutor
  • Semaphore
  • Binary Semaphore
  • BlockingQueue
  • DelayQueue
  • ConcurrentLinkedDeque
  • CountDownLatch
  • ForkJoinPool

Java Tutorial

  • Java Introduction
  • Java Keywords
  • Java Flow Control
  • Java OOP
  • Java Inner Class
  • Java String
  • Java Enum
  • Java Collections
  • Java ArrayList
  • Java HashMap
  • Java Array
  • Java Sort
  • Java Clone
  • Java Date Time
  • Java Concurrency
  • Java Generics
  • Java Serialization
  • Java Input Output
  • Java New I/O
  • Java Exceptions
  • Java Annotations
  • Java Reflection
  • Java Garbage collection
  • Java JDBC
  • Java Security
  • Java Regex
  • Java Servlets
  • Java XML
  • Java Puzzles
  • Java Examples
  • Java Libraries
  • Java Resources
  • Java 14
  • Java 12
  • Java 11
  • Java 10
  • Java 9
  • Java 8
  • Java 7

Meta Links

  • About Me
  • Contact Us
  • Privacy policy
  • Advertise
  • Guest and Sponsored Posts

Recommended Reading

  • 10 Life Lessons
  • Secure Hash Algorithms
  • How Web Servers work?
  • How Java I/O Works Internally?
  • Best Way to Learn Java
  • Java Best Practices Guide
  • Microservices Tutorial
  • REST API Tutorial
  • How to Start New Blog

Copyright © 2020 · HowToDoInjava.com · All Rights Reserved. | Sitemap

  • Java 15 New Features
  • Sealed Classes and Interfaces
  • EdDSA (Ed25519 / Ed448)