Lock Lab

A spinlock is one integer and one instruction. Chapter 13 built it that way: the lock word holds 0 when the lock is free and 1 when it's held, and a thread takes it by running compare-and-swap (CAS), "if the word still holds 0, make it 1, and tell me whether that worked", over and over until it works. That settles whether the lock is correct. It says nothing about what the waiting costs, and the cost sits somewhere the code never mentions, in the cache.

Each core keeps copies of the memory it's using in its own private cache, the L1, and it copies memory in fixed chunks called cache lines, 64 or 128 bytes depending on the processor. The lock word is one integer inside one line. Any number of cores can hold a copy of that line to read, but only one core at a time may write it, so before a core writes, every other copy has to be thrown away. A copy that has been thrown away is invalidated, and the next time its core needs the line, the line has to travel back across the chip. This lab lets you run a CAS, a spinlock and a better spinlock one step at a time and watch every one of those trips.

Each core's card shows its copy of the line, tagged with one of the four states of MESI, the coherence protocol from chapter 02. Modified (M) means this core holds the only copy and has changed it, so memory is out of date. Exclusive (E) means the only copy, unchanged. Shared (S) means several cores hold read-only copies. Invalid (I) means there's no usable copy here. The counters at the top keep the bill: a line transfer is any time the line's contents have to arrive at a core whose copy was Invalid, from memory or from another core, and an invalidation is one copy thrown away. You are the scheduler: each click runs one step of one core.

Things to try

1. A CAS succeeds, then fails

Stay in CAS ++ with two cores. Each core runs a CAS loop, the recipe from chapter 14: read x into a register called old, then try CAS(x, old, old+1). If the CAS fails, it reports the value it found, and the core retries with that.

Step A once. It reads x = 0, misses, and gets the line from memory as Exclusive, since nobody else has it. Step B once. B misses too, so A hands over a copy and both now hold it Shared. Step B again: its CAS expects 0 and finds 0, so it succeeds. B already had a copy, so it only has to send an invalidation, and A's copy turns Invalid while B's turns Modified. Now A's CAS still expects 0, and x is 1.

That's the shape of every CAS loop under contention. Each losing attempt does no useful work and still pays for a trip of the line, and it takes the line away from whoever had it. Chapter 14 counted this at eight threads: 84% of all attempts were thrown away.

2. Taking turns costs almost nothing

Press Reset. This time step A through both of its increments, four clicks, and only then step B through both of its own.

Now reset and alternate strictly, A, B, A, B, until both finish. The same four increments cost seven transfers, six invalidations and three failed CAS attempts. The atomic instructions didn't get slower. What costs is the line moving between cores, and it only moves when the cores take turns writing it.

3. A spinlock with one waiter, then two

Switch to TAS lock. The name comes from test-and-set, the classic atomic instruction that writes 1 and returns the old value. This lab writes the lock with CAS(lock, 0, 1) the way chapter 13 did, and as far as the cache is concerned the two behave the same, because both need the line in a writable state. A waiting core simply retries the CAS until it succeeds.

Step A once so it takes the lock, then step B three times while A sits in its critical section.

Now pick 3 cores, take the lock with A, and alternate B and C. Every single step is a transfer. Each failed CAS needs ownership, so B steals the line from C, then C steals it back from B,. When A finally releases, its plain store lock = 0 also needs ownership, so it has to pull the line out of whichever spinner has it at that moment.

4. Spin on a read instead

Switch to TTAS lock, short for test-and-test-and-set, and keep three cores. The only change is the first line of the loop: a waiting core reads the lock word with an ordinary load and spins while it says 1, and it tries the CAS only when the word reads 0. If the CAS then fails, the core goes back to reading.

Step A twice to take the lock. Its CAS is free, because its read got the line as Exclusive. Step B once and C once. Each misses, A writes the line back to memory and hands it over, and now all three hold it Shared.

The cost comes all at once when A releases. Step A to the end. Its store lock = 0 has to own the line, so it sends one invalidation and both spinners' copies go Invalid. Then B and C each miss and fetch the line again, both see 0, and both try the CAS. One wins. The other's CAS fails and pulls the line over one more time before it goes back to spinning. So TTAS pays a burst of traffic at each handoff, roughly two transfers per waiting core, and pays nothing while the lock is held.

5. The same locks, a hundred times each

At the bottom of the widget, leave the hold time at 10 steps and press Run. Each row lets every core take the lock a hundred times under a random scheduler, once with TAS and once with TTAS, and reports line transfers per acquisition.

Now switch the hold time to 50 steps. TAS at four cores climbs to around a hundred transfers per acquisition, while TTAS stays near six. At eight cores TTAS sits around fifteen at both 10 and 50 steps, close to two per core.

The two locks pay at different moments. TAS pays per spin, so its traffic grows with how many cores are spinning and with how long the lock is held. TTAS pays per handoff, so its traffic grows with the number of waiters and doesn't depend on hold time at all. A real critical section runs many instructions while a spin iteration is only a few, which puts real locks toward the long-hold end of this table.

What this shows

A lock is correct because of one atomic instruction, and what it costs depends on one cache line. The rule underneath every experiment here is the one from chapter 02: reads share, writes take turns. A successful CAS is a write, a failed CAS is a write as far as the cache is concerned, and the release store is a write, so all three move the line whenever another core touched it last. A spin loop that reads until the lock looks free waits on its own Shared copy and moves the line only when something has actually changed.

TTAS still has its burst at every release, and it grows with the number of waiters. Production locks go further. Backoff makes a core that just lost wait a little before retrying. A queued lock such as the MCS lock gives each waiter a flag on its own cache line and has the holder hand the lock directly to the next in line, so a release touches only one waiter. The Linux kernel's spinlock is a queued design of this kind. And for waits that could be long, the futex from chapter 13 stops spinning altogether and puts the thread to sleep.

The model here is simplified on purpose. Intel and AMD processors use extensions of MESI (MESIF and MOESI) that add a state for deciding which cache answers a request, a transfer between cores costs different amounts depending on where they sit on the chip, and real cores run at the same time instead of taking turns at your click. The lab counts trips and leaves out nanoseconds.

Where this comes from

• Chapter 13, Locking primitives, end to end, section 2, "Building a lock": the CAS spinlock this lab starts from, and what spinning costs a core.
• Chapter 14, Lock-free and wait-free programming, section 2, "Update, check, retry", for the CAS loop, and section 6, "Why the retry loop collapses", for the count of wasted attempts.
• Chapter 02, Memory hierarchy and cache coherence, section 6, "When two cores share a line": MESI and false sharing.
• Chapter 03, The memory model and atomics, section 7, "What ordering costs", where contention on one variable turns out to matter far more than the choice of memory ordering.