Glossary

Every term the book defines — 435 of them — with the chapter that introduced it. These are the same definitions behind the dotted-underline tooltips throughout the site.

435 shown

2q replacement ch. 23: Linux's answer to LRU's scan problem: first touch puts a page on the INACTIVE list; a re-reference promotes it to the ACTIVE list (kept ~2/3 of the cache); evict from inactive. A huge cyclic file parades through inactive without flushing the hot working set.
absolute pathname ch. 39: A name that locates a file or directory by walking the directory tree from the root, e.g. /foo/bar.txt. Directories and files can share a name if they sit at different places in the tree.
abstraction ch. 2: Hiding lower-level detail behind a simple interface — the OS designer's fundamental tool.
access control list ch. 39: An ACL: a more general, precise way than permission bits to say exactly who may access a resource and how, used by systems like AFS (per-directory). Where permission bits offer only owner/group/other, an ACL can list specific users and rights (read, write, lookup, insert, delete, administer, lock).
access path ch. 40: The sequence of on-disk structures a file system reads and writes to carry out an operation. Opening /foo/bar walks the path from the root inode down (reading each directory's inode and data); reading a block consults the inode then the block; an allocating write touches the bitmap, inode, and data block. I/O cost grows with pathname length.
acknowledgment ch. 48: A short message (an 'ack') the receiver sends back to confirm it received the sender's message. Receiving an ack lets the sender be sure the original message arrived; its absence (after a timeout) signals possible loss.
address space ch. 2: A process's private virtual view of memory, which the OS maps onto physical memory.
address space identifier ch. 19: ASID: a small per-process tag (like an 8-bit PID) in each TLB entry letting translations from different processes coexist — the alternative to flushing the whole TLB on every context switch.
address translation ch. 15: Hardware transforming every memory reference's virtual address into a physical one — LDE's memory-side twin.
admission control ch. 22: Fighting thrashing by refusing to run some processes so the remainder's working sets fit — sometimes it's better to do less work well than everything at once poorly.
advice ch. 8: Hints users/apps give the OS (nice, madvise, informed prefetching) — the OS may use them for better decisions but needn't obey.
allocation header ch. 17: A small block the allocator stores just before each handed-out chunk (minimally its size, often a magic number for integrity), letting free(ptr) deduce the region's size — so a request for N bytes really searches for N + header bytes.
allocation policy ch. 41: The rules a file system uses to DECIDE where on disk to place inodes and data blocks (as opposed to the data structures that record the result). FFS's mantra: keep related stuff together (a file's data near its inode; files in a directory near each other) and unrelated stuff apart.
allotment ch. 8: The total CPU time a job may use at one priority level before demotion — counted across all its bursts (Rule 4).
amat ch. 22: Average memory access time: AMAT = T_M + (P_miss × T_D). Because disk time dwarfs memory time (10ms vs 100ns), even a 0.1% miss rate drags performance toward disk speed — the arithmetic behind every replacement policy's stakes.
amortization ch. 7: Reducing a fixed cost by incurring it less often — e.g., longer time slices dilute context-switch overhead.
andrew file system ch. 50: AFS — a distributed file system developed at CMU in the 1980s (led by M. Satyanarayanan) with the overriding goal of scale: supporting as many clients per server as possible. It achieves this with whole-file caching to the client's local disk plus server callbacks, and offers a consistency model far simpler to reason about than NFS's. Its client-side code is called Venus and its servers are collectively called Vice.
approximate counter ch. 29: A scalable counter (a.k.a. sloppy counter) representing one logical count as per-CPU local counters (each with a local lock) plus a single global counter/lock. Threads bump their local contention-free; a local is flushed to the global and reset once it reaches threshold S — trading accuracy (the global lags by up to CPUs×S) for scalability.
aslr ch. 23: Address space layout randomization: place code, stack, and heap at randomized virtual addresses so ROP chains can't be pre-computed (print &stack twice — different every run). KASLR extends the trick to the kernel.
asynchronous i/o ch. 33: OS interfaces (AIO) that issue an I/O request and return control immediately, before the I/O completes, plus a way to check for completion — e.g. fill a struct aiocb, call aio_read(), then poll aio_error() (0 = done, EINPROGRESS otherwise) or receive a signal on completion. Lets an event loop issue disk I/O without blocking.
atomic ch. 2: Executing all at once, indivisibly — what a multi-instruction sequence like counter++ is not.
atomicity ch. 26: 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.
atomicity violation ch. 32: A non-deadlock concurrency bug where a sequence of accesses assumed to be atomic is interrupted, letting another thread interleave and break the assumption — e.g. one thread checks a pointer is non-NULL and is interrupted before using it while another sets it NULL, causing a crash. Fixed by holding a lock around all the accesses. With order violations, ~97% of non-deadlock bugs (Lu et al.).
attribute cache ch. 49: A client-side cache of file attributes, with a short timeout (e.g. 3 seconds), added to NFS so that validating a cached file usually needs no network round-trip. It exists because the naive stale-cache fix — issuing a GETATTR to check the last-modified time before every cached access — flooded the server; the attribute cache lets a client trust its cached copy for the timeout window, at the cost of occasionally using a slightly stale file.
automatic memory ch. 14: Stack memory — allocated and freed implicitly by the compiler at function call/return; don't keep long-lived data there.
base register ch. 15: Per-CPU MMU register holding where the address space sits in physical memory; physical = virtual + base.
batch processing ch. 2: Early non-interactive computing: an operator ran queued jobs in batches.
belady's anomaly ch. 22: The unsettling discovery that FIFO can get WORSE with a BIGGER cache (stream 1,2,3,4,1,2,5,1,2,3,4,5: size 4 loses to size 3). Policies with the stack property are immune.
best fit ch. 17: Free-list strategy: search the whole list and return the SMALLEST chunk that satisfies the request — minimizes leftover waste but pays for the exhaustive search and tends to leave tiny slivers.
big kernel lock ch. 29: The BKL: a single coarse-grained lock guarding the entire kernel, used by early multiprocessor SunOS and Linux. A scaling bottleneck once multi-CPU machines became the norm — Linux replaced it with many fine-grained locks; Sun instead built Solaris for concurrency from day one.
binary semaphore ch. 31: A semaphore used as a lock: initialized to 1, with a sem_wait()/sem_post() pair bracketing the critical section. It has only two effective states (held / not held), hence 'binary'.
bitmap ch. 40: An allocation structure: one bit per object marking it free (0) or in-use (1). vsfs keeps an inode bitmap (for the inode table) and a data bitmap (for the data region). Bitmaps are consulted and updated only when allocating or freeing — never during a plain read.
block ch. 40: The fixed-size unit a file system divides its disk region into and allocates in (commonly 4 KB) — distinct from a hardware disk sector (usually 512 bytes). vsfs addresses its partition as blocks 0…N−1; the on-disk layout is a sequence of these blocks.
block corruption ch. 45: A disk block silently holds the wrong contents — e.g. buggy firmware wrote it to the wrong place (a misdirected write) or it was garbled crossing a faulty bus — while the disk's ECC still reports the block as good. The disk gives no indication of the problem, so this is a silent fault that must be detected with checksums.
block group ch. 41: The modern equivalent of a cylinder group (ext2/3/4): a consecutive portion of the disk's logical block address space. Since disks now hide their geometry, file systems group by block-address range instead of true cylinders, but the locality purpose is identical.
blocked ch. 4: Process state: waiting for an event (e.g., I/O completion) before becoming ready again.
bounds register ch. 15: Per-CPU MMU register (a.k.a. limit) holding the address-space size; out-of-bounds or negative references raise an exception.
broadcast ch. 30: pthread_cond_broadcast — wake ALL threads waiting on a condition variable, versus signal, which wakes only one. Needed when the signaler cannot identify the single correct waiter to wake (see covering condition).
buddy allocation ch. 17: Treat free memory as one 2^N space; recursively halve to the smallest sufficient power-of-two block (internal fragmentation is the tax). A freed block's buddy — its address differs by exactly one bit — is checked and merged, recursively, making coalescing trivial.
buffer overflow ch. 14: Writing past an allocation's end (e.g., forgetting strlen+1); sometimes silently "works," sometimes crashes, often a security hole.
bus ch. 36: The interconnect wiring devices to the CPU and memory, arranged as a hierarchy for physics and cost: a fast, short memory bus (CPU↔memory), a general I/O bus (e.g. PCIe) for higher-performance devices like graphics and NVMe, and slower peripheral buses (SCSI, SATA, USB) for disks, keyboards, and mice. Faster buses must be shorter and cost more, so high-demand components sit nearer the CPU.
bus snooping ch. 10: Each cache watches the shared bus and invalidates/updates its copy when it sees a write to data it holds.
cache affinity ch. 10: A process runs faster on the CPU whose caches/TLB already hold its state; schedulers should prefer keeping it there.
cache coherence ch. 10: The problem of keeping per-CPU caches consistent with the shared-memory illusion (stale-D vs updated-D′); solved in hardware.
cache consistency problem ch. 49: The challenge that arises once multiple clients cache copies of the same file: keeping their views consistent as clients read and write. Illustrated with clients caching different versions of a file F, it splits into two subproblems — update visibility (when do one client's writes become visible elsewhere?) and the stale-cache problem (a client still holding an old cached copy after another has updated the server).
callback ch. 50: In AFS, a promise the server makes to a client that it will notify (recall) the client whenever a file the client has cached is modified by someone else. Callbacks let a client assume its cached copy is valid until told otherwise, replacing NFS-style polling (repeated GETATTR/TestAuth checks) with an interrupt-like model — the key to AFS's scalability. When a writer closes a modified file, the server 'breaks' the callbacks of all other clients caching it, forcing them to re-fetch.
calloc ch. 14: malloc + zero-fill — inoculates against uninitialized reads.
capacity miss ch. 22: A miss because the cache ran out of space and had to evict — the kind replacement policies actually fight over.
cfs ch. 9: Linux's Completely Fair Scheduler — pick the lowest vruntime; dynamic slices from sched_latency/min_granularity; nice-based weights; red-black tree of runnables.
checkpoint region ch. 43: The CR: a fixed, well-known disk location (LFS keeps two) that points to the latest pieces of the inode map — the starting point for finding everything. It's updated only periodically (~every 30 s) so it doesn't hurt performance; on reboot, LFS reads the CR to bootstrap recovery.
checkpointing ch. 42: The step that writes a committed transaction's updates to their FINAL on-disk locations (overwriting the old structures in place), after the transaction is safely in the log. Only once checkpointing succeeds is the update truly done; its journal space can then be freed.
checksum ch. 45: A small summary (typically 4–8 bytes) produced by a function computed over a chunk of data (say a 4 KB block). Stored alongside the data and recomputed when the data is read: if the stored and computed checksums differ, the data has been corrupted. The primary mechanism modern storage systems use to preserve data integrity. Common functions include XOR, addition, the Fletcher checksum, and the CRC.
checksum collision ch. 45: When two data blocks with non-identical contents produce the same checksum. Collisions are unavoidable — a checksum squeezes something large (e.g. 4 KB) into a tiny summary (e.g. 4–8 bytes) — so a good checksum function is one that merely minimizes the chance of collision while staying cheap to compute.
chunk size ch. 38: How many consecutive logical blocks a RAID places on one disk before moving to the next. Small chunks boost single-file parallelism but raise positioning time (max over all disks touched); large chunks reduce intra-file parallelism but lower positioning cost. Tuning it needs workload knowledge.
circular log ch. 42: The journal treated as a fixed-size ring reused over and over. Once a transaction is checkpointed, its log space is freed for reuse; a journal superblock records which transactions are not yet checkpointed. This bounds the log size (and thus recovery time) and prevents the log from filling up and stalling the FS.
circular wait ch. 32: The key Coffman condition for deadlock: a circular chain of threads exists, each holding a resource (lock) that the next thread in the chain is waiting for. Prevented — most practically — by imposing a total (or partial) ordering on lock acquisition so no cycle can ever form.
cleaning ch. 43: LFS's garbage collection: since LFS never overwrites in place, old (dead) versions of blocks/inodes accumulate as garbage. The cleaner works segment-by-segment — reading M partly-dead segments, keeping only the live blocks, and writing them into N < M new segments — freeing whole segments for future sequential writes.
client-side file system ch. 49: The client half of a distributed file system. It receives the application's file-system system calls, holds what little client state exists (the mapping from an integer file descriptor to a server file handle, and the current file offset), and translates each call into the appropriate protocol messages sent to the server.
clock algorithm ch. 22: Corbató's LRU approximation: pages in a circle, a hand sweeping — use bit 1? clear it, advance; use bit 0? victim found. Cheap, scan-bounded, and commonly extended to prefer clean over dirty victims.
clustering ch. 22: Collecting pending page writes and issuing them as one large disk write — disks do one big write far more efficiently than many small ones (the swap daemon's favorite trick).
coalescing ch. 17: Allocator mechanism: when memory is freed, merge it with any address-adjacent free chunks into one larger chunk — without it, a fully-free heap can still look fragmented into useless pieces.
coarse-grained segmentation ch. 16: Segmentation with just a few large segments (code, heap, stack) — the address space is chopped into big, coarse chunks.
code segment ch. 13: The address-space region holding the program's instructions — static in size, conventionally placed at the top (low addresses).
compaction ch. 16: Rearranging allocated segments into one contiguous region (stop the process, copy its data, update its segment registers) to cure external fragmentation — effective but memory- and CPU-expensive.
compare-and-swap ch. 28: Atomic: if *ptr equals expected, store new; either way return the original (x86 compare-and-exchange). Builds the same spin lock as test-and-set but is strictly more powerful — the foundation of lock-free synchronization.
compulsory miss ch. 22: A miss because the cache starts empty and this is the first reference to the item (a.k.a. cold-start miss) — no policy can avoid it; hit rates are sometimes quoted 'modulo compulsory'.
concurrency ch. 2: The problems that arise when working on many things at once within the same memory space.
condition variable ch. 27: The signaling primitive (pthread_cond_t): wait(cond, mutex) sleeps the caller — releasing the mutex while asleep, reacquiring before return — until another thread signal()s. Always called with the lock held; always re-checked in a while loop. The deep treatment arrives with ch30.
conflict miss ch. 22: A miss caused by hardware placement restrictions (set-associativity). Doesn't arise in the OS page cache, which is fully associative — a page can live in any frame.
consistent-update problem ch. 38: A crash or power loss partway through a multi-disk write (e.g. updating both copies of a mirror) leaves the copies inconsistent — new on one disk, old on the other. Solved with a write-ahead log recording the intended update before it happens, usually kept in battery-backed non-volatile RAM to avoid the cost of logging to disk.
context switch ch. 4: The mechanism that stops one program and starts another on a CPU by saving and restoring register state.
continuation ch. 33: A record of the information needed to finish handling an event later — e.g. storing a socket descriptor sd in a hash table keyed by the file descriptor fd, so that when the async read on fd completes, the handler can look up where (sd) to write the data. An old programming-language idea used to solve event-based state management.
convoy effect ch. 7: Short jobs queued behind a heavyweight resource consumer — the three-cart grocery line.
copy-on-write ch. 23: COW (from TENEX): to 'copy' a page, map it read-only into both address spaces; only when someone writes does a trap allocate a real private copy. Makes fork()+exec() affordable and shared libraries cheap.
covering condition ch. 30: A condition on which the signaler wakes ALL waiting threads (via broadcast) rather than one (via signal), because it cannot tell which specific waiter should proceed — e.g. a memory allocator freeing bytes that could satisfy any of several differently-sized requests. Correct but potentially wasteful: needlessly woken threads simply re-check and go back to sleep. (Lampson & Redell.)
crash-consistency problem ch. 42: The challenge of updating on-disk structures when a single operation needs several writes but the disk commits only one at a time: a crash or power loss between writes leaves the file system half-updated and inconsistent. The FS-specific name for ch38's consistent-update problem. Goal: move atomically from one consistent state to another despite arbitrary crashes.
critical section ch. 26: A piece of code that accesses a shared resource (variable, structure) and must NOT be concurrently executed by more than one thread — Dijkstra's term, like most of this vocabulary.
cyclic redundancy check ch. 45: A checksum (CRC) computed by treating the data block as one large binary number and dividing it by an agreed-upon value k; the remainder is the checksum. The modulo operation can be implemented very efficiently, making CRCs popular in storage and networking alike.
cylinder ch. 41: A set of tracks that sit at the same distance from the center of a drive, across all its surfaces/platters — so named for the cylindrical shape they trace. FFS grouped consecutive cylinders to reason about disk locality.
cylinder group ch. 41: FFS's unit of locality: N consecutive cylinders grouped together, each group holding its own superblock copy, inode/data bitmaps, inode table, and data blocks. Placing related files in one group keeps their accesses close, avoiding long seeks.
dangling pointer ch. 14: Using memory after freeing it — the region may have been recycled by a later malloc.
data block ch. 40: A block in the file system's data region that holds actual user file contents (or a directory's entries, or an indirect block of pointers). Most of a disk is data blocks; the inode records which ones belong to a file.
data integrity ch. 45: Also called data protection: ensuring that the data a storage system returns is identical to what was written to it, despite the unreliable nature of modern storage devices. This chapter's central concern — the reliability of the data itself, complementing RAID's whole-disk reliability.
data journaling ch. 42: The journaling mode (ext3) that logs everything — metadata AND user data — to the journal before checkpointing. Safest, but writes every data block to disk twice, roughly halving write bandwidth.
datagram ch. 48: A fixed-size message (up to some maximum) sent over an unreliable layer such as UDP. Delivery is best-effort: datagrams may be lost, duplicated, or arrive out of order, with no guarantees from the layer itself.
deadlock ch. 31: A situation where a set of threads are each holding a resource and waiting for one held by another, forming a cycle in which none can proceed — e.g. every dining philosopher holding their left fork and waiting for their right, or a consumer holding a mutex while blocked on 'full' while the producer that would post 'full' is blocked on that mutex. Studied in depth in ch32.
deadlock avoidance ch. 32: A strategy that uses global knowledge of which locks each thread may acquire to schedule threads so deadlock can never occur — e.g. never co-scheduling two threads that both grab L1 and L2. Dijkstra's Banker's Algorithm is the classic example; it needs full advance knowledge and can limit concurrency, so it's rarely general-purpose.
demand paging ch. 22: The default page-selection policy: bring a page into memory only when it's accessed — on demand — rather than ahead of time.
demand zeroing ch. 23: Lazy page allocation: map the new heap page as inaccessible and only find, zero (a security must), and map a physical page when it's actually touched — never touched, never paid for.
device driver ch. 2: Code in the OS that knows how to deal with a specific hardware device.
device register ch. 36: A small hardware location a device exposes as its interface. The canonical three are a STATUS register (read the device's current state), a COMMAND register (tell it to perform a task), and a DATA register (pass data in or out). The OS controls the device by reading and writing these registers.
dining philosophers ch. 31: Dijkstra's classic concurrency problem: five philosophers around a table with one fork between each pair; each needs both neighboring forks to eat. The naive 'grab left then right' solution deadlocks (all hold their left fork, all wait forever for their right). Breaking the symmetry — one philosopher grabs right-then-left — removes the cycle.
direct memory access ch. 36: DMA: a dedicated engine that orchestrates data transfers between a device and main memory without much CPU involvement. The OS programs it (where the data lives, how much, and which device), then does other work; the DMA controller raises an interrupt when the transfer is complete. Frees the CPU from copying data by hand (as in PIO).
direct pointer ch. 40: A disk address stored directly in the inode that points at one of the file's data blocks. An inode holds a small fixed number of them (e.g. 12); together they cover small files entirely — which is most files.
direct-mapped ftl ch. 44: The naive FTL where logical page N maps straight to physical page N. Every write must read the whole containing block, erase it, and re-program all pages — causing huge write amplification, terrible write speed, and rapid wear of hot blocks. A bad idea, motivating the log-structured FTL.
directory ch. 39: A special file whose contents are a list of (user-readable name, low-level name/inode-number) pairs. Each entry maps a name to either a file or another directory; nesting directories builds the directory tree. A directory has its own inode number and always contains '.' (itself) and '..' (its parent). You never write a directory directly — the file system owns its format.
directory entry ch. 40: One record in a directory's data blocks mapping a name to an inode number, typically with a record length (reclen) and string length. The reclen lets a deleted entry's space be reused. Every directory also has '.' and '..' entries. Directories are just files whose inode type is 'directory'.
directory tree ch. 39: The single hierarchy (a.k.a. directory hierarchy) into which all files and directories are organized, starting at the root directory '/'. A name like /foo/bar.txt is an absolute pathname walking the tree from the root.
dirty bit ch. 18: PTE bit set when a page has been modified since it was brought into memory — a clean page can be evicted without writing it back.
disk scheduling ch. 37: Choosing which of several pending disk I/O requests to service next (by the OS and/or the drive). Unlike CPU jobs, a disk request's cost is estimable from its seek and rotation, so schedulers approximate SJF by servicing the cheapest-to-reach request first.
disk scrubbing ch. 45: Periodically reading through every block of the system and re-verifying its checksum (often nightly or weekly), so that rarely-accessed data does not silently rot until every copy is corrupted. Most latent sector errors in the Bairavasundaram studies were found this way.
distributed file system ch. 49: A file system in which client machines access files and directories stored on a server (or a few servers) over a network, rather than on their own local disks. The arrangement enables data sharing across clients (the same view of the files from any machine), centralized administration and backup, and better security. Ideally it offers transparent access — behaving just like a local file system.
distributed shared memory ch. 48: DSM: an abstraction that let processes on different machines share a single large virtual address space, implemented through the OS virtual-memory system (accessing a page held on another machine triggers a page fault that fetches it). It is not used in practice today because a machine failure makes part of the shared address space vanish (e.g. a pointer into missing memory) and remote page faults are expensive.
distributed state ch. 49: Ousterhout's term for state that is shared between a client and a server — such as the meaning of an open file descriptor that the server tracks on the client's behalf. Distributed state is exactly what a stateless protocol avoids, precisely because keeping it consistent across crashes of either side is hard.
distributed system ch. 48: A system built from many cooperating machines that, despite regular failures of machines, disks, networks, and software, is engineered to appear to clients as if it rarely fails. Collecting unreliable components into a reliably-appearing whole is the central value of distributed systems, and underlies virtually every modern web service (Google, Facebook, and so on).
double free ch. 14: Freeing the same region twice — undefined behavior, often a crash.
dynamic relocation ch. 15: Base-and-bounds translation done at runtime by hardware — the address space can even be moved while the process is descheduled.
elevator algorithm ch. 37: SCAN: a disk-scheduling policy that sweeps the head back and forth across the disk, servicing requests in track order per sweep and deferring requests that arrive behind the head to the next sweep — which avoids the starvation of pure SSTF. Like an elevator that keeps going one direction rather than always serving the nearest floor. Variants: C-SCAN (one-way sweeps, fairer) and F-SCAN (freeze the queue during a sweep).
end-to-end argument ch. 48: The design principle that certain functionality — reliability being the classic example — can only be implemented completely at the highest level of a system, the application 'at the end,' because lower-level guarantees never cover the whole path. Reliable network delivery, for instance, does not make a file transfer reliable if the bytes can be corrupted in memory or when written to disk; only an end-to-end check does. A corollary is that lower-level machinery can still be worth adding for performance.
error correcting code ch. 45: Redundant bits (ECC) stored in the disk that the drive uses to determine whether a block's on-disk bits are good and, in some cases, to repair them. If the ECC cannot correct the error, the drive returns an error rather than silently handing back bad data — turning many faults into detectable (non-silent) ones.
event handler ch. 33: The code that processes a single event in an event-based server. Since handlers run one at a time in a single thread, no locks are needed — but a handler must never make a blocking call, or the whole server stalls.
event loop ch. 33: The heart of an event-based server: while(1){ events = getEvents(); for (e in events) processEvent(e); }. It waits for events, then processes each one with its handler, one at a time. Because only one handler runs at a time, choosing which event to handle next IS scheduling.
event-based concurrency ch. 33: A style of concurrent programming that uses no threads: a single-threaded event loop waits for events and dispatches each to a handler, one at a time. It gives the application explicit control over scheduling and needs no locks (on one CPU), at the cost of complexity around blocking calls and manual state management. Used in GUIs, servers like Flash, and node.js.
exactly-once semantics ch. 48: The guarantee that each message is delivered to the receiving application exactly once — never lost and never duplicated. It matters because timeout/retry (e.g. after a dropped acknowledgment) can cause the same message to arrive twice on the wire; the receiver must ack the duplicate but not re-deliver it. Under failure, RPC often weakens this to at-most-once.
exception ch. 6: The processor's reaction to an illegal act (raw I/O in user mode, divide by zero, bad memory access) — traps into the OS, which likely kills the process.
exec ch. 5: UNIX call family that transforms the current process into a different program — loads new code/static data over the old, re-initializes heap and stack; never returns on success.
exponential back-off ch. 48: A strategy where, on repeated packet loss (often a symptom of overload), the sender increases its timeout/retry interval each time — for example doubling it — rather than resending at a fixed rate. This avoids adding still more load to an already-congested resource; it was pioneered in the Aloha network and adopted in early Ethernet.
extent ch. 40: An alternative to per-block pointers: a disk pointer plus a length (in blocks), describing a contiguous run of a file. Extent-based file systems (XFS, ext4) allow several extents per file. More compact than pointers but less flexible; works best when files can be laid out contiguously.
external fragmentation ch. 16: Free physical memory chopped into little non-contiguous holes by variable-sized allocations, so a request can fail even though enough total free space exists — e.g. 24KB free in three chunks cannot satisfy a 20KB segment.
fail-partial ch. 45: The modern (fail-partial) disk-failure model: a disk can still fail entirely, but it can also seem to be working while individual blocks become inaccessible (latent sector errors) or return the wrong contents (corruption). Faults may be non-silent (an error is returned) or silent (wrong data is returned). Introduced by Prabhakaran et al.'s IRON File Systems work.
fail-stop ch. 45: The classic disk-failure model, assumed by early RAID: a disk is either entirely working or has failed completely, and the failure is straightforward to detect. Simple to build around, but it ignores partial faults like latent sector errors and corruption.
fail-stop fault model ch. 38: The simple RAID failure assumption: a disk is either working (all blocks readable/writable) or failed (permanently, wholly lost), and a failure is immediately and reliably detected. It deliberately ignores 'silent' faults like corruption and latent sector errors (deferred to the data-integrity chapter).
fairness ch. 7: Evenly dividing the resource among contenders (e.g., Jain's index); often at odds with turnaround performance.
fast file system ch. 41: FFS: the Berkeley redesign of the old UNIX file system that keeps the SAME interface (open/read/write/…) but makes the on-disk structures and allocation policies 'disk aware' — treating the disk like a disk (with real positioning costs) instead of like random-access memory. It set the template that modern file systems still follow.
fetch-and-add ch. 28: Atomically increment a memory value and return the OLD value — the ticket dispenser primitive.
fifo ch. 7: First In, First Out (a.k.a. FCFS) — run jobs in arrival order to completion; simple, but suffers the convoy effect.
file ch. 39: The file-system abstraction for a linear array of bytes you can read and write. The OS usually knows nothing about a file's contents; its job is to store the bytes persistently and return them intact. Each file also has a low-level name (its inode number).
file descriptor ch. 39: A small non-negative integer, private per process, returned by open() and used to read/write a file. It indexes a per-process array of pointers into the open file table. Think of it as a capability — an opaque handle granting access. Descriptors 0, 1, 2 are stdin, stdout, stderr, so the first opened file is usually 3.
file handle ch. 49: NFS's unique identifier for the file or directory an operation targets, included in most protocol requests. It has three parts: a volume identifier (which exported file system), an inode number (which file within it), and a generation number (to guard against stale handles). Together they let a stateless server locate the exact file with no other context.
file identifier ch. 50: AFS's FID, the analog of an NFS file handle: {volume identifier, file identifier, uniquifier}. The uniquifier allows the volume and file IDs to be safely reused after a file is deleted. Using FIDs, the client walks a pathname one component at a time (caching each directory) rather than shipping whole pathnames for the server to traverse.
file offset ch. 39: The 'current' position stored in an open file table entry, deciding where the next read or write begins. Each read/write of N bytes advances it by N; lseek() sets it explicitly (enabling random access). lseek() only changes this in-memory variable — it does NOT itself cause a disk seek.
file server ch. 49: The server half of a distributed file system: it stores the data on its disks and responds to protocol messages from clients. In a stateless design each message it receives is self-contained, carrying all the information needed to complete the request, so the server need remember nothing between requests.
file system ch. 2: The OS software that manages persistent data on storage devices.
file-system inconsistency ch. 42: A state where the file system's own data structures disagree — e.g. an inode points to a block the data bitmap says is free, or a bitmap marks a block used that no inode references (a space leak). Caused by a crash mid-update; it must be resolved (by fsck or journal recovery) before the FS can be trusted.
fine-grained locking ch. 28: Protecting different data with different locks so more threads can hold locks at once — versus one coarse-grained lock for everything. More concurrency, more care required.
fine-grained segmentation ch. 16: Segmentation with a large number of small segments (Multics, Burroughs B5000), requiring a segment table in memory; compilers chopped code and data into many pieces so the OS could place memory more flexibly.
firmware ch. 36: Software embedded within a hardware device that implements the abstraction the device presents to the system — for example, a modern RAID controller may contain hundreds of thousands of lines of firmware.
first fit ch. 17: Free-list strategy: return the first chunk big enough — fast (no exhaustive search) but can pollute the list's start with small splinters; address-ordered lists ease coalescing.
flash block ch. 44: The unit of flash ERASE (an 'erase block'), typically 128 KB–2 MB — much larger than a flash page, and different from a disk/FS block. Erasing sets every bit to 1 and destroys all pages in the block, so any data you still need must be copied out first. This erase-before-program constraint shapes all of SSD design.
flash memory ch. 44: NAND-based flash: solid-state storage that traps charge in transistors to store bits and retains it without power. Its defining quirks: you can read/program at page granularity but must ERASE a whole (larger) block before re-programming any page in it, and blocks wear out after many program/erase cycles.
flash page ch. 44: The unit of flash reads and programs (writes), a few KB (e.g. 4 KB) — distinct from a VM page or a disk block. Pages live within a flash block. A page can be programmed only once after its block is erased; changing it again requires erasing the whole block.
flash translation layer ch. 44: The FTL: the SSD's control logic that presents a normal logical block interface while translating client reads/writes into low-level flash read/erase/program operations. It aims for high performance (low write amplification, chip parallelism) and reliability (wear leveling), typically via a log-structured design + a mapping table.
fletcher checksum ch. 45: A checksum (named for John G. Fletcher) computed from two running check bytes over the data bytes d_i: s1 = (s1 + d_i) mod 255 and s2 = (s2 + s1) mod 255. Simple to compute yet nearly as strong as a CRC, detecting all single-bit, all double-bit, and many burst errors.
flush-on-close ch. 49: NFS's fix for update visibility, also called close-to-open consistency: when a client finishes writing a file and closes it, the client-side file system flushes all of that file's dirty cached pages to the server. This guarantees that a subsequent open of the file on another client will see the writer's latest version.
fork ch. 5: UNIX call creating a new process as an (almost) exact copy of the caller; the parent receives the child's PID, the child receives 0.
free ch. 14: Releases a malloc'd region — pointer only, no size (the library tracks it). Knowing when/how/if to call it is the hard part.
free list ch. 15: The OS structure tracking unused physical memory ranges, searched at process creation and refilled at termination.
fsck ch. 42: The file system checker: the old, lazy crash-consistency approach — let inconsistencies happen, then scan the whole disk at reboot and repair the metadata (rebuild bitmaps from inodes, fix link counts, clear bad pointers, move orphaned inodes to lost+found). Correct-ish but O(disk size), so far too slow on large modern volumes.
fsync ch. 39: A system call that forces all buffered ('dirty') data for a file descriptor to persistent storage and returns only once those writes complete. Needed by apps (e.g. databases) that require durability, since write() normally just buffers in memory for a few seconds. To durably create a file you often must fsync() its parent directory too.
full-stripe write ch. 38: The efficient RAID-4/5 write: when a whole stripe's worth of data is written at once, the RAID computes the new parity directly by XOR-ing the new blocks and writes all data + parity in parallel — no read of old values needed. Sequential writes hit this fast path.
fully associative ch. 19: Any translation can sit in any TLB entry, and the hardware searches all entries in parallel — so each entry must store the VPN alongside the PFN.
futex ch. 28: Linux's kernel-assisted lock support: a memory word with a per-futex in-kernel queue; futex_wait(addr, expected) sleeps iff the word still holds expected, futex_wake wakes one. glibc packs held-bit (sign) + waiter count into one integer, making the uncontended path a single atomic op.
gaming ch. 8: Tricking the scheduler into more than a fair share — e.g., issuing a throwaway I/O at 99% of the slice to stay high-priority.
garbage collection ch. 44: Reclaiming dead pages left behind by a log-structured device/FS: find a block with garbage (overwritten) pages, copy its still-live pages elsewhere, then erase the block for reuse. In SSDs it's a key FTL job (the FS-level version is LFS cleaning). It adds write amplification, mitigated by overprovisioning.
garbage collector ch. 14: Runtime machinery in newer languages that frees unreferenced memory for you — at the cost of keeping-a-reference leaks.
generation number ch. 49: The component of an NFS file handle that is incremented each time an inode number is reused. Because a stale file handle carries the old generation number, it will no longer match the (incremented) current one, preventing a client holding an outdated handle from accidentally accessing the different file that has since reused that inode.
global namespace ch. 50: A design, provided by AFS, in which every file is named the same way on all client machines, so a given path refers to the same file everywhere. This contrasts with NFS, where each client may mount servers at whatever mount points it chooses, making consistent naming across clients only a matter of convention and administrative effort.
hand-over-hand locking ch. 29: Lock coupling: one lock per list node instead of one lock for the whole list. A traversal grabs the next node's lock before releasing the current node's, enabling overlapping traversals — though per-node acquire/release overhead usually loses to a single big lock in practice.
hard link ch. 39: A second directory entry pointing at the SAME inode number as an existing file — another equal name for one file, made with link()/ln (no data is copied). Both names are indistinguishable; each raises the inode's link count. Can't span file systems (inode numbers are per-FS) or link to directories.
hardware-managed tlb ch. 19: On a miss the hardware itself walks the page table (whose location AND format it must know exactly — x86 via CR3), refills the TLB, and retries; the CISC-era design.
heap ch. 4: Memory region for explicitly requested dynamic allocations — malloc() and free() in C.
hoare semantics ch. 30: The stronger alternative to Mesa semantics (Hoare) in which signaling immediately hands the lock and CPU to a woken waiter, guaranteeing the signaled state still holds when it runs. A stronger guarantee, but harder to build — so it is rarely used in practice.
hold-and-wait ch. 32: One of the four Coffman conditions for deadlock: threads hold resources (locks) they've already acquired while waiting to acquire more. Prevented by acquiring ALL needed locks at once, atomically, under a global prevention lock (at the cost of modularity and concurrency).
huge pages ch. 23: Linux's 2MB/1GB pages. The prize is TLB coverage (big-memory apps burn ~10% of cycles on TLB misses with 4KB pages), plus shorter miss walks; adopted incrementally — explicit mmap/shmget first, then transparent huge pages. Costs: internal fragmentation, swap amplification.
hybrid mapping ch. 44: An FTL scheme that balances mapping-table size against write flexibility: keep a few erased log blocks with per-PAGE mappings (a small log table) for flexible writes, plus per-BLOCK mappings (a data table) for everything else. Log blocks are periodically merged back into block-mapped form — a switch merge (best), partial merge, or full merge (costliest).
i/o device ch. 2: Hardware that connects the computer to the outside world or stores long-lived data (disks, SSDs).
idempotency ch. 49: The property that performing an operation multiple times has exactly the same effect as performing it once — 'store value X to memory' is idempotent, while 'increment the counter' is not. It is the heart of NFS crash recovery: because most requests are idempotent (READ and LOOKUP trivially, and WRITE because it carries the exact offset), a client can safely retry after any failure — lost request, crashed server, or lost reply — in one uniform way.
indeterminate ch. 26: A program containing race conditions: its output varies from run to run depending on which threads ran when — the opposite of the determinism computers are supposed to deliver.
indirect pointer ch. 40: An inode pointer to an indirect block — a data block full of MORE pointers to data blocks (not user data). With 4 KB blocks and 4-byte addresses, one indirect block adds 1024 pointers. Double- and triple-indirect pointers add further levels for very large files.
inode ch. 39: The persistent per-file data structure the file system keeps to hold a file's metadata — size, owner, permissions, timestamps, link count, and pointers to its data blocks. Named by its inode number. Inodes live on disk; active ones are cached in memory. (Its internals are the subject of the file-system-implementation chapters.)
inode map ch. 43: The imap: LFS's level of indirection from inode number → the disk address of the most recent version of that inode. Since LFS scatters inodes across the disk and moves them on every write, the imap is how they're found; it's updated (and written) right alongside each segment. It also solves the recursive update problem.
inode number ch. 39: A file's low-level name: a unique number (also called an i-number) the file system uses internally to identify a file, as opposed to the human-readable name stored in a directory. A directory entry maps a name to an inode number.
inode table ch. 40: The on-disk region holding an array of inodes. Because inodes are fixed-size (e.g. 256 bytes, 16 per 4 KB block), the file system computes an inode's disk location directly from its i-number: blk = (inumber · sizeof(inode)) / blockSize, offset from the table's start.
internal fragmentation ch. 15: Wasted space INSIDE an allocated unit — e.g., the unused gap between heap and stack in a fixed base/bounds slot.
interposition ch. 15: Inserting machinery at a well-defined interface (here: every memory access) to add functionality transparently.
interrupt ch. 36: A hardware signal a device raises when it finishes an operation, causing the CPU to stop its current work and jump into an OS interrupt handler. Interrupts let the OS sleep the waiting process and run other work during slow I/O — overlapping computation and I/O — instead of polling. Best for slow devices; for fast ones the handling/context-switch cost can outweigh the benefit.
interrupt coalescing ch. 36: An optimization where a device briefly delays raising an interrupt so that several requests completing around the same time can be reported in ONE interrupt delivery, lowering per-interrupt overhead — at the cost of a little added latency.
interrupt handler ch. 36: The interrupt service routine (ISR) — the OS code that runs when a device raises an interrupt. It finishes the request (reads data and any error code from the device) and wakes the process that was waiting on the I/O.
inverted page table ch. 20: One system-wide table with an entry per PHYSICAL frame (which process, which virtual page), found by search — in practice hashed (PowerPC). The extreme reminder that page tables are just data structures.
isolation ch. 2: Keeping processes separated from one another — the principle at the heart of protection.
job ch. 7: Scheduling's name for a unit of work (a process, or a CPU burst treated independently).
join ch. 27: pthread_join(thread, &retval): block until the named thread completes, optionally collecting its void* return value. Long-lived servers may never join; parallel task programs join to know the work is done. (create-then-immediately-join has a simpler name: a procedure call.)
journaling ch. 42: A crash-consistency technique (write-ahead logging, borrowed from databases): before overwriting structures in place, first write a note describing the update to an on-disk log. After a crash, recovery replays only the log — turning recovery from O(disk size) into O(log size). Used by ext3/ext4, XFS, JFS, NTFS.
kernel logical address ch. 23: Linux's kmalloc territory: direct-mapped to the start of physical memory (0xC0000000 → PA 0), never swapped, and contiguity carries over to physical — which is what DMA transfers require.
kernel mode ch. 2: The privileged hardware mode in which the OS has full access to the machine.
kernel stack ch. 6: The per-process stack in the kernel where hardware saves user registers (PC, flags…) on a trap/interrupt, popped by return-from-trap.
kernel virtual address ch. 23: Linux's vmalloc territory: virtually contiguous, physically scattered (so no DMA) — easier to allocate for large buffers, and on 32-bit systems the kernel's route past its ~1GB direct-map limit.
kpti ch. 23: Kernel page-table isolation: post-Meltdown, unmap (almost all of) the kernel from user page tables and switch tables on every kernel entry — better isolation, real performance cost. Security's price: convenience and performance.
large-file exception ch. 41: FFS's rule that overrides 'keep a file's blocks in one group' for big files: after a chunk (e.g. the 12 direct blocks) fills part of a group, later chunks spill into other groups. This stops one large file from filling a group and destroying locality for related small files — at the cost of extra seeks, amortized by using large enough chunks.
last writer wins ch. 50: AFS's behavior when processes on different machines modify the same file concurrently — more precisely 'last closer wins': whichever client calls close() last flushes its whole file to the server last and becomes the winning version. The result is a file produced entirely by one client or the other, never a block-level intermixing of both clients' writes (which a block-based protocol like NFS can produce, e.g. a corrupt half-and-half JPEG).
latent sector error ch. 45: A latent sector error (LSE) occurs when a disk sector (or group of sectors) is physically damaged — e.g. a head crash scrapes the surface, or a cosmic ray flips bits. The drive's in-disk error correcting code detects the bad bits and, if it cannot fix them, returns an explicit error when the block is read. Because it is detected, an LSE is a non-silent partial fault and is relatively easy to recover from using redundancy.
lfs segment ch. 43: In LFS, a large (a few MB) chunk of buffered updates that LFS writes to disk in one long sequential transfer. Large segments are what make writes efficient (amortizing positioning cost) and are also the unit of cleaning. (A different meaning from the memory 'segment' of virtual-memory segmentation.)
lfu ch. 22: Least-frequently-used replacement: evict the page with the fewest accesses — the frequency-based sibling of LRU's recency. (Their opposites, MFU/MRU, mostly lose by ignoring locality.)
limited direct execution ch. 6: Run programs directly on the CPU for speed, but with hardware-enforced limits (modes, trap table, timer) so the OS keeps control.
linear page table ch. 18: The simplest page table: a flat array indexed by VPN, one PTE per virtual page — the structure whose 4MB-per-process cost motivates smarter tables.
link count ch. 39: A reference count inside an inode tracking how many hard links (directory entries) point to it. link() increments it; unlink() decrements it; the file is truly deleted (inode + data freed) only when it hits zero.
livelock ch. 32: A failure where threads are not blocked (not deadlocked) yet make no progress — e.g. two threads each grab lock 1, fail to trylock lock 2, release lock 1, and retry in lockstep forever. Unlike deadlock the threads keep running; fixed by adding a random back-off delay before retrying.
load imbalance ch. 10: Some CPUs oversubscribed while others idle — MQMS's fundamental failure mode when jobs finish unevenly.
load-linked/store-conditional ch. 28: The paired primitives (MIPS, ARM, PowerPC, Alpha): load-linked reads; store-conditional succeeds ONLY if no intervening store touched the address since the LL — returning 1/0. Race between LL and SC? Exactly one contender's SC succeeds; the rest retry.
lock ch. 28: A variable holding one of two states — available (free) or acquired (held by exactly one thread, the owner) — with lock() not returning until the caller holds it, and unlock() freeing it. Programmers bracket critical sections with them, making the section execute as if atomic.
lock-free ch. 32: A synchronization approach that coordinates threads using atomic hardware instructions (e.g. compare-and-swap) instead of locks, so no lock is held and no deadlock can arise (livelock still can). It sidesteps the mutual-exclusion deadlock condition; e.g. a list insert via while(CAS(&head, n->next, n)==0). Pioneered by Herlihy.
log-structured file system ch. 43: LFS (Rosenblum & Ousterhout): a file system that turns ALL writes into sequential writes. It buffers updates (data AND metadata) in memory, then writes them to an unused part of the disk as one big segment — never overwriting in place (copy-on-write). Optimizes write performance (most traffic is writes; sequential ≫ random) and sidesteps RAID's small-write problem.
log-structured ftl ch. 44: The dominant FTL design: on a write to logical block N, append the data to the next free page (logging) and record N → physical-page in a mapping table. This turns random writes into sequential ones (few erases), improves performance, and spreads wear — the same log idea as LFS, inside the device. Its costs: garbage collection and mapping-table size.
lost write ch. 45: A failure mode where the device reports a write as completed but never actually persists it, leaving the old block contents behind. Basic checksums and physical IDs still match the stale block, so detection requires either a write verify (read-after-write) or a checksum kept elsewhere — e.g. ZFS stores a checksum in each inode and indirect block, so a lost data write no longer matches.
lottery scheduling ch. 9: Every slice, draw a random winning ticket; the holder runs. Probabilistically proportional, minimal state, no global bookkeeping.
lru ch. 19: Least-recently-used replacement: evict the entry idle longest, betting on locality — sensible until a loop over n+1 pages meets an n-entry TLB and EVERY access misses (random replacement dodges such corner cases). Studied in depth with swapping.
machine state ch. 4: What a program can read or update while running: its memory, its registers, and its open I/O resources.
malloc ch. 14: The C library call requesting heap bytes (size via sizeof()); returns a pointer, or NULL on failure. A library call, not a system call.
manual stack management ch. 33: The burden in event-based code (named by Adya et al.) of explicitly packaging the program state needed to finish handling an event later — because, unlike a thread, there is no per-request stack holding that state across a blocking/async call. Solved with continuations.
mapping problem ch. 38: Given a logical block address, how does the RAID compute which physical disk and offset hold it? For simple striping with a one-block chunk it is just Disk = A % N, Offset = A / N (integer arithmetic).
marshaling ch. 48: Packing a function's arguments (or results) into a single contiguous message buffer so they can be sent across the network — also called serialization. The inverse operation at the far end, extracting the values back out of the message, is called unmarshaling or deserialization.
mechanism ch. 4: A low-level method or protocol implementing a needed piece of functionality — the "how" answer (vs. policy's "which").
meltdown and spectre ch. 23: The 2018 attacks showing that SPECULATIVE EXECUTION — the CPU running guessed-at instructions early — leaves traces in caches and predictors that leak memory the MMU supposedly protects. Mitigations (like KPTI) help; the fundamental tension remains.
memory hierarchy ch. 21: The layered arrangement of storage — small fast caches, then RAM, then big slow disks at the bottom; swapping adds that bottom level to the virtual-memory story so address spaces can exceed physical memory.
memory leak ch. 14: Forgetting to free memory; slowly fatal for long-running programs, and GC can't help while references persist.
memory-mapped i/o ch. 36: A device-communication method in which device registers appear as ordinary memory addresses; the OS reads and writes them with normal load/store instructions, and the hardware routes those accesses to the device. The alternative is explicit (port-mapped) I/O instructions such as x86's privileged in/out. Both approaches are still used.
mesa semantics ch. 30: The interpretation (Lampson & Redell, from the Mesa system) where a condition-variable signal is only a HINT that the waited-on state may have changed — not a guarantee it still holds when the woken thread finally runs. The woken thread must re-check the condition, hence 'while, not if'. Virtually every real system uses Mesa semantics.
metadata ch. 39: Data about a file rather than its contents — size, inode number, owner/group, permissions, link count, and access/modify/change times. Retrieved with stat()/fstat() (the stat structure); stored in the file's inode.
metadata journaling ch. 42: Ordered journaling: journal only metadata (inodes, bitmaps, directories), not user data. To avoid an inode pointing at garbage, the rule is 'write the pointed-to data block to its final location BEFORE committing the metadata that points to it.' Far less journal traffic than data journaling; the common choice (ext3 ordered mode, XFS, NTFS).
microkernel ch. 13: An OS design that walls off pieces of the kernel from each other, extending isolation inside the OS itself for reliability.
migration ch. 10: Moving a job between CPUs to rebalance load — sometimes once, sometimes continuously.
mirroring ch. 38: RAID-1: keep two (or more) physical copies of every block on separate disks. Tolerates at least one disk failure (more, with luck); a read can use either copy, but every logical write must update all copies. Costs half the capacity (useful capacity (N·B)/2 at mirroring level 2).
misdirected write ch. 45: A failure mode where the disk or RAID controller writes the data correctly but to the wrong location (wrong block, or in a multi-disk system the wrong disk). Detected by storing a physical identifier — the disk and block numbers — together with the checksum, so a read can tell whether the right block is in the right place.
mlfq ch. 8: Multi-Level Feedback Queue — priority queues + observed behavior: assume every job short, demote CPU-grinders, boost everyone periodically; approximates SJF without an oracle.
mmap ch. 14: System call that can create anonymous memory regions (swap-backed) usable like a heap; one of the primitives malloc builds on.
mmu ch. 15: The memory management unit — the part of the CPU that translates addresses; grows from two registers to TLBs and page-table walkers.
mount point ch. 39: An existing directory onto which another file system is grafted with mount(), so its root appears at that path and its contents become reachable in the unified tree. Mounting is how many separate file systems (ext3, proc, tmpfs, AFS…) are glued into one directory hierarchy; mkfs first writes an empty file system onto a device.
mqms ch. 10: Multi-queue multiprocessor scheduling — per-CPU queues scheduled independently; scalable and affine, but prone to load imbalance.
multi-level cell ch. 44: How many bits a flash transistor stores by distinguishing charge levels: SLC (single-level, 1 bit — fastest, longest-lived, priciest), MLC (2 bits), TLC (3 bits — densest/cheapest, slower, shorter-lived). More bits per cell = more capacity per dollar but worse performance and endurance.
multi-level index ch. 40: The imbalanced-tree scheme for locating a file's blocks: a few direct pointers, then single, double, and triple indirect pointers. It optimizes for the common case (most files are small → direct pointers suffice) while still supporting huge files. Used by ext2/ext3, the original UNIX FS, and WAFL.
multi-level page table ch. 20: A page table chopped into page-sized pieces with entirely-invalid pieces simply not allocated — a page directory tracks which pieces exist. Space grows with the USED address space, at the cost of an extra memory load per TLB miss (x86's design).
multi-zoned disk ch. 37: A disk organized into zones (consecutive sets of tracks) where outer zones pack MORE sectors per track than inner zones — because there is simply more room on the outer, longer tracks. Each zone has a fixed number of sectors per track.
multicore ch. 10: Multiple CPU cores on one chip — the reason multiprocessors went mainstream when single CPUs hit the power wall.
multiprogramming ch. 2: Keeping several jobs in memory and switching between them (especially during I/O) to raise utilization.
mutex ch. 27: POSIX's lock object (pthread_mutex_t): lock() blocks until the caller holds it, unlock() releases. Must be INITIALIZED (static initializer or pthread_mutex_init) and its return codes CHECKED — the two classic omissions. trylock/timedlock variants exist; mostly avoid them.
mutual exclusion ch. 26: The guarantee that if one thread is executing a critical section, others are prevented from doing so — the property locks exist to provide, and the road back to deterministic output.
namespace locality ch. 41: The tendency for files that are close in the directory tree to be accessed close together in time (e.g. compiling all the files in one directory). FFS exploits it by placing files from the same directory in the same group. Distinct from spatial/temporal locality, which are about addresses/time.
network file system ch. 49: NFS — Sun Microsystems' early and hugely successful distributed file system. Rather than a proprietary product, Sun defined it as an open protocol (publishing the exact client/server message formats), so many vendors could build interoperable NFS servers. The classic version studied is NFSv2, whose overriding goal is simple and fast server crash recovery.
next fit ch. 17: First fit plus a roving pointer: resume searching where the last search ended, spreading splinters through the list instead of piling them at the front.
nice ch. 9: Classic UNIX priority knob, −20…+19 (default 0); CFS maps it to weights (1024 at 0) — positive = nicer = less CPU.
no preemption ch. 32: One of the four Coffman conditions for deadlock: resources (locks) cannot be forcibly taken from the threads holding them. Worked around with pthread_mutex_trylock — a thread that fails to get a second lock releases the ones it holds and retries, gracefully backing out of its own ownership.
non-blocking ch. 33: A non-blocking (asynchronous) interface begins some work but returns to the caller immediately, letting the work finish in the background — versus a blocking (synchronous) interface that does all its work before returning. Non-blocking calls are essential to event-based servers, since any blocking call would halt the single-threaded event loop.
nondeterminism ch. 5: When output/behavior depends on scheduling timing — e.g., whether parent or child prints first after fork().
nx bit ch. 23: No-eXecute: a PTE bit (AMD's NX, Intel's XD) that forbids executing from a page — stacks stop being launchpads for injected code. The first rung on the defense ladder.
open file table ch. 39: A system-wide table of entries, each describing one open file: which inode it refers to, whether it is readable/writable, a reference count, and the current file offset. A process's file descriptors point into this table; usually one-to-one, but entries can be shared (via fork() or dup()).
operating system ch. 2: Software that makes the system easy to use by virtualizing resources, handling concurrency, and storing data persistently.
optimal replacement policy ch. 22: Belady's MIN: evict the page that will be accessed FURTHEST in the future — provably the fewest misses, unimplementable without clairvoyance, and indispensable as the yardstick that tells you how close to perfect (and when to stop tuning) a real policy is.
order violation ch. 32: A non-deadlock concurrency bug where the desired order between two groups of memory accesses is flipped — A should run before B but the order isn't enforced — e.g. a thread uses a variable another thread was supposed to initialize first, hitting a NULL dereference. Fixed by enforcing order with a condition variable (or semaphore).
overprovisioning ch. 44: Building an SSD with more physical flash than its advertised capacity. The spare space lets garbage collection be delayed and run in the background (when the device is idle) and adds internal bandwidth for cleaning — reducing the performance hit of GC.
packet loss ch. 48: The fundamental fact of networking that packets sometimes never reach their destination. Causes include bit corruption in transit, down or severed links and non-working machines, and — most fundamentally — a switch, router, or host running out of buffer space and having no choice but to drop arriving packets.
page ch. 18: A fixed-sized unit of a virtual address space; every page can live in any free physical frame, which is what makes free-space management trivial under paging.
page cache ch. 23: Linux's unified in-memory cache of memory-mapped files, file data/metadata, and anonymous (heap/stack) memory, kept in a hash table with clean/dirty tracking; pdflush threads write dirty pages back in the background.
page directory ch. 20: The top structure of a multi-level page table: one entry per page of the page table, saying whether that piece holds any valid PTEs and, if so, which frame it lives in (its base register: the PDBR — x86's CR3).
page fault ch. 21: An access to a page that is valid but not present in physical memory (present bit = 0) — really a page MISS, but the hardware can only raise an exception and let the OS make things better. The OS then fetches the page from swap.
page frame ch. 18: A fixed-sized slot of physical memory holding exactly one virtual page; physical memory is viewed as an array of them.
page table ch. 18: The per-process structure storing each virtual page's translation (VPN → PFN) plus per-page bits; one of the most important data structures in a modern OS — and, done naively, both too big and too slow.
page-directory entry ch. 20: One page-directory record (PDE): a valid bit plus a PFN; valid means at least one PTE on the pointed-to page of the page table is valid — invalid means that whole slice of address space costs nothing.
page-fault handler ch. 21: The OS code that services a page fault: find (or evict for) a free frame, issue the disk read, mark the PTE present with the new PFN, and retry the instruction — always software, even with hardware-managed TLBs (disk is slow enough that nobody cares, and hardware wants no part of swap I/O).
page-replacement policy ch. 21: The decision of WHICH page to kick out when memory is full. Choosing badly runs programs at disk speed — 10,000–100,000× slower — which is why it gets its own chapter.
page-table base register ch. 18: Hardware register (PTBR) holding the physical address where the running process's page table starts; the hardware computes PTEAddr = PTBR + VPN × sizeof(PTE) on every reference.
page-table entry ch. 18: One page table record (PTE): the physical frame number plus bits — valid, protection, present, dirty, reference — that the hardware checks and the OS exploits.
paging ch. 18: Virtualizing memory by chopping the address space into fixed-sized pages mapped to physical page frames — no external fragmentation by design, and sparse address spaces come cheap (Atlas, early 1960s).
parallelization ch. 26: Transforming a single-threaded program to spread its work across CPUs — typically one thread per processor — for real speedups on real hardware.
parity ch. 38: Redundancy computed with XOR across the data blocks of a stripe and stored in a parity block, so any one lost block can be reconstructed by XOR-ing the survivors. Cheaper than mirroring (one extra disk protects a whole group → (N−1)·B capacity) but slower on writes, since updating data means updating parity too.
park ch. 28: Solaris's sleep-a-thread primitive (with unpark(tid) to wake one): the OS support that turns spinning locks into sleeping ones — enqueue yourself, park; the releaser unparks the next waiter, passing the lock DIRECTLY (flag never resets in between). setpark() closes the wakeup/waiting race.
perfect scaling ch. 29: Threads finish work on many CPUs just as fast as one thread does its share on one CPU — more total work, done in parallel, so wall-clock time does not grow.
permission bits ch. 39: The classic UNIX access control: nine bits shown as rwxrwxrwx giving read/write/execute for owner, group, and other. Changed with chmod. For a regular file, execute means runnable; for a directory, execute allows cd/traversal into it. A coarser model than access control lists.
persistence ch. 2: Keeping data safe across power loss and crashes, via I/O devices and the software that manages them.
physical address ch. 13: An actual location in the machine's memory — known only to the OS and hardware, never to user programs.
pid ch. 2: Process identifier — a unique number naming a running process.
pipe ch. 5: An in-kernel queue connecting one process's output to another's input, created with pipe(); the plumbing behind cmd | cmd chains.
platter ch. 37: A circular hard surface (aluminum coated with a thin magnetic layer) that stores bits persistently, even when the drive is off. A disk has one or more platters, each with two surfaces, all bound to a spindle that a motor spins at a fixed rate (RPM).
policy ch. 2: An OS decision rule that answers "which/what next?" questions, e.g. which program runs next.
polling ch. 36: Repeatedly reading a device's status register in a loop to learn its state (e.g. spinning while STATUS == BUSY). Simple, but it wastes CPU cycles busy-waiting on a slow device instead of doing useful work — the motivation for interrupts.
pre-allocation ch. 40: An allocation heuristic (ext2/ext3) that grabs a run of consecutive free blocks (e.g. 8) for a new file at once, so part of the file lands contiguously on disk and reads/writes faster.
preemptive ch. 7: A scheduler willing to stop a running process to run another (via the context switch); all modern schedulers are.
prefetching ch. 22: Guessing a page will be needed and loading it early (e.g. code page P arrives → fetch P+1) — worthwhile only when the guess has a reasonable chance of being right.
present bit ch. 18: PTE bit saying whether the page is in physical memory or swapped to disk; the hinge on which chapter 21's swapping turns (x86 fuses it with validity into a single P bit).
priority boost ch. 8: Periodically (every S) moving all jobs to the top queue — cures starvation and lets phase-changed jobs be re-learned.
priority inheritance ch. 28: The inversion fix: temporarily boost the lock-holding low-priority thread to its waiter's priority so it can run, release, and restore order.
priority inversion ch. 28: A high-priority thread stuck behind a low-priority lock holder — with spin locks it can hang the system outright, and with a middle-priority thread running, mighty T3 waits while lowly T2 rules (see: Mars Pathfinder). An intergalactic scourge.
process ch. 4: The OS abstraction of a running program — its address space, registers (PC, stack pointer), and I/O state such as open files.
process control block ch. 4: The per-process structure (PCB, process descriptor) holding its state — like xv6's struct proc.
process list ch. 4: The OS data structure tracking all processes in the system (a.k.a. task list).
producer/consumer problem ch. 30: Dijkstra's canonical synchronization problem (a.k.a. the bounded-buffer problem): one or more producer threads place items into a shared bounded buffer while one or more consumers remove them. Correct solutions need mutual exclusion on the buffer plus making producers wait when it is full and consumers wait when it is empty — a lock plus two condition variables (empty and fill).
program counter ch. 4: The register holding the address of the instruction to execute next (a.k.a. instruction pointer, IP).
programmed i/o ch. 36: PIO: data movement in which the main CPU is directly involved, copying data to or from a device one word at a time via the data register. Simple but CPU-costly for large transfers, which is why DMA is used to offload it.
proportional share ch. 9: Scheduling that guarantees each job a percentage of the CPU rather than optimizing turnaround/response (a.k.a. fair-share).
protection ch. 2: Ensuring the bad behavior of one program cannot harm other programs or the OS itself.
protection bits ch. 16: Per-segment permission bits (read / write / execute) checked by the hardware on every access; setting code read-only lets one physical copy be safely shared across processes.
race condition ch. 26: (A data race:) the result depends on the TIMING of execution — context switches at untimely points yield wrong, run-to-run-varying answers. Demonstrated forever by two threads running counter = counter + 1 (a three-instruction sequence) and losing updates.
raid ch. 38: Redundant Array of Inexpensive (or Independent) Disks: a technique that ties several disks into one logical disk to gain capacity, performance (parallelism), and/or reliability (redundancy). It presents the same block interface as a single disk, so it works transparently — you can swap a disk for a RAID without changing any software above it.
raid level ch. 38: A named RAID design choosing a specific point in the capacity/reliability/performance trade-off space: RAID-0 (striping, no redundancy), RAID-1 (mirroring), RAID-4 (dedicated-parity), RAID-5 (rotated-parity). The 'level' naming comes from the 1988 Patterson/Gibson/Katz paper.
reader-writer lock ch. 31: A lock that permits many readers to access a data structure concurrently but grants a writer exclusive access. Built from semaphores: the FIRST reader acquires the write lock (blocking writers) and the LAST reader releases it. Simple, but can starve writers and often costs more than a plain lock.
ready ch. 4: Process state: able to run, but the OS has chosen not to run it at this moment.
realloc ch. 14: Grows an allocation: new larger region, contents copied, new pointer returned.
recursive update problem ch. 43: A hazard in any never-overwrite-in-place file system: moving an inode to a new address would force updating the directory that points to it, then that directory's parent, and so on up to the root. LFS avoids it with the inode map — the directory keeps the same name→inode-number mapping, and only the imap entry changes.
red-black tree ch. 9: A balanced binary tree keeping operations O(log n); CFS stores runnable processes in one, ordered by vruntime.
redirection ch. 5: Pointing a process's standard input/output at a file — the shell's child closes a descriptor and opens the file before exec (UNIX assigns the lowest free fd).
redo logging ch. 42: The recovery style journaling uses: on reboot, scan the log and re-apply (replay, in order) every transaction that committed (has a matching TxB/TxE), writing its blocks to their final locations. Transactions not fully committed are skipped. Redundantly re-doing already-checkpointed writes is harmless.
reference bit ch. 18: PTE bit (a.k.a. accessed bit) recording that a page was touched — the raw signal replacement policies use to guess which pages are popular.
register context ch. 4: The saved register contents of a stopped process; restoring them resumes the process.
reliable communication layer ch. 48: A messaging layer built on top of an unreliable network that guarantees delivery — and usually exactly-once, in-order delivery — using acknowledgments, timeout/retry, and sequence numbers. TCP/IP is the most common example.
remote procedure call ch. 48: RPC: the dominant abstraction for building distributed systems, borrowed from programming languages. It makes executing a routine on a remote machine look almost like an ordinary local function call — the client calls a stub, and the RPC system hides the messaging, argument marshaling, and timeout/retry needed to run the code remotely and return the result.
resident set size ch. 23: VMS's per-process cap on resident pages (RSS): each process keeps at most this many pages in memory, evicting FIFO-style from its own set — a fairness guard against memory hogs that global policies like LRU can't provide.
resource manager ch. 2: The OS's role of sharing the CPU, memory, and disk among many programs efficiently and fairly.
response time ch. 7: T_firstrun − T_arrival — the interactivity metric born with time sharing.
retry ch. 48: Re-sending a message after a timeout, in hopes it gets through the second time. This requires the sender to keep a copy of the message until it is acknowledged. The combined technique is called timeout/retry.
return-from-trap ch. 2: The instruction that reverts to user mode and resumes the application where it left off.
return-oriented programming ch. 23: ROP: with injection blocked, attackers chain 'gadgets' — instruction fragments already present in the program and libc — by overwriting the stack with a sequence of return addresses. Arbitrary computation from borrowed code.
revoke record ch. 42: A journal entry (ext3) that marks a block as NOT to be replayed during recovery. It solves the block-reuse hazard: if a directory block is logged, then that block is freed and reused as user data for a new file, replaying the old logged contents would clobber the new data. Recovery scans for revoke records first and skips revoked blocks.
roll forward ch. 43: An LFS crash-recovery technique (from databases): after reading the last checkpoint region, start at the end of the log it records and scan forward through the following segments, applying any valid updates written since the last checkpoint — recovering data that would otherwise be lost between periodic CR writes.
rotating parity ch. 38: RAID-5: spread (rotate) the parity blocks across all disks instead of dedicating one parity disk (RAID-4). This removes the parity-disk bottleneck, so small random writes can proceed in parallel — throughput (N/4)·R vs RAID-4's R/2 — while keeping RAID-4's capacity ((N−1)·B) and single-failure tolerance. It has largely replaced RAID-4.
rotational delay ch. 37: The time a disk spends waiting for the desired sector to rotate under the head. On average it is about half of a full rotation (R/2). Together with seek time, one of the two dominant costs of a disk I/O.
round robin ch. 7: Run each job for a time slice, then switch to the next in the queue — great response time, nearly pessimal turnaround.
running ch. 4: Process state: executing instructions on a processor.
scheduler ch. 4: The OS component whose policy decides which ready process runs next, using history, workload knowledge, and metrics.
sector ch. 37: The atomic unit of a hard disk: a 512-byte block. Sectors are numbered 0…n−1, forming the disk's address space. Manufacturers guarantee only that a single-sector write is atomic; a larger write interrupted by power loss can leave a partial 'torn write.'
seek time ch. 37: The time to move the disk arm so the head is over the target track. It has phases — acceleration, coasting, deceleration, and settling (the settling alone is 0.5–2 ms). Along with rotation, one of the most costly disk operations; the AVERAGE seek is about one-third of a full-stroke seek.
segment ch. 16: A contiguous portion of the address space of a particular length — canonically code, heap, or stack — that the hardware relocates and bounds-checks as a unit.
segment summary block ch. 43: A small structure at the head of each LFS segment recording, for every data block in the segment, which file (inode number) and offset it belongs to. Cleaning uses it to test liveness: a block at address A is live iff, following its (inode#, offset) through the imap and inode, the inode's pointer still equals A.
segment table ch. 16: An in-memory table of segment descriptors used when there are too many segments for dedicated registers — the hardware support behind fine-grained segmentation.
segmentation ch. 16: Virtualizing memory with a base-and-bounds register pair per logical segment (code, heap, stack) instead of one pair for the whole address space, so each segment can be placed independently in physical memory and unused gaps cost nothing.
segmentation fault ch. 14: The OS's response to an illegal memory access — "you did something wrong with memory, foolish programmer" (name explained with segmentation).
segmented fifo ch. 23: VMS's replacement scheme: per-process FIFO bounded by the RSS, backed by global second-chance lists (a clean-page free list and a dirty-page list). Fault on a listed page before it's recycled and you reclaim it without disk I/O; the bigger the lists, the closer to LRU.
segregated list ch. 17: Keeping a dedicated free list for a popular request size: near-zero fragmentation and O(1) alloc/free for that size, with the open question of how much memory to dedicate to it versus the general pool.
semaphore ch. 31: Dijkstra's single synchronization primitive: an integer manipulated by two atomic routines — sem_wait() (P/down: decrement, then block while the value is negative) and sem_post() (V/up: increment, and wake one waiter if any). The initial value determines its behavior; when the value is negative, its magnitude equals the number of waiting threads. Usable as both a lock and a condition variable.
sequence counter ch. 48: A low-memory scheme for detecting duplicate messages. Sender and receiver each maintain a counter starting from an agreed value; the sender attaches its current value N as the message's ID and increments. The receiver expects N; if the incoming ID matches it delivers and increments, but if the ID is one it has already passed (a retransmission), it acks without re-delivering — preserving exactly-once.
shell ch. 5: An ordinary user program (bash, zsh, …) that reads commands and runs them via fork → exec → wait, printing a prompt in between.
shortest positioning time first ch. 37: SPTF (a.k.a. SATF, shortest access time first): a disk-scheduling policy that accounts for BOTH seek and rotation, servicing whichever request has the shortest total positioning time. It beats SSTF/SCAN (which ignore rotation) when seek and rotation are comparable, but needs exact head position and track layout — so it is usually performed inside the drive.
shortest seek time first ch. 37: SSTF: a disk-scheduling policy that services the request on the nearest track first (at the OS level, approximated as nearest-block-first, NBF). Fast, but a steady stream of near-track requests can starve requests to far-away tracks.
signal ch. 5: The UNIX mechanism for delivering external events to processes (SIGINT from control-c, SIGTSTP from control-z, …); sent with kill(), caught with signal().
silent fault ch. 45: A fault the device gives no indication of: it returns wrong data as though it were correct. Contrast a non-silent partial fault, where the disk returns an explicit error. Block corruption is the canonical silent fault, and is why checksums are needed for detection.
sjf ch. 7: Shortest Job First — run the shortest job to completion first; optimal turnaround when all jobs arrive together.
slab allocator ch. 17: Bonwick's kernel allocator (Solaris): boot-time object caches — segregated lists for hot kernel objects (locks, inodes) — fed page-multiple slabs by a general allocator, with freed objects kept PRE-INITIALIZED to skip costly init/destroy cycles.
small-write problem ch. 38: In parity RAID, a small random write must read-modify-write both the data block AND the parity block (4 I/Os via the subtractive method). In RAID-4 all parity lives on one disk, so that disk becomes a bottleneck serializing every write; small-random-write throughput is stuck at ~R/2 and does not scale with disks.
soft updates ch. 42: An alternative to journaling (Ganger & Patt): carefully ORDER all writes so the on-disk structures are never inconsistent — e.g. always write a data block before the inode that points to it. Avoids a journal, but needs intricate, file-system-specific knowledge of every structure, making it complex to implement.
software-managed tlb ch. 19: On a miss the hardware just raises an exception; an OS trap handler walks whatever page-table structure it likes, refills the TLB with privileged instructions, and returns to RETRY the faulting instruction (MIPS, SPARC).
solid-state drive ch. 44: An SSD: persistent storage built from transistors (flash), with no moving parts — unlike a hard disk. It presents the standard block read/write interface but internally uses a flash translation layer to hide flash's quirks (erase-before-write, wear-out). Much faster than disks at random I/O, but pricier per GB.
space sharing ch. 4: Dividing a resource among users in space rather than time (e.g., disk blocks belong to one file until deleted).
sparse address space ch. 16: An address space that is large but mostly unused (e.g. a huge free gap between heap and stack); segmentation accommodates it by allocating physical memory only for the used segments.
spatial locality ch. 10: After touching address x, nearby addresses are likely next (array streaming, sequential code).
spin lock ch. 28: The simplest lock: spin-wait, burning CPU cycles, until the lock frees (built on test-and-set or kin). Correct; unfair (spinners can starve); painful on one CPU (whole slices wasted if the holder is preempted), reasonable on multiprocessors with short critical sections.
splitting ch. 17: Allocator mechanism: when a request is smaller than any free chunk, split one chunk in two — return the first piece to the caller, keep the remainder on the free list.
spurious wakeup ch. 27: Some pthread implementations can wake a waiting thread when nothing actually changed — which is why the condition is re-checked in a WHILE loop, never an if: treat waking as a hint, not a fact.
sqms ch. 10: Single-queue multiprocessor scheduling — one shared queue feeds all CPUs; simple and balanced, but lock-limited and affinity-blind.
stack ch. 4: Memory region for function parameters, local variables, and return addresses; allocated by the OS at process creation.
stack property ch. 22: A cache of size N+1 always contains the contents of the size-N cache (LRU has it; FIFO and random don't) — guaranteeing bigger caches never hurt, and enabling one-pass simulation of all sizes at once.
stale cache ch. 49: The other half of the cache consistency problem: after one client (C2) has flushed its update F[v2] to the server, another client (C1) may still hold the old version F[v1] in its cache. Unless C1 re-validates before reading, it returns outdated data instead of the latest copy.
starvation ch. 8: A job receiving no CPU time at all because others perpetually outrank it — the failure mode the priority boost prevents.
stateful protocol ch. 49: A protocol in which the server maintains state about each client — for example, an open file descriptor mapping to a particular file. Such shared state complicates crash recovery: a server crash loses the state (so outstanding operations can no longer be completed), and a client crash leaks server-side resources (like the open file) that the server must somehow detect and reclaim.
stateless protocol ch. 49: A protocol in which the server keeps no state about individual clients — it does not track which files a client has open, current file offsets, or which blocks a client caches. Every request carries all the information needed to complete it. This is NFSv2's central design choice: it makes crash recovery trivial, because after a crash the server simply restarts and clients, at worst, retry their requests.
static relocation ch. 15: A loader rewriting a program's addresses at load time — no protection, and painful to move afterward.
stcf ch. 7: Shortest Time-to-Completion First (preemptive SJF) — on each arrival, run whichever job has least time left.
stride scheduling ch. 9: Deterministic fair share — stride = bignum/tickets; run the job with the lowest pass value, then add its stride to its pass.
stripe ch. 38: The set of blocks at the same position across all disks of a striped array (one 'row'). Related: the chunk size sets how many consecutive blocks land on one disk before moving to the next.
striping ch. 38: RAID-0: spread the array's blocks round-robin across all disks with no redundancy. Perfect capacity (N·B) and best-case performance (all disks in parallel), but zero reliability — any one disk failure loses data. Serves as the performance/capacity upper bound for the other levels.
stub generator ch. 48: The RPC 'protocol compiler' that takes an interface definition and generates the glue code: a client stub (which marshals the arguments into a message, sends it, waits, and unmarshals the reply) and a server stub (which unmarshals the request, calls the real function, and marshals the reply). Automating this removes a class of hand-written packing bugs and can optimize the code.
sub-block ch. 41: A 512-byte fragment FFS could allocate to a small file so it doesn't waste a whole 4 KB block (internal fragmentation). A file grows in sub-blocks until it reaches a full block, then FFS copies them into one 4 KB block. (Costly copying was mostly avoided by having libc buffer writes into 4 KB chunks.)
superblock ch. 40: A block (usually the first) holding file-system-wide info: how many inodes and data blocks there are, where the inode table starts, and a magic number identifying the file-system type. On mount, the OS reads the superblock first to initialize the volume.
superuser ch. 5: The administrative user (root) who can control any process and run powerful commands; use sparingly.
swap daemon ch. 21: The background thread (a.k.a. page daemon; 'daemon' via Multics from Maxwell's demon) that evicts pages when free memory dips below the low watermark, until the high watermark is restored — enabling clustered swap writes along the way.
swap space ch. 21: Disk space reserved for pages pushed out of memory, read and written in page-sized units; its size caps how many pages a system can have in use, and the OS tracks each swapped page's disk address (stashed in the PTE's PFN bits).
symbolic link ch. 39: A soft link: a distinct file type whose data is the pathname of another file (ln -s). Unlike a hard link it can cross file systems and point to directories, but if the target is removed it becomes a dangling reference (points to a nonexistent path). Its size equals the length of the stored pathname.
synchronization primitives ch. 26: 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.
system call ch. 2: A controlled entry into the OS (via trap) that raises the privilege level so the kernel can do work on a program's behalf.
system call number ch. 6: The number user code places in a register/stack slot to request a specific service — indirection that prevents jumping to arbitrary kernel addresses.
tcp ch. 48: The Transmission Control Protocol (TCP/IP), the most commonly used reliable communication layer. On top of unreliable IP it adds acknowledgments, sequence numbers, retransmission, congestion control, and many other optimizations to deliver an ordered, reliable byte stream.
temporal locality ch. 10: Data accessed now is likely accessed again soon (loop variables, instructions).
test-and-set ch. 28: The atomic exchange instruction: return the old value at an address while storing a new one — test and set as ONE atomic act (x86 xchg, SPARC ldstub). Enough to build a working spin lock, which pure loads/stores provably are not.
thrashing ch. 22: The state where memory demand exceeds physical memory and the system pages constantly, making little progress — met historically with admission control, and in Linux with the out-of-memory killer.
thread ch. 2: A function running within the same memory space as other functions, with more than one active at a time.
thread control block ch. 26: The TCB: per-thread saved state (PC, registers) inside a process — the PCB's smaller sibling. Switching threads saves/restores TCBs but keeps the SAME page table, since the address space is shared.
thread safe ch. 29: A data structure with locks added so multiple threads may use it concurrently and still get correct results. Exactly where the locks go decides both correctness and performance.
thread throttling ch. 31: Admission control via a semaphore: initialize it to N and bracket a region of code with sem_wait()/sem_post() to cap how many threads run that region at once — e.g. keeping a memory-intensive section from over-committing memory and thrashing.
thread-local storage ch. 26: Each thread's own stack — where its locals, arguments, and return values live. A multi-threaded address space holds one stack per thread, scattered through the space (ruining the tidy two-ends layout, mostly harmlessly).
ticket ch. 9: A token representing a share of a resource; percent of tickets held = share received. Reusable far beyond CPUs (e.g., hypervisor memory).
ticket currency ch. 9: Users allocate tickets to their jobs in a private currency; the system converts to global tickets before the drawing.
ticket inflation ch. 9: A process raising/lowering its own ticket count — sensible only among mutually trusting processes.
ticket lock ch. 28: Mellor-Crummey/Scott: myturn = FetchAndAdd(&ticket); spin until turn == myturn; unlock increments turn. The ticket guarantees eventual progress for EVERY thread — the fairness that plain spin locks lack.
ticket transfer ch. 9: Temporarily handing your tickets to another process — e.g., a client boosting the server working on its request.
time sharing ch. 4: Sharing a resource by letting one entity use it for a while, then another — how the CPU illusion is built.
time slice ch. 7: The quantum a job runs before round robin switches (a multiple of the timer-interrupt period).
timeout ch. 48: A timer the sender sets when it sends a message; if no acknowledgment arrives before the timer fires, the sender concludes the message (or its ack) was lost. Choosing the value well matters — too short wastes resources on needless resends, too long hurts perceived performance.
timer interrupt ch. 6: A hardware timer raising an interrupt every few milliseconds, halting the running process and running an OS handler — how the OS regains control without cooperation.
tlb ch. 19: Translation-lookaside buffer: a small, fast, fully-associative cache of VPN→PFN translations inside the MMU, checked before the page table on every reference — the hardware that 'in a real sense makes virtual memory possible'.
tlb coverage ch. 19: The total memory the TLB's entries can map at once; touch more pages than that in a short window and misses dominate (Culler's Law: RAM isn't always RAM). Larger pages stretch it.
tlb hit ch. 19: The desired translation is already in the TLB: the physical address forms in a few cycles with no page-table access — the common case everything is designed around.
tlb miss ch. 19: The translation is absent: the page table must be consulted (extra memory reference or worse), the TLB updated, and the instruction retried — the retry then hits.
track ch. 37: A concentric circle of sectors on a platter surface. A single surface holds many thousands of tightly packed tracks (hundreds fit within a human hair's width). A read/write head, mounted on a movable disk arm (one head per surface), positions over the desired track.
track buffer ch. 37: A small memory inside the drive (a disk cache, historically the track buffer, usually 8–16 MB) that holds data read from or written to the platters — e.g. on reading one sector the drive may cache the whole track to answer later same-track requests quickly.
track skew ch. 37: An angular offset in sector numbering between adjacent tracks, arranged so that after switching tracks a sequential read finds the next block just arriving under the head — rather than having just missed it and paying nearly a full rotation.
transaction ch. 42: The unit of a journaled update: a transaction-begin block (TxB, with the target addresses and a transaction id/TID), the blocks being updated (metadata and, in data journaling, data), and a transaction-end/commit block (TxE, with the same TID). A transaction is atomic — recovery applies it fully or not at all.
transparency ch. 13: The VM illusion must be invisible to programs — a transparent system is one that's hard to notice (not the FOIA kind).
transparent access ch. 49: The goal that a distributed file system look and feel just like a local one: the client application uses the same standard API (open, read, write, close, mkdir, …) and gets the same view of files, differing only — perhaps — in performance. No one would want a file system that required a different, painful set of APIs.
trap ch. 2: A hardware instruction/event that jumps into a pre-registered OS handler while raising the privilege level.
trap handler ch. 6: The pre-registered kernel code the hardware jumps to when a trap or interrupt occurs.
trap table ch. 6: The table of handler addresses the OS installs at boot (privileged); tells the hardware what kernel code runs on each syscall/interrupt/exception.
trim ch. 44: A storage command by which the file system tells the SSD that a block range is no longer in use (e.g. after a delete). Because a log-structured FTL keeps a flexible logical→physical map, knowing a block is dead lets it drop the mapping and reclaim the space in garbage collection — a case of the implementation shaping the interface.
turnaround time ch. 7: T_completion − T_arrival — the performance metric batch systems care about.
two-phase lock ch. 28: Spin briefly first (the lock may free any moment), THEN sleep if not acquired (Dahm locks, 1960s; Linux's futex lock is a one-spin variant). A hybrid whose payoff depends on hardware, thread counts, and workload.
udp ch. 48: The User Datagram Protocol (UDP/IP), the ubiquitous unreliable communication layer. A process uses the sockets API to create an endpoint and exchange fixed-size datagrams; UDP includes a checksum to detect some corruption but provides no protection against, or notification of, packet loss.
uninitialized read ch. 14: Reading malloc'd memory before writing it — you get whatever unknown bytes were there.
unlink ch. 39: The system call that removes a name from a directory (what rm uses). It is called unlink, not delete, because it removes one link to an inode and decrements the inode's link count; the file's inode and data blocks are freed only when the count reaches zero.
unreliable communication layer ch. 48: A messaging layer that makes no guarantee of delivery — packets may be silently lost, with the sender never informed — leaving applications that can tolerate loss to cope themselves. UDP is the canonical example, and using such a layer is an instance of the end-to-end argument.
update visibility ch. 49: One half of the cache consistency problem: the question of when updates made by one client become visible to other clients. If a client buffers its writes in its local cache before propagating them to the server, other clients that read the file in the meantime will see an old version — until the buffered writes reach the server.
use bit ch. 22: The hardware bit set to 1 whenever a page is referenced (a.k.a. the reference bit; first in Atlas) — hardware sets, the OS clears. The raw material from which clock and every LRU approximation is built.
user ch. 5: A logged-in identity that may launch and control only its own processes; the OS parcels resources among users.
user mode ch. 2: The restricted hardware mode applications run in — no direct I/O or privileged operations.
valid bit ch. 18: PTE bit marking a translation as usable; unused address-space pages are marked invalid and get NO physical frames — the trick that makes sparse address spaces cheap (access → trap, likely termination).
versioning file system ch. 43: A file system that keeps old versions of files rather than reclaiming them — letting users restore accidentally overwritten or deleted data. LFS could be one (the old versions are already there as 'garbage'); NetApp's WAFL turns LFS's cleaning problem into this feature via snapshots.
virtual address ch. 13: An address as seen by a running program — every address a user program generates or prints; translated to physical by OS + hardware.
virtual file system ch. 49: The VFS / vnode interface, introduced by Sun to support NFS, that lets multiple file-system implementations plug into a single operating system. VFS-level operations act on a whole file system (mount, unmount, sync all dirty writes); vnode-level operations act on a single file (open, close, read, write). A new file system just implements these methods; the framework connects system calls to it and handles generic functions like caching. Some form of it now exists in Linux, the BSDs, macOS, and Windows.
virtual memory ch. 13: The OS subsystem providing each process the illusion of a large, sparse, private address space atop shared physical memory.
virtualization ch. 2: Transforming a physical resource (CPU, memory, disk) into a more general, powerful, easy-to-use virtual form.
volume ch. 50: In AFS, a unit of files that an administrator can relocate between servers to balance load. Volumes were introduced to fix the load-imbalance problem of the first AFS version; the volume identifier is also the first component of a file identifier (FID).
von neumann model ch. 2: The fetch–decode–execute model: a processor runs one instruction at a time, in order.
voo-doo constant ch. 8: A magic parameter (like the boost period S) that seems to need black magic to set correctly; avoid when possible (Ousterhout's Law).
vruntime ch. 9: Virtual runtime a process accrues while running (scaled inversely by its weight); CFS always runs the minimum.
wait ch. 5: UNIX call letting a parent pause until a child finishes (waitpid() is the fuller sibling); also reaps the zombie.
wait-free ch. 32: A stronger form of lock-free synchronization guaranteeing that EVERY operation completes in a finite number of steps (no unbounded retry loops). Harder to build than lock-free; a few wait-free structures have made their way into real systems, including Linux.
watermarks ch. 21: The high/low free-memory thresholds (HW/LW) governing proactive eviction: below LW the swap daemon wakes and frees pages until HW are available, so the fault path rarely has to evict synchronously.
wear leveling ch. 44: The FTL activity that spreads program/erase cycles evenly across all blocks so they wear out at roughly the same time (rather than a few hot blocks dying early). Log-structuring helps, but the FTL must also periodically migrate long-lived data out of cold blocks so those blocks take their share of writes.
wear out ch. 44: Flash's main reliability limit: each program/erase (P/E) cycle leaves a little extra charge in a block until 0s and 1s can no longer be told apart and the block dies. Rated lifetimes are ~10,000 P/E cycles (MLC) to ~100,000 (SLC). Avoiding uneven wear is why SSDs do wear leveling.
whole-file caching ch. 50: AFS's defining technique: on open() the entire file is fetched from the server and stored on the client's local disk; all subsequent read() and write() calls are serviced purely locally with no network traffic; on close(), if the file was modified, the whole file is flushed back to the server. It contrasts with NFS, which caches individual blocks in client memory.
work stealing ch. 10: A low-occupancy queue occasionally peeks at a fuller one and steals jobs; peek frequency trades overhead against imbalance.
working set ch. 22: The set of pages a process is actively using (Denning). If the running processes' working sets fit in memory, progress happens; if not, thrashing.
workload ch. 7: The collective description of the processes/jobs running in a system; the more you know about it, the better your policy.
worst fit ch. 17: Free-list strategy: return the LARGEST chunk, hoping to keep leftovers usefully big — studies show it performs badly, with excess fragmentation and full-search overheads.
write amplification ch. 44: The ratio of write traffic the FTL actually issues to the flash divided by the write traffic the client issued to the SSD. Extra writes come from garbage collection, block-mapping copies, and wear leveling. High write amplification wastes flash endurance and hurts performance; minimizing it is a core FTL goal.
write barrier ch. 42: A mechanism that forces write ordering: when a barrier completes, all writes issued before it are guaranteed on disk before any issued after. Needed because disk write caches (immediate reporting) otherwise let writes reach the platter out of order — which would break journaling. (Some disks cheat and ignore barriers for speed.)
write buffering ch. 40: Delaying writes in memory (typically 5–30 s) before committing them to disk. It lets the file system batch updates, schedule them efficiently, and even cancel them (create-then-delete). The cost is the durability/performance trade-off: buffered writes are lost if the system crashes first.
write-back caching ch. 37: A disk-cache write policy (a.k.a. immediate reporting) that acknowledges a write as soon as the data reaches the drive's memory — making the drive appear faster, but risking correctness if a crash occurs before the data hits the platter (dangerous when order matters, e.g. journaling). The safe alternative is write-through, which acks only after the data is actually on disk.
yield ch. 6: A system call that does nothing but hand the CPU to the OS — the cooperative approach's way to share.
zombie ch. 4: Final process state: exited but not yet cleaned up, so the parent can read the return code via wait().