Synchronization 3: Atomic Instructions, Monitors, Readers/Writers

Source: UC Berkeley CS162, Fall 2020/2021 - Prof. John Kubiatowicz, Lecture 8

CS162 Lecture 8 - Synchronization 3: Atomic Instructions, Monitors, Readers/Writers

The previous lecture built locks out of disabling interrupts and pointed at hardware atomic read-modify-write as the real answer. This lecture finishes that story - it uses atomic instructions to build locks that run at user level, on multiprocessors, and that sleep instead of spinning. Then it climbs one level higher to monitors (a lock plus condition variables), the pattern that makes complex synchronization tractable, and puts them to work on the classic readers/writers problem.

Why disabling interrupts is not enough

The in-kernel lock from Synchronization 2 works by disabling interrupts around a tiny critical section that inspects a lock value. It has two fatal limits:

• Kernel only. You cannot let user code disable interrupts - a single while (true) with interrupts off would hang the machine. Wrapping it as a system call fixes safety but makes every lock operation pay the kernel-crossing tax.
• Uniprocessor only. Disabling interrupts on one core says nothing about the others. On a multicore or multi-socket machine another core is still free to charge into the critical section.

The way out is a hardware instruction that reads a memory word and writes it back atomically, so no other thread can slip between the read and the write. The hardware is responsible for making it work, including the cache-coherence work needed on a multiprocessor - and unlike disabling interrupts, it works across all the cores.

Atomic read-modify-write instructions

Every one of these is a single instruction: everything shown between the braces happens all at once, indivisibly, in a way two threads cannot interleave. On many machines it is implemented by briefly locking the memory bus (or the cache line) for the duration of one load-store.

The atomic toolkit. test-and-set is on essentially every architecture; swap and compare-and-swap are on x86; load-linked/store-conditional is the RISC (MIPS R4000, Alpha) way to build the others.

test&set(&address) { /* most architectures */

result = M[address]; // return the old value at "address"

M[address] = 1; // and set the value to 1

return result;

}

 

swap(&address, register) { /* x86 */

temp = M[address]; // exchange the register's value

M[address] = register; // with the value at "address"

register = temp;

}

 

compare&swap(&address, reg1, reg2) { /* x86 (returns old value), 68000 */

if (reg1 == M[address]) { // if memory still equals reg1,

M[address] = reg2; // store reg2 into memory,

return success;

} else {

return failure; // otherwise leave memory unchanged

}

}

 

load-linked&store-conditional(&address) { /* R4000, Alpha */

loop:

ll r1, M[address]; // load-linked

movi r2, 1; // (arbitrary computation here)

sc r2, M[address]; // store-conditional: fails if anyone

beqz r2, loop; // wrote address since the ll

}

≡

What each primitive gives you

• test-and-set - reads the old value and unconditionally writes 1. The old value tells you whether you won. Start a word at 0; if 12,000 threads all test-and-set it at once, exactly one reads back the 0, the rest read 1.
• swap - a generalized test-and-set that exchanges a register with memory.
• compare-and-swap - only writes if memory still holds an expected value. This is the powerful one - it lets you say "change X to Y, but only if nobody changed X out from under me."
• load-linked / store-conditional - the RISC decomposition: ll loads, sc stores back but fails if any other write touched the address in between, so you loop. Enough to construct the other three.

Lock-free structures with compare-and-swap

Compare-and-swap is strong enough that some shared structures need no lock at all. Consider pushing onto a singly linked list that thousands of threads share.

A lock-free push. The new object's next is set to the old head; the compare-and-swap only publishes the new head if root has not changed since we read it. If a competitor got in first, the swap fails and we retry - harmlessly.

addToQueue(&object) {

do { // repeat until no conflict

ld r1, M[root] // r1 = current head

st r1, M[object] // new object's next = old head

} until (compare&swap(&root, r1, object));

}

The loop reads the current root into r1, links the new object's next to it, then tries to swing root to point at the new object - but only if root is still r1. If a competing thread pushed first, root changed, the compare-and-swap fails, and we loop and retry. Nobody's insertion is ever lost.

⚠

Retrying is not the same as busy-waiting

The retry loop looks like spinning, but it is not the pathological busy-wait we worry about. Under zero contention it makes exactly one pass - a load, a store, and one compare-and-swap - and returns. It only re-loops when another thread actually made progress, so the system as a whole is always moving forward. That is the defining property of a lock-free algorithm.

Building a lock with test-and-set: the spinlock

Now use test-and-set to build a real acquire/release. Start the lock at 0 (free):

acquire(int *thelock) {

while (test&set(thelock)); // spin until we read back a 0

}

release(int *thelock) {

*thelock = 0;

}

If the lock is free, test&set reads 0 (so the while exits) and sets it to 1 - we hold it. If it is busy, test&set reads 1, writes 1 (no change), and we keep spinning. release just stores 0, and the next thread to test-and-set wins.

This is correct, needs no kernel crossing, and works on a multiprocessor. But it busy-waits, which is bad.

#

The cost of a spinlock

• A waiting thread burns its entire time slice - roughly 100 ms - spinning and doing no useful work, then hands the CPU to the next waiter, which spins for another 100 ms, and so on.
• Worse, the spinner steals cycles from the thread that actually holds the lock, delaying the very release it is waiting for.
• If a spinning thread has higher priority than the lock holder, it can spin forever while the holder never runs - a priority inversion (the bug behind the original Mars Pathfinder rover).

There is one honest fix for the cache traffic. Every test&set is a write, so on a cache-coherent machine the lock's cache line ping-pongs between every spinning core - ironically, all of them writing the same 1 over and over. Spinning on a plain read first avoids that:

acquire(int *thelock) {

do {

while (*thelock); // spin read-only on a cached copy

} while (test&set(thelock)); // only then attempt the write

}

This test-and-test-and-set stops the ping-ponging, but it still busy-waits. When a critical section can be long (and once you have monitors, it can be arbitrarily long), what you really want is to sleep.

A lock that sleeps, at user level

Apply the same trick the kernel lock used with interrupts: do not make the atomic operation be the lock, use it to protect the few instructions that implement the lock. Introduce a global guard variable; spin on the guard only for the handful of instructions that inspect the real lock, then either take it or go to sleep.

The guard is held only for the tiny critical section that reads and writes the lock, so the busy-wait is very short. If the lock is taken, the thread parks on the wait queue and goes to sleep, releasing the guard as it sleeps - exactly mirroring how the interrupt-based lock re-enabled interrupts on the way to sleep.

int guard = 0; // one global guard for all locks

int mylock = FREE; // one of these per lock

 

acquire(int *thelock) {

while (test&set(guard)); // short busy-wait for the guard

if (*thelock == BUSY) {

put thread on wait queue;

go to sleep() & guard = 0; // sleep AND release guard together

} else {

*thelock = BUSY;

guard = 0;

}

}

 

release(int *thelock) {

while (test&set(guard));

if (anyone on wait queue) {

take a thread off the wait queue;

place it on the ready queue;

} else {

*thelock = FREE;

}

guard = 0;

}

The guard is held for only a few instructions, so the spin is negligibly short. The expensive part - actually sleeping - happens by parking the thread on a wait queue and yielding. Note the subtlety, identical to the interrupt version: you must reset guard to 0 as you go to sleep, otherwise you would sleep holding the guard and no one could ever release the lock.

≡

Why this is the shape of a real lock

• User level in the common case - test&set runs like any arithmetic instruction; no system call is needed to grab an uncontended lock.
• Sleeps under contention - a thread that cannot get the lock is put on a wait queue, not left spinning. Going to sleep does require the kernel, but if you are about to sleep anyway, that crossing is cheap by comparison.
• One wait queue per lock - so release always knows exactly whom to wake.

Futex: fast user-space mutex

The one piece still missing is a clean interface for "put me to sleep on this memory word." Linux provides it as the futex (fast user-space mutex) system call:

int futex(int *uaddr, int futex_op, int val, const struct timespec *timeout);

FUTEX_WAIT says "put me to sleep, but only if *uaddr still equals val"; FUTEX_WAKE wakes up to val sleepers. The conditional check closes a race: if the lock is released in the window between our test-and-set and our call into the kernel, FUTEX_WAIT returns immediately instead of sleeping on a wakeup that already happened. A first cut:

acquire(int *thelock) {

while (test&set(thelock)) // got a 1? someone holds it

futex(thelock, FUTEX_WAIT, 1); // sleep while it is still 1

}

release(int *thelock) {

*thelock = 0;

futex(thelock, FUTEX_WAKE, 1); // wake one sleeper

}

This never busy-waits, and acquire can be as fast as a single atomic instruction. Its flaw is that every release makes a system call, even when nobody is waiting. A second cut adds a maybe_waiters flag so release only enters the kernel when a waiter might exist - but the clean solution is to give the lock three states and drive it entirely with atomics.

The three-state lock. UNLOCKED means free; LOCKED means one thread holds it and nobody is in the kernel; CONTESTED means someone may be asleep. release only calls into the kernel when the state was CONTESTED, so an uncontended lock never crosses into the kernel at all.

typedef enum { UNLOCKED, LOCKED, CONTESTED } Lock;

Lock mylock = UNLOCKED;

 

acquire(Lock *thelock) {

// Fast path: if unlocked, grab it outright.

if (compare&swap(thelock, UNLOCKED, LOCKED))

return;

// Otherwise mark it contested and sleep until it is released.

while (swap(thelock, CONTESTED) != UNLOCKED)

futex(thelock, FUTEX_WAIT, CONTESTED);

}

 

release(Lock *thelock) {

if (swap(thelock, UNLOCKED) == CONTESTED) // only wake if someone waited

futex(thelock, FUTEX_WAKE, 1);

}

?Which locking primitive should you build on?

A uniprocessor kernel with tiny critical sections→Disable interruptsCheapest possible, but kernel-only and useless across cores. See Synchronization 2.

A multiprocessor with many cores and roughly one thread per core, holding the lock only briefly→Spinlock (test-and-test-and-set)Busy-waiting is acceptable when there is no one else the core would run anyway; test-and-test-and-set avoids the cache ping-pong.

General user-level code where critical sections may be long→A lock that sleeps (guard variable / futex)Waiters sleep instead of burning cycles; the uncontended path stays at user level with no system call.

Production user-space mutexes on Linux→Three-state futexUncontended acquire and release are pure atomics; the kernel is touched only when a thread must actually sleep or be woken.

Pick this when: you are implementing acquire/release and choosing how a waiter should behave

From semaphores to monitors

Semaphores solved the bounded buffer, but a semaphore is doing two jobs at once - mutual exclusion (the mutex) and a scheduling constraint (the full/empty counts). That dual purpose is exactly why the solution is fragile: swap the order of two P operations and it deadlocks, and it is hard to look at the code and prove it is correct.

A monitor separates the two concerns:

• a lock for mutual exclusion, and
• one or more condition variables for the scheduling constraints.

A monitor is really a programming pattern, not just a data type. Some languages (Java) provide it natively; in C you get condition variables from the pthreads library. Once the pattern clicks, surprisingly intricate synchronization becomes easy.

Condition variables

A condition variable is a queue a thread can sleep on when the conditions are not right to proceed - and, strangely, it is used while holding the lock. It has three operations:

• Wait(&cv, &lock) - atomically release the lock and go to sleep; re-acquire the lock before returning.
• Signal(&cv) - wake one waiter, if any.
• Broadcast(&cv) - wake all waiters.

⚠

You sleep with the lock held - and that is the point

Every prior lecture said sleeping while holding a lock deadlocks the system. Condition variables are the deliberate exception: Wait releases the lock under the covers as it puts you to sleep, and re-acquires it before it returns. The rule that makes it all work is simple - you must hold the lock when performing any condition-variable operation. Program as if you hold the lock continuously from acquire to release, even across a Wait; the release-and-reacquire is invisible to you.

A synchronized (infinite) buffer

Start with half of the bounded-buffer problem: an infinite queue where a consumer must block when it is empty (no full check needed).

One lock, one condition variable. The producer signals after enqueuing; the consumer sleeps on the CV inside a while loop whenever the queue is empty. Because the lock is held throughout, the consumer can safely check the queue, sleep, wake, and re-check without anything changing underneath it.

lock buf_lock; // initially unlocked

condition buf_CV; // initially empty

queue queue;

 

Producer(item) {

acquire(&buf_lock);

enqueue(&queue, item);

cond_signal(&buf_CV); // wake a waiter, if any

release(&buf_lock);

}

 

Consumer() {

acquire(&buf_lock);

while (isEmpty(&queue)) {

cond_wait(&buf_CV, &buf_lock); // sleep until signaled

}

item = dequeue(&queue);

release(&buf_lock);

return item;

}

The consumer's pattern is the heart of every monitor: grab the lock, check a condition in a while loop, sleep if it is not satisfied, and re-check on wakeup - always holding the lock.

Mesa vs. Hoare: why while, not if

The while loop around cond_wait is not optional, and the reason comes down to what exactly happens when a thread is signaled.

The whole question is whether to guard cond_wait with while or if. The answer depends on the monitor's signaling semantics - and essentially every real operating system uses Mesa semantics, which forces the while loop.

Under Hoare semantics (named after Tony Hoare), signal immediately hands the lock and the CPU to the woken waiter, which runs right away. Nothing can change between the signal and the waiter running, so an if would suffice. It is clean to reason about but ugly to implement and bad for the cache - the signaler is forced to give up the CPU and all its cached state mid-stream.

Under Mesa semantics (named after the Xerox PARC Mesa OS), signal just moves the waiter to the ready queue and the signaler keeps running with the lock. The waiter runs "sometime later," and in that gap another thread can sneak in and invalidate the condition.

Mesa signaling puts the waiter on the ready queue and returns immediately - the signaler keeps the lock and its cache state. By the time the waiter is scheduled the condition may be false again, so it must loop back and re-check. Almost every real OS is Mesa-style.

⚠

Under Mesa semantics, guard cond_wait with while, never if

Because a Mesa signal only makes the waiter runnable, another thread can acquire the lock and consume the resource before the woken thread ever runs. If you guarded the wait with an if, the thread would fall straight through to dequeue on an empty queue. Guarding it with a while forces it to re-check the condition after every wakeup and go back to sleep if it is still false. On a Mesa-semantics system - which is all of them in practice, including pthreads and Java - always use while.

	Hoare monitors	Mesa monitors
On signal	Lock and CPU handed straight to the waiter	Waiter moved to the ready queue; signaler keeps running
Waiter runs	Immediately	Sometime later, after re-scheduling
Guard with	if is sufficient	while is mandatory (re-check on wakeup)
Cost	Extra context switches; bad for cache locality	No forced switch; signaler keeps its cache state
Used by	Mostly of theoretical interest	Essentially every real OS, pthreads, Java

The bounded buffer with monitors

With monitors the full bounded (circular) buffer is just the infinite version with a second condition variable and a full check. One lock, two condition variables - one for "buffer full," one for "buffer empty":

The pthread-style bounded buffer. Each side waits in a while loop on its own condition variable and signals the other after making progress. Far cleaner than the semaphore version because the mutual exclusion (the lock) and the scheduling constraints (the two CVs) are separated - and because the code runs entirely under the lock, nothing it checks can change underneath it.

lock buf_lock = <initially unlocked>

condition producer_CV = <initially empty>

condition consumer_CV = <initially empty>

 

Producer(item) {

acquire(&buf_lock);

while (buffer full) { cond_wait(&producer_CV, &buf_lock); }

enqueue(item);

cond_signal(&consumer_CV); // a slot filled - wake a consumer

release(&buf_lock);

}

 

Consumer() {

acquire(&buf_lock);

while (buffer empty) { cond_wait(&consumer_CV, &buf_lock); }

item = dequeue();

cond_signal(&producer_CV); // a slot freed - wake a producer

release(&buf_lock);

return item;

}

Because every check, wait, and signal runs while holding the lock, you never have to reason about anything changing between the check and the action - the thing that made the semaphore solution so easy to get wrong.

The readers/writers problem

The payoff example. A shared database has two classes of users: readers, which never modify it, and writers, which do. Many readers can safely read at once, but a writer needs exclusive access - no other writers and no readers.

Many readers may share the database concurrently; a writer must have it entirely to itself. A single lock on the database would be correct but too strict - it would forbid concurrent readers, which is the whole thing we want to allow.

A single lock around the database is too coarse: it would serialize the readers, throwing away the concurrency we care about. Instead we use a monitor whose lock guards a little bit of bookkeeping, with two condition variables. The correctness constraints:

• Readers may access the database when there are no writers.
• A writer may access it when there are no active readers or writers.
• Only one thread manipulates the shared state at a time.

≡

The monitor state

The lock protects four counters and gates two condition variables:

• AR - number of active readers (currently reading); starts at 0.
• WR - number of waiting readers (blocked); starts at 0.
• AW - number of active writers (at most 1); starts at 0.
• WW - number of waiting writers; starts at 0.
• okToRead, okToWrite - the two condition variables to sleep on.

Code for a reader

A reader checks in under the lock, sleeps on okToRead while any writer (active or waiting) is present, then releases the lock BEFORE reading so other readers can enter too. On the way out it wakes a waiting writer only if it was the last reader.

Reader() {

// Check in.

acquire(&lock);

while ((AW + WW) > 0) { // is it safe to read?

WR++; // a writer exists - wait

cond_wait(&okToRead, &lock);

WR--;

}

AR++; // now we are an active reader

release(&lock);

 

AccessDatabase(ReadOnly); // the actual read

 

// Check out.

acquire(&lock);

AR--;

if (AR == 0 && WW > 0) // last reader out, a writer waits?

cond_signal(&okToWrite); // wake one writer

release(&lock);

}

⚠

Release the lock before touching the database - the lock is meta-locking

Notice the reader releases the lock before AccessDatabase and re-acquires it afterward. The lock is not protecting the database - it is protecting the counters that decide who may enter. This is "meta-locking": the entry code checks whether your constraints are satisfied and marks you active, then hands the actual database access off with the lock released, which is precisely what lets multiple readers be in the database at the same time. A reader waits while AW + WW > 0 (writers are also prioritized: a waiting writer blocks new readers so it does not starve).

Code for a writer

A writer sleeps on okToWrite while any active reader or writer is present, takes exclusive access, and on exit gives priority to a waiting writer (signal one) but otherwise wakes ALL waiting readers with a broadcast.

Writer() {

// Check in.

acquire(&lock);

while ((AW + AR) > 0) { // is it safe to write?

WW++; // active users exist - wait

cond_wait(&okToWrite, &lock);

WW--;

}

AW++; // now we are the active writer

release(&lock);

 

AccessDatabase(ReadWrite); // the actual read/write

 

// Check out.

acquire(&lock);

AW--;

if (WW > 0) { // give priority to writers

cond_signal(&okToWrite); // wake one writer

} else if (WR > 0) { // otherwise wake the readers

cond_broadcast(&okToRead); // wake ALL waiting readers

}

release(&lock);

}

?signal one, or broadcast all?

At most one waiter can make progress (only one writer can be active)→cond_signalWaking one writer is enough - a second writer could not enter anyway, so waking it would just make it re-check and sleep.

Many waiters can proceed together (all readers can read at once)→cond_broadcastA finishing writer wakes every waiting reader so they all enter concurrently, which is the whole point of allowing shared reads.

Pick this when: a monitor thread finishes and must wake the right waiters

⚠

A mistaken broadcast is still safe under Mesa semantics

Suppose you broadcast to many waiting writers by accident. They all wake, but each must re-acquire the lock before returning from cond_wait - so they emerge one at a time. The first decrements WW, sees no active readers or writers, increments AW, and enters. Every other woken writer then re-checks its while condition, finds AW > 0, and goes right back to sleep. There is no interleaving inside the monitor because the lock serializes the check-and-update, and the while loop catches the stale wakeups. This is exactly why Mesa monitors are robust: an over-eager wake never breaks correctness, it only costs a little work.

The lecture stops here, before walking a full simulation of the state variables - that comes at the start of the next lecture.

Recap

• Disabling interrupts builds locks only in the kernel and only on a uniprocessor. Hardware atomic read-modify-write (test-and-set, swap, compare-and-swap, load-linked/store-conditional) reads and writes a word indivisibly and works at user level and across cores.
• Compare-and-swap is strong enough for lock-free structures: a linked list push that retries only when a competitor actually made progress.
• A test&set spinlock is correct but busy-waits, wasting cycles and risking priority inversion. Test-and-test-and-set fixes the cache ping-pong but still spins. Using an atomic to protect a guard variable lets the lock sleep instead, and the futex gives a three-state lock whose uncontended path never enters the kernel.
• A monitor is a lock plus one or more condition variables, separating mutual exclusion from scheduling. You use Wait/Signal/Broadcast while holding the lock; Wait releases and re-acquires the lock under the covers.
• Under Mesa semantics (which real systems use) a signal only makes a waiter runnable, so you must re-check the condition with a while loop, never an if.
• The readers/writers monitor guards four counters (AR, WR, AW, WW) and two condition variables, releasing the lock before the database access so many readers run concurrently. Writers get priority; a finishing writer signals one writer but broadcasts to all readers.