Building a Mutex From Scratch

Building an Operating System Kernel: Concurrency, I/O & Synchronization

Chapter 2 · Building a Mutex From Scratch

Chapter 1 ended on a deliberately uncomfortable note: "pick a safe-looking quantum" can never be a real fix. This chapter builds the actual fix — a mutex — and finds, before it even works, that the obvious first attempt at building one recreates the exact bug it's supposed to solve.

Finding 1: A Naive Lock Is Exactly as Broken as an Unprotected Counter

The obvious way to build a lock: read its current value, and if it's free, set it to held.

def naive_load_lock(cpu, lock_paddr, mem):
    cpu.registers['R1'] = mem.data[lock_paddr]          # step 1

def naive_store_lock_if_free(cpu, lock_paddr, mem):
    if cpu.registers['R1'] == 0:                     # step 2 -- a SEPARATE step
        mem.data[lock_paddr] = 1
        return True
    return False
    

Verified directly — both processes believe they hold the lock

Process A reads the lock (free) — then gets switched out before it can write. Process B reads and claims it in one uninterrupted turn. A resumes with its own stale "it was free" reading and claims it too. Both A and B now believe they hold the lock at the same time. This is exactly Chapter 1's own lost-update race, wearing a different name — a lock built from non-atomic steps provides zero real protection.

The Fix: A Genuinely Atomic Test-and-Set

def atomic_test_and_set(mem, lock_paddr):
    # ONE indivisible step -- read AND set, with no gap between them
    old = mem.data[lock_paddr]
    mem.data[lock_paddr] = 1
    return old

class Mutex:
    def __init__(self, mem, lock_paddr):
        self.mem = mem; self.lock_paddr = lock_paddr
        self.mem.data[lock_paddr] = 0

    def try_acquire(self):
        old = atomic_test_and_set(self.mem, self.lock_paddr)
        return old == 0   # True only if it was genuinely free

    def release(self):
        self.mem.data[self.lock_paddr] = 0
    

The critical difference from Finding 1's own naive version: atomic_test_and_set() is never split into two separate preemptible steps in this simulation — exactly matching how a real CPU's own hardware TAS/CAS instruction genuinely executes as one indivisible unit.

Finding 2: Real Mutual Exclusion

Verified directly — exactly one of two calls succeeds

Process X calls try_acquire(): succeeds. Process Y calls it immediately after: fails, because the lock is already held. There's no window between a read and a write for a second process to sneak into — the read is the write. After X calls release(), Y's retry succeeds.

Finding 3: The Mutex Fully Resolves Chapter 1's Own Race

Verified directly — 100 of 100, under the exact scheduler that lost updates before

The identical QUANTUM=1 preemptive scheduler that lost 100 of 200 real increments in Chapter 1's own Finding 2 now wraps each increment in mutex.acquire() (a real spin loop) and mutex.release(). Result: 100 of 100, perfectly correct. Nothing about the scheduler changed — only the increment code did.

Finding 4: Cross-Checked Against Python's Own Real threading.Lock

Is this pattern specific to this course's own toy simulation, or does it generalize to genuine, real OS-level concurrency?

Verified directly — real OS threads, the identical interleaving, the identical result

Two real Python threads are forced into the exact same interleaving as Finding 1 (via a real threading.Event handoff, not luck): unprotected, the result is 1, not 2 — a real, genuine lost update on real hardware threads. Wrapped in Python's own real threading.Lock — built on the same underlying atomic-hardware-instruction idea as this chapter's own Mutex — the result is 2, correctly. The pattern this chapter built from scratch is the same one real operating systems and real language runtimes actually use.

Where This Connects

This chapter's finding	What it connects to
A naive lock recreating the exact race it fixes	Course 1 Chapter 7's own double-enqueue bug — a fix built the wrong way can reintroduce the exact failure it was meant to prevent
Atomicity as the entire mechanism	Course 1 Chapter 5's own `context_switch_fixed()` — both rely on one operation completing as a genuinely indivisible unit
Real threading.Lock cross-validation	Building a Database Engine's own Transactions & Concurrency Chapter 5 — that course used real Python threads for its own genuine, measured deadlock the same way this chapter does for a lost update
A single shared physical frame as the lock	Chapter 1's own shared page — reused directly as the storage location for the lock variable itself

Hands-On Exercises

Exercise 1

Call release() twice in a row on an already-free lock, then investigate what happens if release() is called by code that never actually held the lock, while a legitimate holder is still mid-critical-section. Report both outcomes and explain the real risk.

📄 View solution

Exercise 2

Have three processes call try_acquire() on the same lock in a row. Confirm mutual exclusion still holds with three competitors, not just two, and explain why nothing in try_acquire() needed to change to support this.

📄 View solution

Exercise 3

Run two processes against a shared counter where one correctly uses ACQUIRE/RELEASE and the other skips the lock entirely. Measure whether real updates are still lost, and explain what this reveals about what a mutex actually protects.

📄 View solution

Chapter 2 Quick Reference

Atomic test-and-set: read AND set as one genuinely indivisible step — the entire mechanism a mutex depends on
Verified Finding 1 (bug): a lock built from two separate, preemptible steps has exactly the same lost-update shape as an unprotected counter
Verified Finding 2: real mutual exclusion — exactly one caller ever successfully acquires a held lock
Verified Finding 3: the mutex fully resolves Chapter 1's own race under the identical preemptive scheduler
Verified Finding 4: the identical pattern holds on real OS threads with Python's own real threading.Lock
Golden rule: a mutex only protects code that actually calls it — every accessor of shared data has to agree to go through the same lock, or the protection is an illusion
Next chapter: Semaphores & the Producer-Consumer Problem — a real semaphore built from this chapter's own mutex