Exercises — Atomic operations and CAS

Atomic: (a) and (c). Not atomic: (b) and (d).

• (a) A single aligned store of a machine word is atomic — no other thread can see it half-written.
• (b) counter++ compiles to load → add → store: three separate steps with a race window between them.
• (c) CAS is a single hardware primitive, atomic by definition.
• (d) += is also load → add → store, same race window as (b). Count of atomic operations: 2.

The stored value is $7$ but $expected=4$. Since $7\ne 4$, the compare fails: memory stays $7$ and CAS returns false. Return = false, memory unchanged (still 7).

old_val = *counter        // read 10
new_val = old_val + 1      // 11
CAS(counter, 10, 11)       // FAILS: counter is now 11, not 10
old_val = *counter         // re-read 11
new_val = old_val + 1      // 12
CAS(counter, 11, 12)       // SUCCEEDS: counter was 11

• Attempt 1: old_val=10, new_val=11, CAS → false
• Attempt 2: old_val=11, new_val=12, CAS → true
• Final counter = 12. (The interfering thread's increment made it 11, ours made it 12 — no update lost.)

Fetch-and-add is atomic, so the two adds compose regardless of order. Final value = $100+5+3=108$. Return values depend on order:

• If +5 runs first: it returns $100$, the +3 returns $105$.
• If +3 runs first: it returns $100$, the +5 returns $103$. Exactly one thread always sees $100$; the other sees the partially-updated value. Final = 108 either way.

void acquire(int* lock) {
    while (test_and_set(lock) == 1) {
        // spin: old value was 1 => lock was already held
    }
    // old value was 0 => it was free, and we just set it to 1: we own it
}

You got the lock when test_and_set returns $0$. Returning $0$ means the word was free and you atomically flipped it to $1$ in the same indivisible step. Returning $1$ means it was already held by someone; you keep spinning. See Spinlocks and Mutexes.

The final CAS wrongly succeeds. T1's expected = A and stack_top is once again A, so the pointer comparison matches — but the structure changed underneath. T1 sets stack_top = B, yet $B$ was already popped and freed by T2. Result: stack_top points to freed memory → corruption. The root cause: CAS compares the pointer value, not the object identity. The pointer returned to $A$ (the "A → B → A" sequence), so CAS cannot tell that everything moved. Fix in ABA Problem Solutions and Exercise 4.1.

Each modification increments the version by $1$:

• start: $⟨A,7⟩$
• after pop A: $⟨B,8⟩$
• after pop B: $⟨\text{NULL},9⟩$
• after push A: $⟨A,10⟩$

T1's CAS uses expected = ⟨A, 7⟩. Current is $⟨A,10⟩$. The pointer matches ($A=A$) but $7\ne 10$, so double-width CAS fails — exactly what we want. Final version = 10; T1's CAS fails and it safely retries. The ABA is defeated.

int swap(int* addr, int new) {
    int old_val;
    do {
        old_val = *addr;               // read current
    } while (!CAS(addr, old_val, new));// install new only if unchanged
    return old_val;
}

No contention: we read old_val, and nothing modifies *addr before CAS, so *addr == old_val still holds. CAS succeeds on the first attempt → exactly one CAS, then we return old_val. With contention, each failure means someone else wrote, so we re-read and retry; every retry makes progress by some thread (lock-freedom). See Lock-Free Data Structures.

Immunity: SC fails if any write touched the address after the LL — even a write that restores the same value. So the A→B→A sequence breaks the reservation and SC returns $0$, unlike CAS which only compares final bits. (Caveat: hardware may lose reservations spuriously, so LL/SC always lives in a retry loop.)

bool CAS(int* addr, int expected, int new) {
    int cur = LL(addr);          // load + reserve
    if (cur != expected)
        return false;            // value differs, give up
    return SC(addr, new) == 1;   // store only if reservation intact
}

If SC returns $0$ (reservation broken), CAS returns false, matching CAS semantics. See Memory Barriers for the ordering fences usually paired with this.

Final value: every increment lands exactly once (CAS guards against lost updates), so final $=N\cdot K=4\cdot 1000=4000$. Minimum total CAS executions: in the best case there is zero contention — every CAS succeeds first try — so each of the $N\cdot K$ successful increments costs exactly one CAS. Minimum $=N\cdot K=4000$. (Failures only add to this; the count can be much higher under contention, but never lower than $4000$.) Answers: final = 4000, minimum total CAS = 4000.

An atomic op executes completely and indivisibly, so no thread sees a partially-completed state. CAS returns true only when *addr equals expected. The ABA problem fools CAS because it compares the pointer value not the object identity. Version counters defeat ABA by forcing CAS to match both the pointer and the version. LL/SC is ABA-immune because SC fails on any intervening write, not just a value mismatch.