How atomicity is achieved in the classes defined in java.util.concurrent.atomic package?

Question

I was going through the source code of java.util.concurrent.atomic.AtomicInteger to find out how atomicity is achieved by the atomic operations provided by the class. For instance AtomicInteger.getAndIncrement() method source is as follows

public final int getAndIncrement() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return current;
    }
}

I am not able to understand the purpose of writing the sequence of operations inside a infinite for loop. Does it serve any special purpose in Java Memory Model (JMM). Please help me find a descriptive understanding. Thanks in advance.

You seem to be ignoring that a method is being called in that loop and the result of that method is the condition to break the loop. Google "Compare and swap" — Brian Roach, Jun 05 '13 at 13:05
This is a classic use case for a `goto`. In a `goto`less language we use an infinite loop. — Marko Topolnik, Jun 05 '13 at 13:22

Gray · Answer 1 · 2013-08-22T14:29:07.307

I am not able to understand the purpose of writing the sequence of operations inside a infinite for loop.

The purpose of this code is to ensure that the volatile field gets updated appropriately without the overhead of a synchronized lock. Unless there are a large number of threads all competing to update this same field, this will most likely spin a very few times to accomplish this.

The volatile keyword provides visibility and memory synchronization guarantees but does not in itself ensure atomic operations with multiple operations (test and set). If you are testing and then setting a volatile field there are race-conditions if multiple threads are trying to perform the same operation at the same time. In this case, if multiple threads are trying to increment the AtomicInteger at the same time, you might miss one of the increments. The concurrent code here uses the spin loop and the compareAndSet underlying methods to make sure that the volatile int is only updated to 4 (for example) if it still is equal to 3.

t1 gets the atomic-int and it is 0.
t2 gets the atomic-int and it is 0.
t1 adds 1 to it
t1 atomically tests to make sure it is 0, it is, and stores 1.
t2 adds 1 to it
t2 atomically tests to make sure it is 0, it is not, so it has to spin and try again.
t2 gets the atomic-int and it is 1.
t2 adds 1 to it
t2 atomically tests to make sure it is 1, it is, and stores 2.

Does it serve any special purpose in Java Memory Model (JMM).

No, it serves the purpose of the class and method definitions and uses the JMM and the language definitions around volatile to achieve its purpose. The JMM defines what the language does with the synchronized, volatile, and other keywords and how multiple threads interact with cached and central memory. This is mostly about native code interactions with operating system and hardware and is rarely, if ever, about Java code.

It is the compareAndSet(...) method which gets closer to the JMM by calling into the Unsafe class which is mostly native methods with some wrappers:

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

According to my understanding of Volatile: it solves the visibility purpose without using synchronization or any kind of explicit locking. Therefore, volatile can be used without synchronization for consistent visibility of read/write. So, why to use this special for loop for synchronization? If you can explain more about the relation between loops and synchronization, it would be a great help. Thanks for instant reply. — Vaibhav Raj, Jun 05 '13 at 13:11
@VaibhavRaj - The loop has nothing to do with synchronization. It loops until the CAS operation succeeds. — Brian Roach, Jun 05 '13 at 13:16
`volatile` is about visibility; `AtomicInteger` is about *lock-free atomicity*. You can't achieve that without retries. Infinite loop = retries. — Marko Topolnik, Jun 05 '13 at 13:16
Well `volatile` solves the problem of visibility without using the `synchronized` keyword but ensuring memory synchronization is part of what it does. What it _doesn't_ do is give you atomic access to a boolean. — Gray, Jun 05 '13 at 13:17
Is volatile used to solve / improve the progress of the algorithm? Like if volatile is not used the value can be kept on the CPU caches for too long wasting cicles on the spin loop. — Marcos Vinícius da Silva, Feb 18 '22 at 13:18

score 6 · Accepted Answer · edited Aug 22 '13 at 14:46

I am not able to understand the purpose of writing the sequence of operations inside a infinite for loop.

To understand why it is in an infinite loop I find it helpful to understand what the compareAndSet does and how it may return false.

Atomically sets the value to the given updated value if the current
value == the expected value.

 Parameters:
     expect - the expected value
     update - the new value 
 Returns:
     true if successful. False return indicates that the actual value was not
     equal to the expected value

So you read the Returns message and ask how is that possible?

If two threads are invoking incrementAndGet at close to the same time, and they both enter and see the value current == 1. Both threads will create a thread-local next == 2 and try to set via compareAndSet. Only one thread will win as per documented and the thread that loses must try again.

This is how CAS works. You attempt to change the value if you fail, try again, if you succeed then continue on.

Now simply declaring the field as volatile will not work because incrementing is not atomic. So something like this is not safe from the scenario I explained

volatile int count = 0;

public int incrementAndGet(){
   return ++count; //may return the same number more than once.
}

"incrementing is not atomic" - because it is essentially 2 operations, read and write, and race conditions can still happen between these operations. Unless you make it atomic (literally = non separable) — Maverick Meerkat, Jan 20 '19 at 09:36

Evgeniy Dorofeev · Answer 3 · 2013-06-05T13:33:15.493

Java's compareAndSet is based on CPU compare-and-swap (CAS) instructions see http://en.wikipedia.org/wiki/Compare-and-swap. It 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.

In case of incrementAndGet we read the current value and call compareAndSet(current, current + 1). If it returns false it means that another thread interfered and changed the current value, which means that our attempt failed and we need to repeat the whole cycle until it succeeds.

How atomicity is achieved in the classes defined in java.util.concurrent.atomic package?

3 Answers3

Linked