Synchronization 1: Concurrency and Mutual Exclusion
Source: UC Berkeley CS162, Fall 2020/2021 - Prof. John Kubiatowicz, Lecture 6
This lecture builds the machinery of concurrency from the bottom up: how the OS gives you the illusion of many threads on one CPU, and then why that illusion creates a correctness problem the moment two threads touch the same data. It ends with the first tool for fixing it - the lock.
Multiplexing the CPU: the Process Control Block
The OS keeps one Process Control Block (PCB) per process: a chunk of kernel memory describing everything the kernel needs to manage it - process state, process id, saved registers, memory limits, and the list of open files. The scheduler holds a data structure of all the PCBs and decides, for each thread, who gets the CPU next.
The context switch
Switching from one process to another means saving all of the running thread's state (registers, program counter, stack pointer) into its PCB, loading the next one's state from its PCB, and returning to user level. The save/restore happens inside the kernel, at privilege level 0; user code runs at level 3.
Every transition between user and kernel is a potentially expensive save and restore of registers, so the switch must be cheap relative to the work done between switches.
- Switch frequency - a typical OS like Linux context-switches every 10 to 100 ms.
- Overhead - a full process switch costs on the order of 3 to 4 microseconds; a thread switch within a process is much cheaper, roughly 100 ns (about 30-40x cheaper than a process switch).
- Target - keep switching overhead under 10% of total time, so most cycles do useful work.
If you switch back and forth too rapidly, the blue "actually executing user code" slices shrink to a vanishing fraction of the timeline and the machine spends all its time on overhead, making no forward progress. That is a form of thrashing.
Lifecycle of a process or thread
A process (and each thread inside it) moves through a fixed set of states:
new (just after fork), ready (runnable, waiting for the CPU),
running (currently on a core), waiting (blocked on I/O or an event), and
terminated (after exit).
We do not free a process the instant it exits. Its parent still needs to collect the exit result, so the entry lingers in the terminated-but-not-reclaimed state. That is a zombie process.
Scheduling: all about queues
A non-running process sits on some queue. The ready queue holds threads waiting for the CPU; each device (disk, network) has its own I/O queue of threads blocked on it. PCBs migrate from queue to queue: a thread whose time slice expires goes back on the ready queue; a thread that issues I/O goes on that device's queue until the I/O completes.
Threads: the unit of concurrency
A process is a protected environment (address space, open files) plus one or more threads. Threads encapsulate concurrency - the active part - while the address space is the passive part shared among them. Within one process, all threads share the heap, global variables, and code; each thread has its own Thread Control Block (TCB), saved registers, and stack.
Why multiple threads per address space? Sharing. Threads in the same process can cooperate through shared memory directly, with no IPC.
Running a thread and the dispatch loop
Conceptually the OS is an infinite dispatch loop: run a thread, choose the next thread, save the current thread's state, load the new thread's state, and repeat forever. To run a thread you load its registers, PC and stack pointer; if you are also changing process, you install its address space (page table) first, then jump to the PC.
A key fact drives everything else: the OS and the thread it manages run on the same CPU. When the OS runs, the thread does not, and vice versa. So starting a thread means the OS gives up control of the CPU - which raises the question of how it ever gets control back.
Internal events: cooperative yielding
The old answer (Windows 3.1, early Macintosh) was cooperative multitasking:
each thread voluntarily gives up the CPU by calling yield. This works only if
everyone cooperates - one buggy program stuck in a loop froze the whole machine.
Voluntary yields happen when a thread blocks on I/O, waits for another thread, or
explicitly calls yield (sched_yield / pthread_yield).
Every user thread has a matching kernel stack (a "kernel thread"). On a trap, the kernel switches to that kernel stack rather than trusting the user's stack pointer - because the kernel never trusts the user. If user code put a null in its stack pointer and trapped, running on that stack would crash the kernel. The kernel's job on every system call is to check what the user gave it.
The switch() routine
switch(curThread, newThread) saves every register of the current thread into
its TCB (including the stack pointer and return PC), then loads the next thread's
registers back. Because the switch changes the stack pointer partway through,
the return at the end of switch returns onto a different thread's stack -
which is exactly how control flows from thread S into thread T and back.
A thread is therefore a self-contained snapshot - TCB plus user stack plus kernel stack - that you can pull off the ready queue, park on a wait queue, and revive later.
switch is the code you cannot get wrongswitch sits at the core of the kernel and has no exhaustive test. Forget to
restore one register and you get intermittent, unexplained failures depending on
whether user code happened to use it. The cautionary tale: DEC's Topaz kernel
saved one instruction in switch by assuming the kernel stayed under 1 MB. It
was documented and correct - until years later the kernel grew past 1 MB and
started failing bizarrely. Design for simplicity; a micro-optimization here has
to be truly worth it.
Threading models and their cost
The model discussed above is one-to-one: every user thread has a kernel stack, so a blocking I/O call parks just that thread while the others keep running. This is what Linux and Pintos do. Alternatives trade safety for speed:
| Model | How it works | Trade-off |
|---|---|---|
| One-to-one | Each user thread has its own kernel thread/stack (Linux, Pintos default). | A blocking call parks only that thread; the rest keep running. Requires a kernel crossing to switch. |
| Many-to-one | Many user threads multiplexed onto one kernel thread by a user-level library ("green threads", early Java). | Switching is very fast (no kernel crossing), but if any thread blocks in the kernel, all of them stall. |
| Many-to-many | A small pool of kernel threads backs many user threads. | Combines fast user-level switching with real blocking; needs library support, hidden from the programmer. |
The same trade-off explains why processes are heavier than threads:
- Switch overhead - low between threads of one process; high between processes.
- Protection - low between threads (by design, they share memory); high between processes (by design, to isolate them).
- Sharing - cheap inside a process (shared memory); across processes needs IPC.
- Parallelism - only appears with multiple cores; a single core gives concurrency, not parallelism.
External events: preemption by interrupts
Cooperative yielding cannot handle a thread that never does I/O and never yields
(a tight compute loop). The fix is external events - interrupts from
hardware, especially a timer programmed to fire every 10 to 100 ms. An
interrupt is a hardware-invoked context switch: it stops the user code, traps
into the kernel, and the kernel can then run_new_thread and switch.
- Devices raise interrupt lines; the controller chooses which request to honor.
- The interrupt mask enables or disables specific interrupts; the CPU can disable all of them with a single internal flag while handling one.
- A priority encoder picks the highest-priority enabled interrupt.
- The non-maskable interrupt (NMI) cannot be disabled - it is the "power is about to fail, act now" line.
If external events happen often enough, the CPU is shared fairly whether or not threads cooperate.
Correctness: the scheduler is out to get you
Once threads run concurrently, the scheduler may run them in any order and switch at any time. Independent threads are fine; threads cooperating on shared data are not.
Treat the scheduler as a malicious device whose only goal is to pick the interleaving that exposes your worst concurrency bug - and to do it at the worst possible moment. The bad interleaving may show up once in a million runs, at 3am, when a plane is in the air. Your only defence is to design code that is correct by construction, regardless of the schedule.
The race condition
Consider a bank server handling deposits from many ATMs, one thread per request.
You deposit $10 while your parents deposit $100 into the same account. Each
thread does load balance, add, store balance. If they interleave -
the account ends at $10: the $100 deposit vanished. This is a race
condition - two threads access the same data at the same time and at least one
writes.
- Atomic operation - an operation that always runs to completion or not at all, indivisible, and whose state cannot be modified partway by anyone else. Without atomics, threads cannot cooperate at all. On most machines, plain memory loads and stores of a word are atomic (a double-precision load/store may not be).
- Synchronization - using atomic operations to get cooperation between threads.
- Mutual exclusion - ensuring only one thread does a particular thing (enters a particular region) at a time.
- Critical section - the piece of code that only one thread at a time may execute.
Locks and critical sections
A lock enforces mutual exclusion. You acquire before entering a critical
section and release when done; if the lock is already held, acquire waits.
Correctness here fundamentally involves waiting - you deliberately do not run
right away, so that the atomic sections do not interleave.
The banking bug is fixed by wrapping the load-add-store in the same lock. The key word is same: every method that touches the shared data (deposit, withdraw) must use the same lock, or the mutual exclusion has a hole. Fixing concurrency starts as an analysis problem - find the shared data, find the critical sections, and put the right lock around them.
Putting a lock around i++/i-- removes the race (no two threads update i
mid-flight), but a program whose threads just increment and decrement a shared
counter forever is still meaningless. Removing the race is necessary, not
sufficient - the logic above the lock still has to make sense. A cleaner use is
one lock at the root of a shared data structure (for example a balanced search
tree), so every insert/lookup sees a consistent structure.
Getting this analysis wrong is not academic. The Therac-25 radiation therapy machine used inconsistent synchronization on operator input; when an operator typed too fast, a race set the wrong beam configuration and patients received lethal radiation doses. The Mars Pathfinder priority inversion and Toyota unintended-acceleration cases were synchronization failures too. Take synchronization seriously.
Recap
- The OS multiplexes the CPU by unloading the current thread and loading the next,
either voluntarily (
yield, blocking I/O) or involuntarily (interrupts). - A thread's TCB plus its two stacks hold its complete state, so it can be parked on a queue and revived later.
- Concurrency creates non-determinism; cooperating threads on shared data can hit race conditions.
- Atomic operations, synchronization, mutual exclusion, and critical sections are the four ideas behind correct-by-design multithreaded code.
- A lock is the first synchronization mechanism for enforcing mutual exclusion on a critical section. Semaphores - a more powerful primitive - come next.