CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 4 of 7 · 2 min read

Compare-and-swap

Think of it this way. A person edits a shared online page. Before saving, the editor checks that nobody changed the page since it was opened. If someone did, the editor reads the page again and redoes the change. No one has to wait for a lock, and nobody blocks. The analogy stops in one place: the editor sees a message that a change happened, while the processor learns it only from the failed compare.

Compare-and-swap (CAS) takes an address, an expected value and a new value. If the memory still holds the expected value, it stores the new value and reports success. Otherwise, it does nothing and reports failure. It is the basis of lock-free updates: a thread reads the value, computes the new one, and tries to install it. If another thread got in first, the thread tries again.

void increment(long *counter) {
    long old;
    do {
        old = __atomic_load_n(counter, __ATOMIC_RELAXED);        /* read   */
    } while (!__atomic_compare_exchange_n(counter, &old, old + 1,  /* try    */
                 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED));         /* retry if it failed */
}

In plain words: Four threads, each incrementing one million times with this loop, reached exactly 4,000,000 in all runs, in 0.125 s. No thread ever holds a lock, so a thread that is descheduled in the middle cannot stop the others. That is the strength of lock-free code: one slow thread does not block the rest.

Trace: two threads A and B, with the counter at 5.

Step A B counter
1 reads 5 5
2 reads 5 5
3 CAS(5 to 6): succeeds 6
4 CAS(5 to 6): fails (value is 6) 6
5 reads 6, CAS(6 to 7): succeeds 7

Compare-and-swap has a known trap, the ABA problem: a value changes from A to B and back to A between a thread's read and its CAS, and the CAS succeeds although things changed. It can break lock-free stacks and queues that compare pointers. Such structures are hard to write correctly, and production code uses well-tested libraries.

Compare-and-swap

Compare-and-swap is an atomic instruction that takes an address, an expected value and a new value, and stores the new value only if the memory still holds the expected value, reporting whether it did.

Example: CAS(counter, 5, 6) succeeds when counter is 5 and fails when another thread has already changed it to 6.

Check yourself: 1. What does a thread do when its CAS fails? 2. Why does a descheduled thread not block the others in lock-free code? 3. What is the ABA problem?