Synchronization 4: Monitors, Readers/Writers, Process Structure

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

CS162 Lecture 9 - Synchronization 4: Monitors and Readers/Writers, Process Structure

This lecture finishes the synchronization arc by driving one hard problem all the way to a correct solution: the readers/writers problem, solved with a monitor. It is the example that shows why a lock plus condition variables is so much cleaner than raw semaphores. The second half zooms out from the primitives to the container that holds them - the structure of a real process: how each user thread is paired with a kernel thread and stack, how the kernel lays those out in memory, and how a timer interrupt turns that structure into scheduling (the next topic).

Recap: atomic instructions build locks

Everything here rests on hardware atomic read-modify-write instructions. Each one grabs a memory value and updates it in a single, uninterruptible step.

The four building blocks: test&set (read the old value, store 1), swap (exchange), compare&swap (store only if the value matches), and load-linked/store-conditional. From these you can build any lock.

With test&set (or compare&swap) you build a lock that does not busy-wait: a short guard protects the lock's own metadata, and a thread that finds the lock busy is put on a wait queue and put to sleep, then handed the lock directly on release. Real systems (Linux futex) take this further with a three-state lock - UNLOCKED, LOCKED, CONTESTED - so the uncontended acquire and release are just a compare&swap in user space and only contention ever enters the kernel.

Locks give mutual exclusion, but they cannot express a richer rule like "many readers or one writer." For that we need to sleep inside a critical section, which is exactly what monitors add.

Monitors: a lock plus condition variables

A monitor is a lock plus zero or more condition variables, used to manage concurrent access to shared data. It is less a data structure than a programming paradigm - a disciplined way of thinking.

A condition variable is a queue of threads waiting for something to become true while inside the critical section. Its whole purpose is to let a thread go to sleep holding the lock - and have the lock quietly released under the covers so others can make progress, then re-acquired before the sleeper wakes.

≡

The three condition-variable operations

• wait(&lock) - atomically release the lock and sleep on this condition variable; re-acquire the lock before returning. You must pass the lock so the release can happen atomically with going to sleep.
• signal - wake one waiter (if any) on this condition variable.
• broadcast - wake all waiters on this condition variable.
• Golden rule - always hold the lock when performing any condition-variable operation.
• Signaling an empty condition variable is a no-op - if nobody is waiting, nothing happens. This is a crucial, defining property (and the reason semaphores cannot stand in for condition variables - see below).

This is precisely what a semaphore cannot do. If you grab a lock and then call a semaphore's P, you sleep while still holding the lock and deadlock the system. Condition variables are designed so that going to sleep releases the lock for you.

The Mesa monitor pattern

There are two flavors of monitor, differing only in what happens on signal. Hoare monitors transfer the CPU immediately to the woken thread; they have elegant mathematical properties but are hard on the cache and the scheduler. Mesa monitors (from Xerox PARC's Mesa OS) simply move the woken thread to the ready queue and keep running. Mesa is what every real system uses, so it is what this course uses.

The canonical Mesa monitor skeleton. Enter by acquiring the lock and looping on a condition; leave by acquiring the lock, updating state, signaling, and releasing.

lock

while (need to wait) {

condvar.wait(); // check/update state; sleep if not ready

}

unlock

 

do something (no need to wait now)

 

lock

condvar.signal(); // check/update state, wake a waiter

unlock

The single most important idea is the while loop. Under Mesa semantics, a signal only makes you runnable - by the time you actually reacquire the lock and return from wait, another thread may have slipped in and changed things back. So on every wake-up you recheck the condition; you only leave the loop when you hold the lock and the condition holds.

⚠

Fool yourself: you hold the lock the whole time

While programming, think of yourself as holding the lock across the entire region between acquire and release - even while asleep inside wait. None of the code you see on the screen ever runs without the lock. (Under the covers wait really does release and reacquire the lock, but you should not reason that way.) This is what makes monitors powerful: because you "always" hold the lock, you can inspect several shared variables at once and know nobody can disturb them between your checks.

?On exit, signal one waiter or broadcast to all?

1Only one waiter can possibly proceed (e.g. one writer)→cond_signalWaking more just makes them recheck and sleep again - wasteful.

2Several waiters can proceed together (e.g. many readers)→cond_broadcastAll of them are now allowed in, so wake them all.

3Waiters of different classes share one condition variable→cond_broadcastA single signal might reach the wrong class; broadcast and let each thread's entry check sort it out.

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

The readers/writers problem

Consider a shared database with two classes of users. Readers never modify it; writers read and modify it. The access rules: any number of readers may be active at once, or a single writer, but never both. A writer mid-update can leave the database temporarily inconsistent, so no reader (and no second writer) may be anywhere near it.

Many readers or a single writer, never both. A single lock on the whole database would be wrong - it would also block a second reader, and we explicitly want concurrent readers.

A single lock is insufficient: grab it to read and no other reader can get in, yet we specifically want many concurrent readers. We need something that distinguishes the two classes - a monitor with two condition variables.

The solution: state and structure

The monitor needs to track who is where. That is four integers and two condition variables, all guarded by one lock.

The complete state: counts of active/waiting readers and writers, plus one condition variable per class. The reader and writer each 'check in', access the database, then 'check out' and wake whoever should go next.

#

The monitor's state variables (all start at 0)

• AR - active readers (readers currently in the database).
• WR - waiting readers (readers ready but blocked).
• AW - active writers. Its maximum possible value is 1.
• WW - waiting writers (no upper bound).
• okToRead, okToWrite - the two condition variables threads sleep on.

The structure of each side is symmetric: wait until it is safe to enter, access the database, then check out and wake whoever should run next. This particular solution gives writers priority - a reader defers to any waiting writer. That is a deliberate choice (writers are usually rarer, and readers usually want the freshest data), and we will see later it is not the only option.

The reader

A reader waits while any writer is active or waiting, becomes an active reader, releases the lock so other readers can enter too, then on exit wakes a writer only if it was the last reader out.

Reader() {

acquire(&lock);

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

WR++; // I am now a waiting reader

cond_wait(&okToRead, &lock); // sleep (lock released under the covers)

WR--; // woke up, no longer waiting

}

AR++; // now active

release(&lock); // let other readers check in too

 

AccessDatabase(ReadOnly);

 

acquire(&lock);

AR--; // no longer active

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

cond_signal(&okToWrite); // wake exactly one writer

release(&lock);

}

Three subtleties are worth pausing on:

• Why increment WR only inside the loop? WR counts readers asleep on the queue. You bump it right before wait and drop it right after, so it is an exact count of sleepers, not of readers loitering outside.
• Why release the lock before AccessDatabase? So that other readers can pass through the entry check and read concurrently. The monitor guards the bookkeeping, not the reading itself.
• Why is AR++ safe without extra care? It is a shared variable, but we do it inside the critical section with the lock held, so there is no race.

On exit, if we are the last reader (AR == 0) and a writer is waiting, we wake one writer. Otherwise there is nothing useful to do - any remaining reader will handle the wake-up when it leaves.

The writer

A writer waits while any reader or writer is active, becomes the single active writer, and on exit prefers to hand off to another writer (signal one), falling back to broadcasting all waiting readers.

Writer() {

acquire(&lock);

while ((AW + AR) > 0) { // safe to write? no, users are active

WW++;

cond_wait(&okToWrite, &lock);

WW--;

}

AW++; // now the one active writer

release(&lock);

 

AccessDatabase(ReadWrite);

 

acquire(&lock);

AW--;

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

cond_signal(&okToWrite); // wake one writer

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

cond_broadcast(&okToRead); // wake all readers

}

release(&lock);

}

⚠

Signal one writer, but broadcast all readers

On entry a writer must not broadcast its own class - only one writer can be active, so waking several just wastes scheduler time as the extras recheck and go back to sleep. On exit it prefers another waiting writer (signal one) and only falls back to broadcast(okToRead) when there are no writers left - because many readers may proceed together, so all of them should wake.

Watching it run

Trace the sequence R1, R2, W1, R3 starting from all-zero state.

Mid-simulation: R1 and R2 read concurrently (AR=2), while W1 sleeps on okToWrite and R3 - blocked only because a writer is waiting - sleeps on okToRead. This is writer priority in action.

• R1 enters: AW + WW is 0, so it sets AR = 1 and reads.
• R2 enters the same way: AR = 2, two readers concurrent, no lock held during the actual reads.
• W1 arrives: AW + AR is 2, so it bumps WW and sleeps on okToWrite.
• R3 arrives: even though readers are active, AW + WW is now greater than zero (a writer waits), so R3 bumps WR and sleeps on okToRead. R3 defers to W1 - writer priority.
• R2 finishes: AR drops to 1. It is not the last reader, so it signals nobody and just leaves.
• R1 finishes: AR hits 0 and WW > 0, so it signals okToWrite. Under Mesa this only moves W1 to the ready queue.
• W1 runs: it returns from wait, rechecks - AW + AR is now 0 - exits the loop, sets AW = 1, and writes.
• W1 finishes: no waiting writers, but WR > 0, so it broadcasts okToRead. R3 wakes, and if there were twenty waiting readers they would each grab the lock in turn, decrement WR, increment AR, and read.

⚠

Mesa signal does not transfer control, and wake order is undefined

signal just puts the waiter on the ready queue - the signaler keeps running and even chooses when to release the lock. When the woken thread finally runs, the implementation of wait tries to reacquire the lock; if someone else holds it, the thread sleeps again - now on the lock, not on the condition variable. And which of several waiters wakes is non-deterministic - never assume writers wake in the order they slept unless you are explicitly told so.

Can readers starve? and how lazy you can be

Yes, readers can starve. With writer priority, a steady stream of arriving writers keeps AW + WW > 0, so a reader rechecking its condition never gets out of the loop. Starvation is a real risk of this design.

But Mesa's recheck discipline also makes the code remarkably forgiving. Suppose you dropped the if (AR == 0 && WW > 0) guard on the reader's exit and just always signaled a writer. You might wake a writer while readers are still present - but that writer immediately rechecks AW + AR > 0, sees the readers, and goes right back to sleep. The entry conditions are self-checking, so an over-eager or even incorrect signal cannot violate the invariant - it is only inefficient. You could even replace every signal with broadcast: wake a thousand writers and only one proceeds; the rest recheck and sleep. This laziness is the great practical advantage of Mesa scheduling; the only cost is an occasional extra trip around the loop.

One condition variable instead of two

What if we collapse okToRead and okToWrite into a single okContinue?

With one shared condition variable, both classes sleep in the same queue. A signal could reach the wrong class (a reader's signal delivered to another reader while a writer waits), so both exits must broadcast.

// reader exit

if (AR == 0 && WW > 0)

cond_broadcast(&okContinue); // must broadcast, not signal

 

// writer exit

if (WW > 0 || WR > 0)

cond_broadcast(&okContinue); // must broadcast to sort things out

It seems like it should work, but a plain signal can be delivered to the wrong class - a reader's signal reaching another reader while a writer waits, for instance. Because we no longer distinguish the queues, we must broadcast and let every woken thread's own entry check decide whether it may proceed. That is less efficient (many threads wake only to sleep again), and it no longer gives strict writer priority - but it is correct. When you get lazy about state, you sometimes have to get very lazy to stay correct.

Building monitors from semaphores is subtle

Can you implement a condition variable out of a semaphore? A lock is easy (a binary semaphore). Condition variables are not, and the reasons are instructive:

• Naive wait = P, signal = V. Sleeping on the semaphore while holding the monitor lock deadlocks - same trap as before.
• wait = release lock, P, reacquire lock; signal = V. No deadlock, but now history matters. A few signals before a wait increment the semaphore, so the later wait sails straight through without sleeping. A real monitor's wait always sleeps, and a signal to an empty condition variable does nothing. P/V are commutative; wait/signal are not.
• signal = "if the queue is non-empty, V". Closer, but semaphores do not let you inspect their queue, and there is a race between releasing the lock and the waiter's P.

A correct construction does exist (it is in some textbooks, and it turns on keeping an extra integer counter under the lock rather than trusting the semaphore's own history), but the takeaway is the hierarchy: a monitor is a distinct, higher-level abstraction, not just a repackaged semaphore.

⚠

Synchronization is the hardest topic in the course

Kubiatowicz's own aside: reading these conditions and knowing what to look for takes real practice the first few times. If it feels hard, that is expected - it settles in with exposure.

Language support for locks

The manual acquire/release discipline is fragile: any early return, longjmp, or thrown exception between them leaks the lock and can wedge the whole system. Modern languages fix this by tying the release to scope.

Language	Mechanism	What it does
C	Manual release on every exit path	You must release before each return, and setjmp/longjmp can jump past your release entirely - error-prone, worse with multiple locks.
C++ / Java	try / catch around the critical section	Catch every exception, release, and re-throw - correct but verbose.
C++	RAII guard (lock as a stack local)	The guard is released automatically on any exit from the scope - normal return or exception. Rust does the same with mutex guards.
Python	with lock: block	The lock is released however the block is left. with also cleans up files, connections, etc.
Java	synchronized keyword	Every object has a built-in lock; a synchronized method acquires it for the call. Java also exposes monitors via wait / notify / notifyAll.

The monitor discipline these encode is the whole lecture in four rules: acquire the lock before touching shared data; loop while the condition is wrong, sleeping inside the loop; on exit, update state and signal or broadcast; and always release, no matter how you leave.

Process structure: threads and kernel threads

Now step back from the primitives to the process that contains them. In the standard model (Linux, Pintos, CPython) every user thread is paired one-to-one with a kernel thread. For each thread the kernel keeps a TCB (thread control block) and a kernel stack used for system calls, interrupts, and traps. That kernel stack plus its state is often called a "kernel thread" - it is the part that can be suspended and put to sleep inside the kernel. Some kernel threads have no user side at all: they still have a TCB and stack but do work purely for the kernel and never run in user mode.

Pintos packs a thread's TCB and kernel stack into one 4 KiB page - struct thread at the bottom, stack growing down from the top. In Pintos this single struct is both the TCB and the PCB, because every process has exactly one thread.

The magic number at the boundary is a sentinel: if the kernel stack overflows it, the number gets clobbered and you get a hint that something went wrong. The practical consequence of a 4 KiB page is stark - do not run anything deeply recursive on a Pintos kernel stack.

#

Kernel per-thread footprint

• Pintos - a single 4 KiB page holds both the TCB and the kernel stack (so the usable stack is a little under 4 KiB).
• Linux - 8 KiB (two pages) per thread, with the stack and a task_struct (holding thread and optional process state) at opposite ends.

Linux uses 8 KiB per thread and one task_struct per thread; threads of the same process share address space and other state. Linux blurs the process/thread line more than the classic PCB-with-many-TCBs picture.

Traditionally a multithreaded process has one PCB per process, and that PCB points to many TCBs - one per thread. Pintos is the easy case: exactly one thread per process, so the TCB and PCB collapse into a single struct.

Kernel structure: shared code, per-thread stacks

Putting it together, the kernel holds shared code, globals, and heap for all kernel code, plus a separate kernel stack for every thread.

One kernel: shared code, globals and heap, plus a PCB per process, a TCB and kernel stack per thread. A two-threaded process has two kernel stacks. Kernel data like pipes lives in the kernel's heap and globals, not only on stacks.

A common misconception is that kernel data lives on the stack. It does not have to - the kernel has a full heap and global area, so long-lived structures like pipes are stored there and simply protected from user access.

Each user thread is backed by a kernel stack in a 4 KB page (the TCB struct). The processor registers - PC, user SP, kernel SP (K SP), privilege level - are what the kernel saves and restores to switch between these threads.

Kernel crossings and the road to scheduling

When a running user thread takes an interrupt or system call, the x86 immediately switches to that thread's kernel stack (its address sits in the TSS structure), then saves the user PC, stack pointer, and other registers onto the kernel stack. Now the CPU runs kernel code on the kernel stack; to return, it restores those saved registers and executes iret, landing back in user mode right where it left off.

Every thread that has a kernel thread is schedulable. On a timer interrupt, the handler bumps the thread's tick counters; if the thread has run too long it sets a yield flag, and on the way out of the interrupt the kernel puts the current thread back on the ready queue and calls schedule, which picks the next thread and calls switch. Because the switch swaps kernel stacks, the eventual "return from interrupt" returns onto a different thread's stack - and thread B is now running instead of thread A. That decision of who runs next is scheduling, the subject of the next lecture.

⚠

You are not expected to understand this

The classic switch routine - which returns onto another thread's stack - carried Dennis Ritchie's famous Unix V6 comment: "You are not expected to understand this." Even the authors flagged context-switch code as the trickiest thing in the kernel. Treat switch as the code you cannot get wrong.

Address space and the kernel

Every process runs in its own virtual address space, mapped to physical memory through a page table. The kernel's portion is mapped into the top of every process's address space, but flagged supervisor-only.

The kernel is mapped into the top of every process's virtual address space but marked user/supervisor = supervisor. In user mode (CPL 3) those entries fault; on a trap the CPU drops to CPL 0 and the same pages become usable. Switching processes swaps the page-table base register (PTBR).

The page table entry's user/supervisor bit decides who may touch a page. In user mode (privilege level 3) the kernel pages fault; the instant an interrupt drops the CPU to level 0, those same pages become available - so the kernel is fully protected yet always addressable. Switching which process you are in means switching the page-table base register; switching between threads of the same process does not, since they share one address space.

Recap

• A monitor is a lock plus one or more condition variables. Always acquire the lock before touching shared data; wait inside a while loop; on a change, signal or broadcast; and you may only sleep while holding the lock.
• The readers/writers solution - four counters, two condition variables, one lock - lets many readers or one writer proceed, and shows how clean monitors are compared to raw semaphores. This version gives writers priority, so readers can starve.
• Mesa semantics (recheck on wake) make the code forgiving: an incorrect or over-eager signal is inefficient, never unsafe, because entry conditions are self-checking. With one shared condition variable you must broadcast.
• Condition variables are not just semaphores - signal to an empty queue is a no-op and wait always sleeps, which naive semaphore constructions get wrong.
• A process is one PCB pointing at one or more TCBs; each thread has a kernel thread (TCB plus kernel stack, 4 KiB in Pintos, 8 KiB in Linux) that lets it block in the kernel independently.
• Every kernel thread is schedulable; a timer interrupt saves user state on the kernel stack, and switch returns onto the next thread's stack - which is exactly how scheduling, the next topic, works.