Do I use atomic_compare_exchange_strong or atomic_exchange in c++11?

Question

I am learning the basics of C++ atomicity and multithreading. Depending on a state (running/sleeping) I either have to run a function (and update the state to running) or do nothing.

Is there any difference between atomic_compare_exchange_strong and atomic_exchange as in the snippets below? Any side effects or pitfalls with either approach?

std::atomic<State> state{State::sleeping};

for (int i = 0; i<4; i++)
{
    State expected{State::sleeping};
    //if (std::atomic_compare_exchange_strong(&state, &expected, State::running))
    if (state.compare_exchange_strong(expected, State::running))
    {
        cout << "running" << endl;
        continue;
    }

    cout << "sleeping" << endl;             
}

vs

std::atomic<State> state{State::sleeping};

for (int i = 0; i<4; i++)
{
    //if (std::atomic_exchange(&state, State::running) != State::running)
    if (state.exchange(State::running) == State::running)
    {
        cout << "running" << endl;
        continue;
    }

    cout << "sleeping" << endl;             
}

Answer 1

The semantics of "exchange" and "compare-and-exchange" (CAS) are completely different, and that's even independent of the atomic business. Exchange is unconditional, and CAS only modifies the variable conditionally.

So when you say x.exchange(A), then x unconditionally now holds the value A. By contrast when you say old = B; x.compare_exchange(old, A);, then x is only given the value A if it previously held the value B, but it is not modified otherwise.

In particular, if x is already in state A, then CAS will fail, whereas the exchange proceeds regardless. If you think of state A representing the fact that something needs to happen and B as being idle, then the CAS will allow the system to finish whatever it's doing before giving it more work, whereas exchange will just drop whatever current state is on the floor. (Yes, you can handle the return value of the exchange and perhaps resume the work at that point, but that's not generally applicable.)

There are valid use cases for both algorithms, of course. Exchange is much cheaper and should be used when it applies. Here are two typical examples:

• Inserting a new node into a linked list at the head position. You first figure out the current head, then set up the new node to point to the current head, and then update the head. This needs to be a CAS, since you only want to update the head if the current head is still what you thought it was. If you used exchange here, you'd discard any other updates that may have happened in the meantime.

• Acquiring a spin lock. This is similar to your code example. You only need to know what the old value was, and you don't care about repeatedly writing a new value to the lock word. So you can just exchange the value "locked" into it, and as soon as you get the previous value "unlocked" back, you have entered the critical section. Since exchange suffices for this operation, it is preferable over CAS.