Why atomic provide the compare_exchange_strong?

Question

Now I'm studying about the AtomicInteger class on Android.

This Java class has two methods

public final void set(int newValue) {
    value = newValue;
}

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

Question 1: The set method stores the new value directly, so this method is not atomic? If we want that the result is correct in many threads we need to use the compareAndSet method?

I had read the source code about AtomicInteger.compareAndSet(). At its end it invokes the std::atomic<T>::compare_exchange_strong method. The incrementAndGet method invokes the compareAndSet.

Question 2: I had read some articals about the CAS, the compare_exchange_strong() is atomic and the store() is also atomic. So I want to know , why we do not use store directly, why need the CAS methods?

Kerrek SB · Accepted Answer · 2016-06-08T10:55:33.097

The point of CAS is that it allows you to store a value that is conditional on the original value. A simple store can be done atomically, of course, but it may not be what you want.

Consider the simple "atomic increment" operation:

Load the current value.
Compute the new value.
Store the new value.

If you used unrelated atomic loads and stores for this procedure, then two threads can read, compute and store the same value, and so one of the increments is lost! Loads and stores are simple atomic operations, whereas CAS is an atomic read-modify-write (RMW) operation. RMWs are more complex than simple loads and stores. RMWs don't only guarantee that a simple value is produced correctly, but that a complex logical operation is applied correctly.

Let's implement atomic increment using CAS to demonstrate how this works:

// Effect: x += n, returns old value of x.
int inc(int n, std::atomic<int> & x)
{
    int old_val = x.load();
    for (;;) {
        int new_val = old_val + n;
        if (x.compare_exchange_weak(old_val, new_val)) {
            return old_val;
        }
        // Note: If the exchange fails, old_val is updated
        //       to the current value of x.
    }
}

The crucial point here is that this operation must be a loop, because while we are computing our tentative result (new_val = old_val + n), the value old_val may have become obsolete, because some other thread already modified it. So we must loop for until we get a chance to apply the new value in a situation where x currently holds the old value. That's the point of CAS: It stores a new value conditional on the old value being what we think it is.

On the distinction of "strong" vs "weak" exchange: If you want your algorithm to succeed unconditionally, you always want a loop like I showed, and you use the weak exchange. The difference is that the weak form may "fail spuriously", i.e. return false even though the stored value is the expected one. (This relaxation allows for more efficient instructions on some platforms.) The strong form may be more expensive but doesn't fail spuriously, and it may be useful in situations where you perform an "optimistic" CAS but don't care whether it succeeds. This is useful in certain concurrent data structures (e.g. queues) where threads make a best effort to help out, but don't need to promise success.

Thanks a lot. So It means if we do not have CAS , we need to add a lock to guarantee the operate sequence and the whole operation is atomic? I know that the CAS implement by CPU instruction just like CMPXCHG on X86. So the CAS is only used to guarantee incrementAndGet and decrementAndGet correctly in multi-thread ? — user6361246, Jun 08 '16 at 10:24
@user6361246: Yes, that's essentially correct. Note that a CAS loop *is* a bit like a lock from the thread's point of view in the sense that you spin indefinitely until you succeed - it's just not a lock that prevents another thread from also trying this. At the hardware level, CAS may involve an actual bus lock (like on x86; your cmpxchg needs a LOCK prefix for correctness), or it may use load-linked/store-conditional mechanics that use extra storage to keep track of who accessed a memory location. — Kerrek SB, Jun 08 '16 at 10:58

Why atomic provide the compare_exchange_strong?

1 Answers1