3 · Sharing between threads Draft

Concurrency review

11 min read

On this page

3.11 What to be able to say afterwards

Threads share memory only through the caches. Each core works on private copies, a write needs sole ownership of the line, and a line changing hands costs 50–100 ns on one socket and two to three times that between sockets.
Each core’s stores wait in a store buffer before they reach its cache. The core sees its own writes at once and other cores see them later, and that is the source of the one reordering x86 allows.
An atomic operation is never seen half done. A read-modify-write such as fetch_add or compare_exchange costs about 5 ns on a line the core owns, plus a transfer when it does not, and on x86 every one is a full barrier whatever ordering it carries.
A data race is undefined behaviour, and safe Rust cannot express one: &mut is exclusive, and sharing between threads needs Sync types built on atomics or locks.
The compiler and the CPU both reorder memory accesses that a single thread cannot tell apart. x86 lets only a later load pass an earlier store; AArch64 lets any pair of accesses to different addresses pass.
The memory model is the contract between programmer, compiler and chip. Happens-before is program order plus synchronises-with, and a load sees a store that happens-before it, or a later one.
Relaxed orders nothing beyond its own variable. Release keeps earlier accesses before a store, Acquire keeps later accesses after a load, and SeqCst adds one total order and supplies the total-order constraint used in the two-flag example. Sequentially consistent fences can also forbid the both-zero outcome; x86 commonly implements those constraints with xchg or a locked/fence instruction.
A program is correct if every outcome the model allows is acceptable. A passing test on x86 samples one chip, one compiler and one schedule; loom checks the instrumented test within its configured bounds and documented limitations.
An uncontended Mutex is one compare-and-swap to lock and one swap to unlock, with no system call. A contended one sleeps in futex and costs 5–200 µs to wake, and a preempted holder costs milliseconds to every thread queued behind it.
Lock-free means that some thread always makes progress, not that operations are fast. CAS loops retry under contention, ABA lets a CAS succeed on a value that was removed and put back, and line transfers remain the real cost.
A single-producer single-consumer ring needs no CAS and has no ABA, because each counter has one writer and slots have a fixed reuse protocol; counter wraparound still needs explicit handling.
The producer writes the slot and then stores its write index with Release; the consumer loads that index with Acquire and then reads the slot. The pair makes the slot’s write happen-before its read. The mirror pair, Release on the consumer’s read index and Acquire on the producer’s load of it, keeps a slot from being overwritten while it is still being read.
A seqlock lets many readers see a consistent latest value without writing anything shared, and each update costs every reader one line transfer.
A mutex in the hot path is a queue nobody designed. A ring between each pair of threads, one writer per line and a Release/Acquire pair at every hand-off is the queue designed on purpose.

3.12 Quiz

Two threads on cores 2 and 6 of one socket each call fetch_add(1, Relaxed) 10 million times on one shared AtomicU64. Roughly how long does it take? Would SeqCst change that on x86? What if each thread counted in its own padded counter instead?
One thread stores data and then ready, both Relaxed. Another spins on ready with a Relaxed load, then reads data. It passes a billion-round test on an x86 server. Name two ways it can still fail, and the one change that fixes both. What does the fix cost on x86?
x and y start at 0. Thread A stores x = 1 and then loads y; thread B stores y = 1 and then loads x. The stores are Release and the loads Acquire. Can both loads return 0, and can that happen on x86? Which ordering forbids it, and what does it compile to on x86-64 and AArch64?
A Mutex<u64> counts events on a hot thread, a million bumps a second, and a monitor thread on another core reads it once a second. What does each bump cost normally? What does the monitor’s read cost the hot thread? What is the worst case, and how does it happen?
A feed thread pushes 500,000 messages a second into a Mutex<VecDeque> during a burst. A convoy has formed, and every hand-over of the lock to the feed thread now costs a 10 µs wake-up. What is the most it can push per second? What happens over a 10 ms burst?
A free list of slot indices has two threads popping and one pushing. Show the ABA problem in three steps. Why does a 32-bit generation tag in the same word fix it, and what cost does the tag leave untouched?
In a single-producer single-consumer ring, which ordering goes on the producer’s store of head, the consumer’s load of head, the consumer’s store of tail, and the producer’s load of tail? What goes wrong on AArch64 if the consumer’s store of tail is Relaxed, and what does x86 do with the same code?
A seqlock holds a 32-byte top of book and its counter in one line. The writer updates it a million times a second, three readers on the same socket poll it without pause, and a write takes 30 ns from odd to even. Per update, how many line transfers do the readers pay, and at what cost each? About what fraction of reads retry? What would an RwLock cost the readers instead?

Answers

20 million increments on one line, each needing ownership, with a core sometimes getting a few done before it loses the line: about 15–50 ns per increment overall, so 0.3–1 s. That is throughput; a single increment that has to fetch the line still waits 50–300 ns, but the two threads’ waits overlap. SeqCst changes nothing on x86, because every ordering of an RMW compiles to the same lock xadd. With a padded single-writer counter per thread, each increment is a load and a store on an owned line, 1–2 ns, and the threads run in parallel: 10–20 ms, 20–100 times faster.
The compiler may emit the two stores, or the two loads, in the other order: the model allows it, and it can start happening after a compiler upgrade or a change to inlining. And AArch64 may let the store of ready leave the buffer before the store of data, and may serve the load of data before the load of ready. The fix is Release on the store of ready and Acquire on its load. On x86 it costs no instruction at all, since both stay plain movs; it costs only the compiler’s freedom to reorder.
Yes. Nothing links the two threads: each load reads the initial value, not the other thread’s store, so no Release/Acquire pair forms and the model allows both to be 0. x86 does it, because each store is still waiting in its own core’s buffer when the other core’s load reads the cache. SeqCst on all four accesses forbids it: in the single total order one store comes first, so the other thread’s later load must see it. On x86-64 the SeqCst stores become xchg, 20–40 cycles plus the drain, and the loads stay mov; on AArch64 they are stlr and ldar.
Normally both locked instructions hit a line the hot core already owns: 10–20 ns a bump, more if stores are pending. The monitor’s read takes the line away, so the hot thread’s next lock pays one transfer, 50–100 ns, once a second, which is negligible. If the two collide, the hot thread’s CAS fails and it spins, and the monitor’s short hold usually ends within the spin. The worst case is the monitor being preempted while it holds the lock. The hot thread spins its hundred rounds, sleeps in futex, waits out the monitor’s slice of 1–4 ms, and wakes 5–200 µs after the unlock: a max of milliseconds, caused by a thread that does almost nothing.
One push per 10 µs is 100,000 a second. Messages arrive at 500,000 a second, so the backlog grows by 400,000 a second. After a 10 ms burst, about 4,000 messages are waiting, and at 100,000 a second they take 40 ms to drain, so the last message of the burst waits about 40 ms. The critical section itself takes 50 ns; the wake-up sets the rate.
Popper 1 reads head = A and next[A] = B, and is delayed. Popper 2 pops A and then B, and the pusher pushes A back, so head is A again with next[A] pointing past B. Popper 1’s CAS from A to B succeeds, because head equals A. It returns A, which was free, so popper 1 is fine; but head is now B, which popper 2 still owns, so B is owned and free at once, and the next pop hands it to a second owner. With a tag, every successful CAS also increments a generation in the same word, so popper 1’s expected value (g, A) no longer matches (g + 3, A), and its CAS fails and retries; a false match needs 2³² changes inside one delay. The tag leaves the shared line alone: the head still moves between three cores, 50–100 ns an operation when they alternate, plus retries in a burst.
Release, Acquire, Release, Acquire. If the consumer’s store of tail is Relaxed, AArch64 may make it visible before the consumer’s read of the slot has completed. The producer then sees room and overwrites the slot, and the consumer reads the new message where the old one was, losing the old one. x86 never lets a load be overtaken by a later store, so the hardware hides the bug, but the compiler may still move the read after the store, and under the model the two plain accesses to the slot are now a data race, which is undefined behaviour.
Each update’s first store takes the line back, invalidating three copies; the writer’s store buffer absorbs that request. Each reader’s next read then misses: three transfers per update, 50–100 ns each, one per reader. The counter is odd for 30 ns of every 1,000, so about 3–5% of reads overlap a write and retry, the read’s own duration included. An RwLock makes every read lock and unlock an RMW on the shared state word, so the readers bounce that line among themselves on every read, 50–100 ns each time, even while the book is not changing, and the writer must wait for readers to leave before it can write.

3.11 What to be able to say afterwards

3.12 Quiz

Answers

Further reading