Appearance
2.4.2 — How Locks Are Built
2.4.1 ended with a bug that atomic instructions cannot fix. The photo-upload service keeps two numbers: how many photos it has received, and how many bytes they added up to. Each number on its own was updated atomically. But a dashboard reading both could catch the moment between the two updates, and compute an average photo size that never existed.
The two updates must happen as one. Nothing may read or write either number while one thread is halfway through. The tool for that is a lock, also called a mutex, short for mutual exclusion: at most one thread may hold it at a time. A thread locks it before the critical section and unlocks it after. Any other thread that tries to lock it meanwhile has to wait.
This page builds a lock from nothing, twice. The first version wastes a CPU core while it waits. The second asks the kernel to put the waiting thread to sleep, which is how real locks work. Then it covers semaphores, condition variables, and the locks the kernel uses on itself. How to use locks well in application code, which ones to pick and what to hold them across, is in 9.5.2. This page is how they work.
1. A lock is just a number
Here is the idea. Keep one shared number. It is 0 when the lock is free and 1 when it is taken. To take the lock, change it from 0 to 1. To release it, set it back to 0.
The hard part is "change it from 0 to 1". If a thread checks "is it 0?" and then writes 1, that is a read followed by a write, and another thread can slip in between them. Both see 0, both write 1, and both believe they hold the lock. That is the very race we are trying to stop.
2.4.1 gave us the answer: compare-and-swap does "change it from 0 to 1, but only if it is 0" as one indivisible step. Exactly one thread can win that swap.
Here are two complete locks guarding the upload count and the byte total. Four threads each record 50 uploads, and each update is made slow on purpose, so that threads really do have to wait for each other.
ts
// two-locks.ts — a spinning lock and a sleeping lock, guarding the upload count and total bytes
import { Worker, isMainThread, workerData } from "node:worker_threads";
const FREE = 0, TAKEN = 1, TAKEN_WITH_WAITERS = 2;
class SpinLock {
constructor(private cell: Int32Array) {}
lock(): void {
while (Atomics.compareExchange(this.cell, 0, FREE, TAKEN) !== FREE) {} // (1) try, try, try…
}
unlock(): void {
Atomics.store(this.cell, 0, FREE); // (2)
}
}
class SleepLock {
constructor(private cell: Int32Array) {}
lock(): void {
let c = Atomics.compareExchange(this.cell, 0, FREE, TAKEN); // (3) fast path
if (c === FREE) return;
do {
if (c === TAKEN_WITH_WAITERS ||
Atomics.compareExchange(this.cell, 0, TAKEN, TAKEN_WITH_WAITERS) !== FREE)
Atomics.wait(this.cell, 0, TAKEN_WITH_WAITERS); // (4) sleep in the kernel
} while ((c = Atomics.compareExchange(this.cell, 0, FREE, TAKEN_WITH_WAITERS)) !== FREE);
}
unlock(): void {
if (Atomics.exchange(this.cell, 0, FREE) === TAKEN_WITH_WAITERS) // (5)
Atomics.notify(this.cell, 0, 1); // (6) wake one sleeper
}
}
const pause = (ms: number) => Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, ms);
if (isMainThread) {
for (const kind of ["spin", "sleep"]) {
const mem = new Int32Array(new SharedArrayBuffer(12)); // [lock, uploads, bytes]
const cpu0 = process.cpuUsage();
const t0 = performance.now();
await Promise.all([1, 2, 3, 4].map(() => new Promise((done) =>
new Worker(new URL(import.meta.url), { workerData: { mem, kind } }).on("exit", done))));
const wall = performance.now() - t0;
const cpu = process.cpuUsage(cpu0);
console.log(`${kind}: uploads ${mem[1]}, bytes ${mem[2]}, wall ${wall.toFixed(0)} ms, ` +
`CPU used ${((cpu.user + cpu.system) / 1000).toFixed(0)} ms`);
}
} else {
const { mem, kind } = workerData as { mem: Int32Array; kind: string };
const lock = kind === "spin" ? new SpinLock(mem) : new SleepLock(mem);
for (let i = 0; i < 50; i++) {
lock.lock();
mem[1] += 1; // (7) two updates that must stay together
pause(2); // pretend the update takes a while
mem[2] += 1000;
lock.unlock();
}
}
// Printed on an 8-core Windows laptop (a second run gave 7,828 ms and 438 ms of CPU):
// spin: uploads 200, bytes 200000, wall 2713 ms, CPU used 8219 ms
// sleep: uploads 200, bytes 200000, wall 2990 ms, CPU used 359 msBoth locks gave the right answer: 200 uploads and exactly 200,000 bytes. Line (7) updates two plain, non-atomic numbers, with a deliberate pause in between, and the lock still kept them together. Now look at the last column. The spinning lock burned over 8 seconds of CPU time. The sleeping lock used about 0.4 seconds, for the same work in about the same wall-clock time. The next two sections explain both numbers. (The wall time is longer than 200 × 2 ms because Windows sleeps in steps of about 15 ms, so each "2 ms" pause lasted longer. That does not change the comparison.)
2. The spinlock, and why it wastes a core
The SpinLock is the simplest possible lock.
(1)To lock, try to swap the cell fromFREEtoTAKEN. If the swap fails, someone else holds the lock, so try again, immediately, forever, until it works.(2)To unlock, writeFREE. The atomic store also acts as a barrier (2.4.1), so every write made inside the lock is visible to the next thread that takes it.
A lock that waits by looping like this is a spinlock. It is correct. But look at what the waiting threads are doing. While one thread holds the lock, the other three are each running line (1) millions of times a second, on their own cores, achieving nothing. That is where the 8 seconds of CPU went: three cores were kept completely busy for the whole run, just asking "is it free yet?".
That is not always wrong. A spinlock is the right tool when the lock is held for a very short time, a few hundred instructions, and every waiting thread has its own core. Then spinning for a moment is cheaper than the alternative, which is a trip into the kernel to go to sleep and another trip to be woken up. The kernel uses spinlocks for exactly such short sections of its own code (section 7).
It is badly wrong in two cases:
- The lock is held for a long time, as in our demo. Every waiter burns a whole core for the entire wait.
- There are more waiting threads than cores. A spinning thread may be using the very core that the lock holder needs in order to finish. The holder cannot run, so it cannot release the lock, so the spinner spins until the scheduler happens to preempt it. On a single-core machine a spinlock wastes an entire time slice every time.
So for ordinary programs we want a lock that makes a waiting thread stop running until the lock is free.
3. The sleeping lock: let the kernel park the waiter
Only the kernel can stop a thread from running and start it again later (2.2.1 showed the blocked state). So a sleeping lock must, at some point, ask the kernel: "put me to sleep until this lock is released". But system calls cost time (2.1.2), and most of the time a lock is free when you ask for it. Paying for a system call on every lock would make every lock slow.
Linux solved this in 2002 with the futex, short for fast user-space mutex. The idea is to split the work:
- The fast path stays in user space. If the lock is free, take it with one compare-and-swap, with no system call at all. This is the common case.
- Only the slow path enters the kernel. If the lock is taken, the thread makes a
futexsystem call meaning "put me to sleep, but only if this number still equals the value I just saw". The kernel keeps a wait queue of sleeping threads for each such number. - The unlocker wakes a sleeper only if there is one. If nobody is waiting, unlocking is again one atomic instruction.
The check "only if this number still equals the value I saw" matters a lot. Without it, the lock could be released in the tiny gap between a thread deciding to sleep and actually falling asleep. That thread would then sleep forever, waiting for a release that already happened. The kernel does the check and the sleep together, so that gap cannot exist.
JavaScript's Atomics.wait and Atomics.notify have exactly these meanings, which is why our SleepLock reads like a futex lock. It uses three states, not two, so that the unlocker knows whether anyone is sleeping:
| Value | Meaning |
|---|---|
FREE (0) | nobody holds it |
TAKEN (1) | held, and nobody is waiting |
TAKEN_WITH_WAITERS (2) | held, and at least one thread may be asleep |
Now the marked lines:
(3)The fast path. Try to swapFREEtoTAKEN. If it worked, we have the lock, with no system call. In a lightly loaded program, almost every lock is taken right here.(4)The slow path. The lock is held. We mark itTAKEN_WITH_WAITERS, so the holder will know to wake someone, and callAtomics.wait. It means "put this thread to sleep, but only if the cell still holdsTAKEN_WITH_WAITERS". When we are woken, the loop tries to grab the lock again, and goes back to sleep if someone else got there first.(5)To unlock, swap the cell toFREEand look at what it was before.(6)If it wasTAKEN_WITH_WAITERS, someone may be asleep, soAtomics.notifywakes one of them. If it was plainTAKEN, nobody is waiting, and unlocking was a single atomic instruction.
That explains the CPU column. The three waiting threads spent the run asleep, using no CPU at all, instead of spinning. The 0.4 seconds is the real work plus the cost of starting four workers.
This is how real locks work. The pthread_mutex that C programs use on Linux is built on futexes, and so are the locks inside Java, Go and most other runtimes on Linux. Windows has its own equivalent, WaitOnAddress.
Spin a little, then sleep
Real lock implementations often combine the two ideas. When the lock is taken, they spin for a short moment first, because the holder may be about to release it, and a short spin is cheaper than a sleep and a wake-up. If the lock is still taken after that, they sleep. This is called an adaptive lock. The length of the spin is tuned to be about the cost of the system calls it might save.
4. What a lock costs
These figures are rough orders of magnitude on a modern machine. They are worth knowing because they decide how you design.
| Situation | Rough cost |
|---|---|
| Taking a free lock, same core as last time | about 10–20 ns |
| Taking a lock whose cache line is on another core | about 50–100 ns |
| Waiting for a held lock, with sleep and wake-up | several µs, plus the wait |
The first row is one compare-and-swap. The second is that same instruction, plus the cache line moving between cores (2.4.1). The third includes two system calls and a context switch. That is why a lock that is rarely fought over is almost free, and a lock that many threads fight over all the time is expensive no matter how it is built. The cost of a lock is almost entirely the cost of contention.
Why a busy lock caps your speed-up
There is a second, deeper cost. A lock lets one thread through at a time, so the code inside it runs one thread at a time, however many cores the machine has. That part of the work cannot be sped up by adding cores. In 1967 the computer architect Gene Amdahl turned this into a formula now called Amdahl's law. If a fraction s of the work must run one thread at a time, then with n cores the best possible speed-up is
\text{speed-up} = \frac{1}{s + \dfrac{1 - s}{n}}
Read it as "one divided by the serial part, plus the parallel part shared out over the cores". Try it with numbers. Suppose 10 % of each upload's work happens inside one shared lock, so s = 0.1. With 8 cores, the speed-up is 1 / (0.1 + 0.9/8) = 1 / 0.2125 \approx 4.7, not 8. With a million cores, the (1-s)/n term almost vanishes, and the speed-up approaches 1 / 0.1 = 10. Ten times faster is the ceiling, forever, because of that one lock. So the most effective thing you can do for a contended lock is to make the work inside it smaller.
5. Semaphores: counting instead of locking
A lock lets exactly one thread in. Sometimes you want to let up to N in. The upload service might allow at most four thumbnails to be made at once, so the machine is never swamped. For that, the computer scientist Edsger Dijkstra invented the semaphore in the early 1960s.
A semaphore is a protected counter with two operations:
- wait, also called
P,acquireordown: if the counter is above 0, subtract 1 and continue. If it is 0, sleep until it is not. - signal, also called
V,releaseorup: add 1, and wake one sleeping thread if there is any.
The letters P and V come from Dijkstra's native Dutch. P is usually read as probeer, "try", and V as verhoog, "increase". Start a semaphore at 4, and the first four thumbnail jobs to call wait go straight through, taking the counter to 0. The fifth sleeps. When any of the four finishes and calls signal, the counter goes back to 1, and the sleeping fifth job wakes and takes it.
The name comes from railways. A railway semaphore is the signal arm beside the track that tells a train "stop" or "go". It is there to stop two trains entering the same section of track at once. A software semaphore does the same job for threads and a limited resource.
A semaphore that starts at 1 behaves much like a lock, but with one important difference. A lock has an owner: only the thread that locked it should unlock it, and that rule is what makes priority inheritance possible (2.3.3). A semaphore has no owner. Any thread may signal it. So semaphores are also good for one thread telling another "go ahead now", such as "a photo is ready for you to process".
Underneath, a semaphore is built exactly like our SleepLock: an atomic counter for the fast path, and a futex wait queue for threads that must sleep.
Curiosity: "semaphore" in the wild. Is it a file? What is inside it? How does AWS use one for user data?
The word semaphore is used for two quite different things, and mixing them up causes confusion.
(1) The operating-system object described above. For threads inside one process, it is just a counter in that process's memory. For several processes to share one, Linux offers a named semaphore, created with sem_open("/thumbs", …). On Linux, this really does appear as a file: /dev/shm/sem.thumbs. But /dev/shm is a file system that lives entirely in memory, not on disk. The "file" holds a few bytes: the counter itself and some bookkeeping. Each process maps those bytes into its memory (2.5.4 explains mapping) and changes the counter with atomic instructions, with futexes for sleeping. So it is a file in name only. It is shared memory with a name.
(2) A marker file that a program creates on disk to mean "this step has already run". It is a do-once flag. It borrows the semaphore idea of "stop, already done", but it is an ordinary file, and the signal is simply that the file exists.
AWS uses exactly the second kind for EC2 user data, the script you give a new server to run when it first boots. The program that runs it, cloud-init, writes a marker file after each step, under a directory such as /var/lib/cloud/instances/<instance-id>/sem/. The file for the user-data step records which process ran it and when. On the next reboot, cloud-init sees the marker and skips the step. That is how "run user data once per server" works. Because the directory is named after the instance ID, a new server built from a copy of the old disk has a new ID, finds no markers, and runs its user data again.
So AWS is not tracking your script with an operating-system semaphore. It uses a marker file as a run-once flag, which people loosely call a semaphore because it plays the same "may I go ahead?" role. Same word, same idea, two different mechanisms. ⚑What is a semaphore — conceptually and technically; is it a file; what's its content; how does AWS track user-data loading through it? [EQ-39]
6. Condition variables: sleeping until something becomes true
A lock protects data. A semaphore counts. The third common need is waiting until a condition becomes true: "sleep until there is a photo in the queue". You could check the queue in a loop, but that is spinning again. The tool built for it is the condition variable.
A condition variable is always used together with a lock, and has two operations:
- wait: release the lock and go to sleep, as one step, then take the lock again on waking. Doing the release and the sleep together matters for the same reason as the futex check in section 3. If they were separate, the condition could become true in the gap, and the wake-up would be missed.
- signal or notify: wake one waiting thread, or all of them, because the condition might now be true.
This is the backbone of the producer–consumer pattern behind every work queue: the upload handler adds photos and signals "not empty", and thumbnail threads wait while the queue is empty and wake to process photos. 9.5.4 builds it.
One rule is worth burning into memory: always re-check the condition in a while loop after waking, never with an if. A thread can wake when the condition is not true. Another thread may have taken the photo between the signal and this thread getting the lock back. The standards also allow spurious wake-ups, which happen with no signal at all, because it makes the implementation simpler and faster. So the correct shape is always "while the queue is empty, wait".
Underneath, a condition variable is again a futex: a number that changes each time someone signals, and a wait queue of sleeping threads.
7. The locks the kernel uses on itself
The kernel has shared data too, such as the run queues from 2.3.3, and many cores running kernel code at the same time. It uses the same ideas, with one extra rule: some kernel code is not allowed to sleep.
Code that handles an interrupt runs at a moment the kernel did not choose, on top of whatever thread happened to be running (2.7.1 covers interrupts). It cannot go to sleep, because there is no thread of its own to put to sleep. So:
- Spinlocks protect data that interrupt code also touches. While holding one, the kernel usually turns off interrupts on that core, so that an interrupt cannot arrive and try to take the same lock on the same core, which would wait forever. Kernel spinlock sections are kept tiny.
- Mutexes protect data only touched by code that is allowed to sleep, such as code running a system call for a thread. A waiting thread sleeps, just as with a futex.
- Read-copy-update, or RCU, is used for data that is read very often and changed rarely, such as routing tables. Readers take no lock at all. A writer makes a new copy, changes it, and swaps a single pointer to it atomically. The old copy is freed only after every reader that might still be looking at it has finished. Reads become almost free, at the cost of more work for writers.
Linux also has a tool called lockdep, used while developing the kernel. It records the order in which every lock is taken and warns when two pieces of code take the same locks in opposite orders, before that ever causes a deadlock. Page 2.4.3 explains why that order matters.
What the interviewer will push on
"How is a mutex implemented?" They are checking whether you get to the hardware. A good answer: the lock is a shared number; taking it is one atomic compare-and-swap from free to taken; a thread that fails either spins or asks the kernel to sleep. The tell of real depth is the futex: no system call when the lock is free, a system call only to sleep or to wake a sleeper.
"When is a spinlock better than a sleeping lock?" When the lock is held for a very short time and each waiter has its own core, so spinning briefly is cheaper than sleeping and waking. Never on a single core, and never for long critical sections. Mentioning that interrupt code cannot sleep, so the kernel must use spinlocks there, shows you know where spinlocks really live.
"What is the difference between a mutex and a semaphore?" A mutex lets one thread in and has an owner who must unlock it. A semaphore counts up to N and has no owner, so any thread may signal it, which also makes it useful for signalling between threads. Binary semaphore versus mutex is a common follow-up: they behave alike, but only the mutex has ownership.
"Why must a condition variable wait be in a while loop?" Spurious wake-ups and stolen wake-ups: the condition may be false when the thread wakes.
"Is a semaphore a file?" This is a real curiosity question. Answer both meanings: a POSIX named semaphore appears as a tiny file in the memory-only /dev/shm, and cloud-init uses ordinary marker files on disk as run-once flags.
Something to volunteer that nobody asks for: the cost of a lock is almost entirely contention. A free lock costs one atomic instruction; a contended one costs system calls, context switches and a bouncing cache line. So the real fix for a slow lock is usually to hold it for less time, or to split the data so threads stop fighting, not a cleverer lock.
Recall
- A lock (mutex) is a shared number taken with one compare-and-swap from free to taken, so exactly one thread wins.
- A spinlock waits by retrying. It suits very short critical sections with a core per waiter, and wastes whole cores otherwise; in the demo it burned about 8 s of CPU against 0.4 s.
- A sleeping lock asks the kernel to park the waiter. The futex keeps the free-lock path in user space and enters the kernel only to sleep or wake, checking the value and sleeping as one step so no wake-up is lost.
Atomics.waitandAtomics.notifybehave the same way. - A semaphore counts up to N and has no owner; a named semaphore on Linux is a tiny file in memory-only
/dev/shm. cloud-init's "semaphores" are marker files used as run-once flags. - A condition variable releases a lock and sleeps as one step; always re-check the condition in a
whileloop. The kernel uses spinlocks where code cannot sleep, mutexes where it can, and RCU for data read far more than it is written.
Self-test: Why can a lock not be taken with a plain "check, then write"? What made the spinlock use 20 times more CPU than the sleeping lock? What problem does the "only if the value is still the same" check in a futex wait prevent? How does a semaphore differ from a mutex in ownership? Why can kernel interrupt code not use a sleeping lock?
Quiz Bank
FoundationalWhat is a mutex, and how does it prevent a race condition?
A mutex is a lock with two operations, lock and unlock, such that at most one thread holds it at a time. A thread locks it before its critical section and unlocks it after. Any other thread that tries to lock it meanwhile must wait. So only one thread runs the critical section at a time, and an update made of several steps, such as changing the upload count and the byte total, completes without any other thread seeing or changing a half-finished state.
FoundationalIf checking and taking a lock is itself a read followed by a write, how can a lock be safe?
Because taking the lock uses a hardware atomic instruction, compare-and-swap, which does "change the lock from free to taken, but only if it is free" as one indivisible step. The CPU holds exclusive ownership of the lock's cache line during the operation, so no other core can come between the check and the write. Exactly one thread's swap succeeds; every other thread sees that it failed and must wait.
AppliedWhen would you use a spinlock rather than a sleeping lock?
Use a spinlock only when the lock is held for a very short time and each waiting thread has its own core. Then a brief spin costs less than the two system calls and the context switch needed to sleep and be woken. Inside the kernel it is also required wherever code is not allowed to sleep, such as interrupt handling.
Avoid it for long critical sections, where every waiter burns a whole core, and whenever there may be more runnable threads than cores, because a spinner can occupy the core the lock holder needs to finish. Most real locks spin briefly and then sleep.
InterviewWhat is a futex, and why does it make locks fast?
A futex, fast user-space mutex, is the Linux mechanism behind almost every lock. The lock's state is a number in the program's memory. Taking a free lock is one compare-and-swap in user space, with no system call. Only when the lock is held does a thread call into the kernel. It asks to sleep only if the number still has the value it saw. The kernel does that check and the sleep together, so a release in between cannot be missed. On unlock, the thread enters the kernel only if the state shows that someone is waiting.
Since most locks are free when taken, most lock and unlock operations never enter the kernel, which makes the uncontended case cost a few nanoseconds.
InterviewHow does a semaphore differ from a mutex, and when would you use one?
A mutex allows one holder and has an owner: the thread that locked it should unlock it. A semaphore is a counter started at N, with wait, which takes one unit or sleeps if none are left, and signal, which returns a unit and wakes a sleeper. It lets up to N threads through and has no owner, so any thread may signal it.
Use a semaphore to limit how many things happen at once, such as at most four thumbnail jobs or ten database connections, or to let one thread tell another that something is ready. A semaphore that starts at 1 behaves much like a mutex but lacks ownership, so it cannot support features such as priority inheritance.
StaffA service's profile shows most threads blocked on one mutex, and adding cores makes it slower. Diagnose and propose fixes, best first.
This is lock contention. One heavily used lock serialises the work, so only one thread makes progress at a time, which is Amdahl's law: the serial fraction caps the speedup however many cores you add. More cores make it worse because each lock hand-off now moves the lock's cache line between more cores and wakes more sleeping threads, adding system calls and context switches.
Fixes, best first:
- Hold it for less time. Move expensive work, such as input and output, allocation or logging, outside the critical section, so only the shared update itself is locked.
- Split the data. Use several locks over separate parts of the data, for example one per bucket of a map, so threads stop colliding.
- Use atomics for simple values, such as counters, instead of a lock, and keep hot counters per thread.
- Use reader-friendly schemes for data read far more than written, such as a read-write lock or a read-copy-update style swap of an immutable snapshot.
- Stop sharing: give each thread its own state and combine results, or send work to a single owner thread through a queue.
Scenario Drill
DrillThe photo-upload service limits thumbnail work with a counting semaphore of 4. After a few days, thumbnail jobs stop being processed, although the machine is idle. Using this page, explain the likely bug and how to prevent it.
A semaphore has no owner, so nothing checks that every wait is matched by a signal. The likely bug is a code path that takes a unit and never returns it. A thumbnail job that throws an error, for example on a corrupt photo, exits before the line that calls signal. Each such failure permanently removes one of the four units. After four corrupt photos, the counter is stuck at 0, every new job sleeps in wait forever, and the machine sits idle.
Prevent it by always releasing in a finally block, or with a wrapper that takes the unit, runs the job and releases the unit however the job ends. Add a check that reports how many units are in use, so a leak shows up as a number climbing towards 4 long before everything stops. The same discipline applies to locks: a lock taken and not released on an error path freezes every thread that later needs it.
Next: locks fix races, but they bring a new failure. If two threads each hold one lock and each wait for the other's, both wait forever. Page 2.4.3 explains this deadlock the way an operating system sees it: the four conditions that cause it, and the four ways a system can deal with it, including the Banker's algorithm.