The explorer made the wish obvious: if only the increment couldn’t be interrupted in the middle.
26.5 The Wish For Atomicity
Imagine a super-instruction:
memory-add 0x8049a1c, $0x1If the hardware guaranteed it executed atomically, the race would vanish: when an interrupt occurs, either the instruction has not run at all, or it has run to completion — no in-between state visible. Hardware can be a beautiful thing, no? Atomicity atomicity All-or-nothing execution: a grouped sequence appears to have happened entirely or not at all, with no in-between state visible even across interrupts. Provided per-instruction by hardware; built into larger units (transactions) by software. defined in ch. 26 — open in glossary means “as a unit” — all or none.
But we can’t have a super-instruction for everything. Building a
concurrent B-tree? No sane instruction set offers
atomic-update-of-B-tree. Instead, the hardware provides a few
useful atomic instructions, and from them — plus help from the OS — we
build a general set of
synchronization primitives synchronization primitives The building blocks (locks, condition variables, semaphores) constructed from a few atomic hardware instructions plus OS help, letting multi-threaded code enter critical sections in a controlled way and produce correct results.
defined in ch. 26 — open in glossary
:
machinery that lets multi-threaded code enter critical sections in a
controlled way and reliably produce correct results. Pretty awesome,
right?
Tip: Use Atomic Operations
All-or-nothing grouping is one of computing’s most powerful ideas — from architecture to concurrent code to file systems (journaling, copy-on-write) to databases and distributed systems, where grouped atomic actions go by the name transactions. Here we’ll use synchronization primitives to make short instruction sequences atomic; the idea, as Part III will show, is much bigger than that.The Crux: How To Support Synchronization
What support do we need from the hardware in order to build useful synchronization primitives? What support from the OS? How can we build these primitives correctly and efficiently? How can programs use them to get the desired results?This is the problem this whole Part studies. It is a wonderful and hard problem, and should make your mind hurt (a bit). If it doesn’t — keep working until your head hurts; then you know you’re headed in the right direction. (Then take a break. We don’t want your head hurting too much.)
26.6 One More Problem: Waiting For Another
Atomicity isn’t the only interaction between threads. Just as often, one thread must wait for another to complete some action — a thread sleeping through a disk I/O must be roused from its slumber when the I/O completes. So the coming chapters build two kinds of machinery: synchronization primitives for atomicity, and mechanisms for sleeping/waking. If that doesn’t fully make sense yet, that’s OK! It will when you read the condition-variables chapter. (If it doesn’t by then, well, that’s less OK — read it again, and again, until it does.)
| definition | |
|---|---|
| critical section | a piece of code that accesses a shared resource, usually a variable or data structure |
| race condition | multiple threads enter the critical section at roughly the same time, both updating the shared structure — surprising outcomes follow |
| indeterminate | a program containing one or more races: its output varies run to run, depending on which threads ran when |
| mutual exclusion | the guarantee that only a single thread ever enters a critical section — races avoided, deterministic output restored |
26.7 Summary: Why In OS Class?
Why study this here and not in a programming course? “History” is the one-word answer: the OS was the first concurrent program, and the techniques were created for its own use. Consider two processes appending to the same file:
| each write() must… | |
|---|---|
| step 1 | allocate a new disk block |
| step 2 | record the block in the file's inode |
| step 3 | grow the file's recorded size |
From the moment interrupts existed, kernel designers had to protect every shared structure — page tables, process lists, file-system metadata, virtually all of it — with proper synchronization. When multi-threaded processes arrived, application programmers inherited the same problems, and the same toolbox.
Homework: x86.py
Interleave real (tiny) assembly yourself: trace loop.s with one thread, then two; shrink and randomize the interrupt interval on looping-race-nolock.s and predict the final shared value; find which interrupt intervals give the “correct” answer and which are surprising — in other words, locate the critical section exactly. Finish with wait-for-me.s and watch a thread busy-wait for a flag: correct, and painfully wasteful. Get it at ostep-homework.Check yourself
1.A hypothetical memory-add instruction would fix the broken counter in one stroke. What does 'atomically' guarantee, exactly?
2.Why don't hardware designers just give us atomic instructions for everything — say, 'atomic update of B-tree'?
3.Besides atomicity for critical sections, the chapter names a SECOND fundamental thread interaction. What is it?
4.'Why in OS class?' has a one-word answer. Give it — and the illustration.
5.Match the four key terms: the CODE, the FAILURE, the SYMPTOM, the CURE.