Mutex — implementation using hardware atomics (test-and-set, CAS)

WHY do we even need hardware help?

Intuition Why software alone fails

Imagine lock is a boolean. The "obvious" lock looks like:

while (lock == true) { }   // wait
lock = true;               // grab it

This is two separate machine operations: a read and a write. The CPU can switch threads between them.

Thread A reads lock == false → about to set it.
Context switch → Thread B reads lock == false too → sets lock = true, enters.
Thread A resumes, sets lock = true, also enters.

Both are inside the critical section. Mutual exclusion is broken. The bug feels invisible because the code looks sequential — but the read and write are not glued together.

The fix: a single CPU instruction that reads the old value AND writes a new value in one atomic, uninterruptible step, with the bus locked so no other core can sneak in.

WHAT is an atomic instruction?

test-and-set: derive the lock from scratch

Definition test-and-set semantics

test_and_set(addr) does this as one atomic unit:

old = *addr;
*addr = 1;
return old;

HOW to build a spinlock from TAS

Formula TAS spinlock

acquire(lock):
    while (test_and_set(&lock) == 1)   // spin while it WAS already 1
        ;                              // (someone else holds it)
release(lock):
    lock = 0;

WHY this is correct. test_and_set always sets lock = 1. The return value tells us what it used to be:

If old value was 0 → the lock was free, and we just claimed it. Loop exits → we own it.
If old value was 1 → someone already held it; we set it to 1 again (harmless, it was already 1) and keep spinning.

The "check" (read old) and the "claim" (write 1) are now one indivisible action, so the race from above cannot happen. There is no window between read and write for another thread to slip through.

compare-and-swap (CAS): the more powerful primitive

Definition CAS semantics

compare_and_swap(addr, expected, new) does atomically:

if (*addr == expected) { *addr = new; return true; }
else                   { return false; }

Some hardware returns the old value instead of a bool (CMPXCHG). Same idea.

Formula CAS spinlock

acquire(lock):
    while (!compare_and_swap(&lock, 0, 1))   // try to flip 0 -> 1
        ;
release(lock):
    lock = 0;   // or CAS(&lock, 1, 0)

WHY CAS > TAS. TAS can only manipulate a boolean. CAS lets you say "change X only if it's still the value I last saw." This enables lock-free data structures (counters, stacks, queues), not just mutexes. It's the foundation of AtomicInteger.compareAndSet, std::atomic::compare_exchange, etc.

Figure — Mutex — implementation using hardware atomics (test-and-set, CAS)

Worked examples

Worked example Example 2 — atomic counter increment with CAS (lock-free)

Goal: increment a shared counter without a mutex.

do {
    old = counter;            // read snapshot
    new = old + 1;            // compute
} while (!CAS(&counter, old, new));   // commit only if unchanged

Read old. Why? CAS needs an "expected" value to compare against.
Compute new from old. Why? We do the work optimistically, assuming no interference.
CAS commits only if counter still equals old. Why? If another thread changed it meanwhile, our new is stale → CAS fails → we retry with a fresh read. Result: no lock, no deadlock; under contention threads just retry the loop.

Worked example Example 3 — Test-and-Test-and-Set (an optimization)

Plain TAS spinning hammers the bus with atomic writes. Better:

acquire(lock):
    while (true) {
        while (lock == 1) ;            // spin on a CHEAP read (cached)
        if (test_and_set(&lock) == 0)  // only do the expensive atomic when it looks free
            return;
    }

Inner loop spins on a plain read — stays in local cache, no bus traffic. Why? Atomic RMW invalidates other cores' cache lines; reading is far cheaper.
Only when lock looks free do we attempt the atomic TAS. Why? Reduces cache-line bouncing under high contention. Result: same correctness, much less bus contention.

Common mistake Steel-manning common errors

"Spinlock = busy waiting = always bad." Feels right because spinning burns CPU. Fix: on multi-core, if the critical section is short, spinning is faster than sleeping (no context-switch cost). Real mutexes spin briefly, then sleep. Choose based on expected wait time.
"volatile is enough for the flag." Feels right — volatile prevents the compiler caching it. Fix: volatile does NOT make read-modify-write atomic and gives no memory ordering guarantees. You still need a hardware atomic.
"Release just needs lock = 0, ordering doesn't matter." Feels right — it's one write. Fix: you need a memory barrier so writes inside the critical section are visible before the unlock is seen. Acquire needs an acquire-barrier, release needs a release-barrier.
ABA problem with CAS. Feels right: "value is back to A, so nothing changed." Fix: it may have gone A→B→A. CAS can't tell. Use version/tag counters (double-width CAS) for lock-free structures.

Flashcards

Why can't a plain while(lock){} lock=1 implement a mutex?

The read of lock and the write are two separate instructions; a context switch between them lets two threads both see "free" and both enter — breaking mutual exclusion.

What does test_and_set(addr) do atomically?

Reads old value at addr, sets *addr = 1, returns the old value — all as one indivisible step.

In a TAS spinlock, what does a returned old value of 0 mean?

The lock was free and you just acquired it; exit the spin loop.

What does compare_and_swap(addr, expected, new) do?

Atomically: if *addr == expected, set *addr = new and return true; else leave it and return false.

Why is CAS more powerful than test-and-set?

CAS conditions the write on the current value matching an expected one, enabling lock-free data structures; TAS only flips a boolean.

What is the ABA problem?

A CAS succeeds because the value equals the expected one, but it actually changed A→B→A in between; CAS can't detect the intermediate change. Fix with version tags.

Why does Test-and-Test-and-Set reduce bus traffic?

It spins on a cheap cached read and only issues the expensive atomic RMW when the lock looks free, avoiding cache-line bouncing.

Is busy-wait spinning always bad?

No — for very short critical sections on multi-core, spinning avoids context-switch overhead and is faster than sleeping.

Why is volatile insufficient for a lock flag?

It prevents compiler caching but does NOT provide atomic read-modify-write or memory-ordering guarantees.

What memory ordering does acquire/release need?

Acquire needs an acquire barrier (no later ops move before it); release needs a release barrier (no earlier ops move after it) so critical-section writes are visible before unlock.

Recall Feynman: explain to a 12-year-old

Imagine one bathroom and a sign on the door that says FREE or BUSY. If two kids both glance at the sign at the same instant, both see FREE and both barge in — chaos. The trick: a magic door handle that, in one snap, looks at the sign AND flips it to BUSY, then tells you what the sign said before. If it said FREE, you got in. If it said BUSY, someone beat you — wait outside. Because looking and flipping happen together with no gap, two kids can never both win. That magic handle is "test-and-set." A fancier handle ("CAS") flips the sign to BUSY only if it's still exactly FREE — letting you safely change shared things without a full lock.

Connections

Critical Section Problem — the race this solves
Spinlock vs Blocking Mutex — what to do while waiting
Memory Barriers and Ordering — making the lock visible across cores
Lock-Free Data Structures — built on CAS
Semaphores — higher-level counting synchronization
Cache Coherence (MESI) — why atomics cause cache-line bouncing
Deadlock — what mutual exclusion can lead to

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, mutex ka core idea bahut simple hai: ek shared flag hota hai jo batata hai "lock free hai ya busy". Problem yeh hai ki normal code mein flag ko padhna (read) aur set karna (write) do alag-alag machine instructions hote hain. In dono ke beech mein CPU thread switch kar sakta hai. Result? Do threads dono "free" dekh lete hain, dono andar ghus jaate hain — mutual exclusion toot gaya. Yeh bug isliye chhupa rehta hai kyunki code sequential dikhta hai, par hardware level pe read aur write glued nahi hai.

Solution: hardware ek atomic instruction deta hai jo read aur write dono ko ek hi indivisible step mein kar deta hai, bus ko lock karke. test-and-set (TAS) flag ko 1 set karta hai aur uski purani value return karta hai — agar purani value 0 thi to tum lock jeet gaye, agar 1 thi to koi aur ke paas hai, spin karo. Return value hi sab kuch hai — wahi batata hai ki tumne lock liya ya nahi.

CAS (compare-and-swap) thoda powerful hai: "value ko tabhi change karo jab woh abhi bhi expected value ke barabar ho." Isse na sirf mutex banta hai, balki lock-free counters, stacks, queues bhi ban jaate hain. AtomicInteger.compareAndSet, std::atomic — sab isi pe khade hain. Bas ek catch: ABA problem — value A se B aur wapas A ho jaaye to CAS ko pata nahi chalta; iske liye version tags use karte hain.

Yaad rakhne wali baat: R-M-W must be ONE — Read, Modify, Write ko indivisible banao, bas yahi pura mutex ka raaz hai. volatile kaafi nahi hai (woh atomicity nahi deta), aur spinning hamesha bura nahi hota — chhoti critical section ke liye spin karna sleep karne se fast hai.

Test yourself — Operating Systems

Connections