Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 66 ยท Synchronization

Hardware Support, Mutexes and Spinlocks

Understand atomic instructions such as test-and-set and compare-and-swap, build a spinlock, see how a mutex sleeps instead, and when to choose which.

Software-only solutions like Peterson's algorithm are fragile on modern hardware. The practical answer is for the CPU to provide a few atomic instructions: operations that read and modify a memory location as one indivisible step. No other core and no interrupt can slip in between the read and the write. Every lock you will ever use, from a kernel spinlock to a Java synchronized block, is built from one of them.

Test-and-set

test_and_set(lock) does two things atomically: it returns the old value of the variable and sets it to true.

TEXT
function test_and_set(target):    # executes as ONE hardware step
    old = target
    target = true
    return old

A lock built on it is almost too simple:

TEXT
acquire:  while test_and_set(lock) == true: spin   # keep trying
release:  lock = false

If the old value was false, you were the one who flipped it to true, so you own the lock. If it was already true, someone else holds it and you try again.

Compare-and-swap

compare_and_swap(target, expected, new) sets target to new only if it currently equals expected, and reports whether it did so. It is the instruction behind most lock-free data structures (x86 CMPXCHG, ARM load-linked/store-conditional).

TEXT
function compare_and_swap(target, expected, new):   # atomic
    if target == expected:
        target = new
        return true
    return false

Let us build both in a simulation. We cannot give Python a real atomic instruction across threads, but our scheduler only switches at yield, so any code between two yields is atomic by construction. That is exactly what the hardware promises.

Python A test-and-set spinlock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The counter is exactly 15 and no two threads were ever inside together. The spins numbers show the price: while A is in the critical section, B and C do nothing useful but keep asking.

Compare-and-swap without a lock at all

CAS lets you update shared data optimistically: read the value, compute the new one, and try to install it. If someone changed it in the meantime, the CAS fails and you retry with fresh data.

Python A lock-free counter with compare-and-swap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

No updates are lost even though no thread ever "held a lock". A failed CAS only means another thread made progress.

Spinlock versus mutex

Both enforce mutual exclusion; they differ in what a waiting thread does.

Spinlock Mutex (sleeping lock)
Waiting thread Loops, burning CPU Is put to sleep on a wait queue
Wake-up Notices the flag change itself Woken by the releaser (needs a system call and a context switch)
Good when The lock is held for a very short time; multiple CPUs The lock may be held long; waiting is expected
Bad when The holder is descheduled; a single CPU Critical sections are tiny (switching costs more than waiting)
Used in Kernel interrupt handlers, scheduler internals Application code, most kernel code that may sleep

A single-CPU spinlock is pointless: the holder cannot run while you spin, so you spin your whole time slice. That is why many kernels compile spinlocks away on uniprocessor builds. Real mutex implementations are often hybrid: spin briefly in case the owner is about to release (Linux futexes and many language runtimes do this), then sleep.

flowchart LR
    A["Thread asks for lock"] --> B{"Lock free?"}
    B -- yes --> C["Take it and run"]
    B -- no --> D{"Lock type"}
    D -- spinlock --> E["Spin on the CPU"]
    D -- mutex --> F["Sleep on wait queue"]
    E --> B
    F --> G["Woken on release"] --> B

Both paths loop back to the question "is it free now?"; they differ only in how the waiting is spent.

A sleeping mutex, simulated

A mutex needs an owner and a queue. The thread that finds the lock taken joins the queue and stops being scheduled until the owner wakes it. The simulation counts how many scheduler turns each design wastes.

Python Spinning versus sleeping: wasted turns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The spinning version wastes many scheduler turns on waiters that can do nothing; the sleeping version wastes only one turn per waiter (the failed attempt) and then the thread leaves the run queue. On a real machine the mutex pays extra for the context switches that this model leaves out, which is why short critical sections favour spinlocks.

Never hold a spinlock while doing something that can sleep, such as waiting for disk I/O or taking a mutex. Other CPUs would spin for as long as the I/O takes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What makes test-and-set useful for building locks?

    Atomicity guarantees that exactly one of several competing threads sees the old value false, so exactly one acquires the lock.
  2. 2. A compare-and-swap fails. What does that usually mean?

    CAS only writes when the value still equals what you read. A failure signals interference, and the usual response is a retry loop.
  3. 3. When is a plain spinlock a poor choice?

    Spinning only helps if the owner is running on another CPU. Otherwise the waiter burns its time slice while the owner cannot make progress.
  4. 4. How does a mutex differ from a spinlock while waiting?

    A mutex blocks the waiting thread, freeing the CPU for other work, at the cost of a context switch on wake-up.
  5. 5. Which statement is true of a hybrid lock?

    Hybrid locks bet that the owner will release soon, spin for a short time, then fall back to sleeping.

Summary

  • Atomic instructions (test-and-set, compare-and-swap, fetch-and-add) are the foundation of all locks.
  • A test-and-set spinlock gives mutual exclusion but wastes CPU while waiting and does not guarantee bounded waiting by itself.
  • CAS enables optimistic, lock-free updates built on retry loops.
  • A mutex puts waiters to sleep; a spinlock makes them loop. Spin for very short holds on multiprocessors, sleep otherwise.
  • Never sleep while holding a spinlock.

Next: Semaphores