Exercises — std - atomic — lock-free operations

WHAT: (A) and (C) are atomic; (B) is not a single atomic operation. WHY:

• a.fetch_add(1) is a member function → one indivisible read-modify-write (RMW). (Order defaults to seq_cst since none is given.) ✅
• ++a calls atomic<int>::operator++, which internally does one RMW. ✅
• a = a + 1 expands to: an atomic load of a, then +1 in a register, then an atomic store to a. Two separate atomic ops. Another thread can slip between them → lost update (exactly figure s01). ❌ Answer: A and C.

memory_order_relaxed. It guarantees the operation on this atomic is indivisible, but places no ordering constraint on surrounding reads/writes of other memory. (Contrast with the default seq_cst, which you get if you pass no argument.)

• is_always_lock_free is a compile-time constant: this type is lock-free on every target this program can run on. You can use it in static_assert.
• a.is_lock_free() is a runtime query for this particular object on this machine (alignment/size can matter). If is_always_lock_free is true, is_lock_free() is guaranteed true too.

Answer: exactly 200000. WHY it is genuinely shared (and thus a real race target): if each thread had its own local counter, there would be no cross-thread interaction at all and the question would be trivial. The point of the exercise is that both threads increment the same memory location — that is precisely where the figure-s01 lost-update race would occur with a plain int. Because we use an atomic fetch_add, the race is defeated. WHY the value: fetch_add is one atomic RMW, so no increment is ever lost — each of the $2\times 100000$ increments lands. $2\times 100000=200000$. WHY relaxed is fine: we only care that the count is right, not about ordering this counter relative to any other variable. Atomicity (no torn/lost updates) is preserved under every memory order; relaxed merely drops the cross-variable ordering we do not use here — the cheapest correct choice. (Note the default would be seq_cst; we consciously downgraded.)

a.fetch_add(5);   // single atomic RMW: returns the OLD value (order defaults to seq_cst)

WHY: a = a + 5 is load-then-store (two ops, a race window between them). fetch_add(5) performs load-add-store as one indivisible unit — no window.

Producer store → std::memory_order_release. Consumer load → std::memory_order_acquire. WHY: the release store "seals the package": every write before it (including data = 42) is pinned to happen before the flag becomes visible. The acquire load "opens the package": once it sees true, it is guaranteed to also see everything sealed before the release. That pair forms a synchronizes-with edge (see figure s02). With relaxed on either side, data could still read 0. (Leaving the blanks empty would give the seq_cst default — also correct here, just stronger/slower than needed.)

Both read old = 5. Say thread A runs its CAS first.

• A: compare_exchange_weak(old=5, 6) → a is 5 == expected → sets a = 6, returns true. A exits.
• B: compare_exchange_weak(old=5, 6) → a is now 6 != expected 5 → fails, and writes the current value 6 into old. The loop condition is !false... wait: CAS returned false, so !false == true → loop body runs again with refreshed old = 6.
• B retry: compare_exchange_weak(old=6, 7) → a is 6 == expected → sets a = 7, returns true. B exits.

Final value: 7. No update lost: A applied +1 (5→6), B applied +1 (6→7). This is optimistic concurrency: assume no conflict, verify at write time, retry the loser. (These CAS calls omit orders → seq_cst default.)

Not wrong, but sub-optimal inside a loop.

• compare_exchange_weak may fail spuriously (report failure even when a == expected), because on some architectures it maps to a cheaper instruction pair called LL/SC — load-linked / store-conditional. Load-linked reads a location and marks it watched; store-conditional writes back only if nothing touched that location meanwhile, otherwise it fails. That "fail if disturbed" check can trip even when the value looks unchanged (e.g. an unrelated cache event), which is the spurious failure. In a loop you retry anyway, so a spurious failure costs one extra harmless iteration.
• compare_exchange_strong guarantees no spurious failure, but must add a retry loop internally on those same LL/SC architectures → extra work. Rule: _weak inside loops, _strong for a single non-looped check.

Lock-free ≠ wait-free ≠ always faster. Lock-free guarantees some thread makes progress each step, not that every thread does. Under heavy contention many threads' CAS calls fail and retry repeatedly — each failed CAS is a wasted round-trip that also bounces the cache line between cores (coherency traffic, see Cache Coherency MESI). A mutex, by contrast, parks losers so only one core touches the line and there is no spin-storm. Takeaway: lock-free shines at low–medium contention; always measure. See also False Sharing for a related slowdown when unrelated atomics share a cache line.

void push(int v){
    Node* n = new Node{v, head.load(std::memory_order_relaxed)};
    while(!head.compare_exchange_weak(
              n->next, n,
              std::memory_order_release,   // success: publish n and everything we wrote into it
              std::memory_order_relaxed))  // failure: pure re-read, no ordering needed
    {}
}

WHY the CAS (n->next, n): expected = n->next (the head we think we're behind), desired = n (our node). CAS installs n as the new head only if head still equals n->next. If another thread pushed in between, CAS fails and writes the new head into n->next — so n is automatically re-linked behind the fresh head, and we retry. No mutex, no blocking (see figure s03 for the CAS timeline).

WHY these memory orders (this is the point of the exercise): the two-argument form lets us pick a success order and a failure order separately.

• Success = release. When the CAS succeeds it publishes n (a store). We want the initialisation of *n (v and next) to be visible to any thread that later load(acquire)s the head and dereferences our node — so we need release semantics on the winning store. acq_rel would also work if a reader/popper needed to acquire on this same op, but push only writes, so plain release is the minimum correct choice.
• Failure = relaxed. A failed CAS is a pure load that just refreshes n->next; nothing downstream depends on ordering it, so relaxed is cheapest. (Recall: the failure order may never be a release.)
• Omitting the orders entirely would default to seq_cst on both paths — correct, but heavier than needed here.

CRITICAL edge case — this toy push is safe, but pop is NOT, because of the ABA problem. push only ever adds, so the head pointer it CASes against is always a valid comparison. The danger appears in pop:

1. Thread 1 reads head = A, plans to CAS head from A to A->next (call it B).
2. Thread 1 stalls. Meanwhile another thread pops A, pops B, then pushes A back. head is A again — but A->next now points somewhere else, and B may have been freed.
3. Thread 1 wakes, its CAS sees head == A (the A→B→A sequence looked unchanged!) and succeeds — installing a stale/freed B. Corruption.

This is the ABA problem: CAS compares values, and a value can return to A after changing, so "unchanged value" ≠ "untouched". Safe reclamation is needed so freed nodes aren't reused (or reused addresses aren't mistaken for the same logical node). Standard fixes:

• Tagged/versioned pointers — pack a counter into the pointer word; every push/pop bumps the tag, so A with tag 7 ≠ A with tag 9, and the CAS distinguishes them.
• Hazard pointers — each thread publishes the pointers it is about to dereference; a node is only actually freed once no hazard pointer references it.
• RCU / epoch-based reclamation — defer freeing until all readers that could hold the pointer have moved on.

For this exercise the push-only code is correct; just remember that a real lock-free stack with pop must address ABA and reclamation.

void multiply_by(std::atomic<int>& a, int k){
    int old = a.load(std::memory_order_relaxed);
    while(!a.compare_exchange_weak(old, old * k,
                                   std::memory_order_relaxed)) {
        /* old was refreshed to current value → recompute old*k */
    }
}

WHY this pattern: any RMW a ← f(a) with no hardware instruction becomes a CAS retry loop: read old, compute f(old), CAS. If someone changed a, CAS refreshes old and we recompute old * k. Eventually one thread wins → lock-free progress. This is the universal recipe from the parent note. Why one order here works: the single relaxed argument sets the success order to relaxed and derives a relaxed failure order — fine, since this counter has no cross-variable ordering dependency. If a guarded other data you'd raise success to release/acq_rel. Check: starting a=3, multiply_by(a,4) gives 12; then multiply_by(a,5) gives 60.

void lock(){   while(flag.exchange(true, std::memory_order_acquire)); }
void unlock(){ flag.store(false, std::memory_order_release); }

WHY acquire on lock: exchange returns the old value; we spin until it was false (we grabbed the lock). The acquire ensures no read/write inside the critical section can be reordered before we own the lock — nothing "opens the package" early. WHY release on unlock: the release store pins every write inside the critical section to happen before the flag drops to false — so the next thread that acquires sees all our updates. Together: release → acquire synchronizes-with across the two threads. relaxed on either side would let critical-section memory leak in or out of the lock. (Omitting the orders would default to seq_cst — correct but stricter than needed.) Compare with a real Mutex and Lock, which does this for you.

Diagnosis: false sharing. Independent counters that sit in the same 64-byte cache line bounce that line between cores on every atomic write, even though no two threads touch the same counter. The coherency protocol (MESI) invalidates the whole line, not just a byte. See False Sharing and Cache Coherency MESI. Fix: pad/align each counter to its own cache line:

struct alignas(64) Padded { std::atomic<int> c{0}; };
Padded counters[64];

Now each thread's write dirties a different line → no cross-core invalidation storm.

Progress argument: each iteration, a thread reads the current value old, computes f(old), and CASes. A CAS fails only if some other thread's CAS succeeded and changed the value since our read. So every failure is caused by another thread's success. Therefore in any run, at each contended step at least one thread completes its operation → the whole system never stalls → lock-free by definition. What it does NOT guarantee: wait-freedom. A single unlucky thread can be perpetually beaten to the CAS and retry indefinitely (starvation of that thread), even while the system as a whole keeps progressing. Lock-free is a system guarantee, not a per-thread one.

Why does fetch_add beat a = a + 1? ::: fetch_add is a single indivisible RMW; a = a + 1 is a separate atomic load then atomic store with a racy gap between them. When is relaxed safe? ::: When you only need this atomic's own correctness, with no ordering dependency on any other variable. What is the default memory order if you pass none? ::: std::memory_order_seq_cst — the strongest and slowest. What order should the success path of a lock-free push CAS use, and the failure path? ::: success = release (publishes the new node); failure = relaxed (a pure re-read). What is the ABA problem? ::: A value changes A→B→A, so a CAS sees "unchanged" and succeeds even though the state was disturbed; fixed with tagged pointers, hazard pointers, or epoch reclamation. Lock-free vs wait-free? ::: Lock-free = the system always progresses; wait-free = every thread finishes in bounded steps (stronger).