Compare-and-Swap in Optimistic Concurrency

The Limits of Simple Atomic Operations

We've seen that C11 provides convenient atomic operations like atomic_fetch_add for simple tasks. But what if we need to perform an operation for which there's no built-in atomic function, like multiplication or a conditional update?

Consider this naive attempt to multiply an atomic integer by 2:

_Atomic int value = 10;

// Thread 1
int current_val = atomic_load(&value);   // Reads 10
int new_val = current_val * 2;           // Computes 20
// <-- Context switch! Another thread runs here.
atomic_store(&value, new_val);           // Writes 20

If another thread modifies value between the atomic_load and atomic_store, that modification will be overwritten and lost. This three-step "read-modify-write" sequence is not atomic. We need a way to perform all three steps as a single, indivisible operation.

This is the exact problem that Compare-and-Swap solves.

Compare-and-Swap: The Conditional Atomic Update

Compare-and-Swap (CAS) is a special atomic instruction that allows you to say:

"Atomically update a memory location to a new value, but only if that location currently contains a specific value I expect it to have."

It fuses the read, modify, and write steps into a single, indivisible transaction.

The following video by Herb Sutter provides an excellent mental model for this operation.

As you saw, the operation checks if the current value matches an expected value. If it does, it performs the swap and succeeds. If not, it fails and, crucially, tells you what the value actually was.

In C11 (stdatomic.h), this is implemented as atomic_compare_exchange_strong():

bool atomic_compare_exchange_strong(
    _Atomic A *object, 
    C *expected, 
    C desired
);

Let's break down the parameters:

• object: A pointer to the atomic variable you want to modify.
• expected: A pointer to a non-atomic variable holding the value you believe object currently has. This is an in-out parameter.
  • On success (returns true): The object is updated to desired. The expected variable is untouched.
  • On failure (returns false): The object is untouched. The expected variable is updated with the actual current value from object.
• desired: The new value you want to store in object if the comparison succeeds.

This "update-on-failure" behavior of the expected parameter is an efficient design. It saves you from having to perform another atomic_load after a failed attempt, preparing you immediately for a retry.

Optimistic Concurrency: The CAS Loop

The CAS operation is the engine of a concurrency strategy called optimistic concurrency. This stands in contrast to the pessimistic concurrency you've used before with mutexes.

• Pessimistic Concurrency (Locks): Assume contention is likely. Lock a critical section to prevent other threads from interfering, do your work, and then unlock. This is safe but can be slow, as other threads must block and wait for the lock.
• Optimistic Concurrency (CAS): Assume contention is rare. Don't lock anything. Read the data, compute the new result speculatively, and then use CAS to try and publish your change. If CAS fails, it means another thread changed the data first. Instead of blocking, you simply retry.

This image brilliantly contrasts the two approaches for a simple increment operation.

This leads to the most common pattern in lock-free programming: the CAS loop. The following video segment explains this pattern perfectly.

Let's translate that C++ example into a C11 function that atomically multiplies a value.

#include <stdatomic.h>
#include <stdbool.h>

void atomic_multiply(_Atomic int *object, int operand) {
    int expected = atomic_load(object);
    int desired;

    do {
        desired = expected * operand;
    } while (!atomic_compare_exchange_weak(object, &expected, desired));
}

Let's trace this loop:

1. Load: We start by loading the current value of object into our local variable expected.
2. Compute: We calculate the desired value based on the expected value.
3. Compare and Swap: We call atomic_compare_exchange_weak.
   • If it returns true: Success! object's value was what we expected, and it has now been atomically updated to desired. The loop terminates.
   • If it returns false: Failure. Another thread modified object after our initial load. The hardware atomically updates our expected variable with the new, fresh value from object. The while condition is met, and the loop repeats from step 2 with the new expected value.

This loop is lock-free: at least one thread always makes progress. If your CAS fails, it's because another thread's CAS succeeded. The system as a whole is not blocked.

void atomic_add_if_less_than(_Atomic int *val, int add, int limit) {
    int expected = atomic_load(val);
    int desired;

    do {
        if (expected >= limit) {
            // The condition isn't met. We don't want to change the value.
            return; 
        }
        desired = expected + add;
    } while (!atomic_compare_exchange_weak(val, &expected, desired));
}

Strong vs. Weak CAS

You may have noticed my example used atomic_compare_exchange_weak while our first C11 reference was to the strong version.

• atomic_compare_exchange_strong: Guaranteed to return false only if the value of object was not equal to expected.
• atomic_compare_exchange_weak: Can spuriously fail. It might return false even if the values were equal, forcing an extra loop iteration.

Why would anyone use weak? On some CPU architectures (notably not x86/x64), a weak CAS can be implemented with a more efficient instruction sequence. If you are already using CAS inside a loop, a rare spurious failure just causes one more spin of the loop, which is often a negligible performance cost in exchange for a potentially cheaper instruction. For algorithms that don't use a loop, strong is almost always the correct choice. In practice, when in a loop, weak is a common and often preferred choice.

Conclusion

You have just learned the most fundamental building block of lock-free programming. By understanding Compare-and-Swap, you've moved beyond simple atomics and grasped the core mechanism for implementing complex, non-blocking concurrent algorithms.

Key Takeaways:

• A "read-modify-write" sequence on an atomic variable is not itself atomic and can lead to lost updates.
• Compare-and-Swap (CAS) is an atomic primitive that updates a value only if it currently holds an expected value.
• CAS is the foundation of optimistic concurrency, a strategy that avoids locking by speculatively performing work and retrying if a conflict occurs.
• The canonical pattern for optimistic concurrency is the CAS loop, where a thread repeatedly tries to commit a change until it succeeds.
• The CAS loop provides lock-freedom: it guarantees system-wide progress, preventing the deadlocks and performance bottlenecks associated with blocking locks.

Preview of the Next Lesson:
We are now fully equipped to put this powerful tool to work. In our next lesson, you will implement a simple lock-free stack using atomic compare-and-swap operations. You'll see how the abstract CAS loop pattern translates directly into the core logic of a practical, high-performance concurrent data structure.