The cost ledger sums exactly: ~1.5 µs served from the page cache, ~100 µs on an NVMe miss, ~13 ms on a disk seek. Each hop names its home topic — miss handling is where the whole storage stack pays rent.

sendfile removes the user-space copy; accept queues and epoll batching remove the idle wakeups. The per-request ledger is the whole event-loop module compressed into one request.

The cost lands on the client: attribute caches go stale inside their timeout window, and writes need a COMMIT (RPC 21) to be durable. v3’s 22-procedure protocol fixes failure recovery by making every request replayable.

A namespace is an indirection layer: the same kernel object gets a different name inside each view. PID namespaces nest so one process is pid 1 inside and ordinary outside; the init process doubles as the reaper for the whole namespace.

The no-internal-process rule forces a clean shape — leaves hold processes, interior nodes hold policy. v1’s parallel trees collapsed into v2’s single hierarchy because delegating the same resource along two trees had no sane semantics.

cpu.stat counts throttled periods separately from running ones: 100ms quota in a 100ms period means a burst can stall up to a full window. Raising period smooths the tail at the price of coarser enforcement.

The ladder of thresholds (low → high → max) separates protection from pressure from enforcement — memory.low protects a group’s workingset from reclaim by others. The OOM-killer’s victim choice scores against the group’s limit, not the system’s.

Copy-up on first write is the hidden cost: a small edit to a big file pays a whole-file copy. Whiteouts encode deletes in the upper layer, and image pulls deduplicate layers across containers on the same host.

x86 circa-2000 failed the test (Robin & Irvine counted 17 sensitive-unprivileged instructions); binary translation and paravirtualisation were the workarounds before hardware support arrived.

KVM turns Linux into the hypervisor — the guest runs in non-root, exits route through the KVM loop to QEMU for device emulation. Exit cost × exit rate is the whole performance story.

Virtqueues put the ring in shared memory so a batch costs one notification, not one exit — measured exits/packet drop from ~1 to 0.06 in the worked batch model. vhost moves the virtio backend into the kernel; SR-IOV removes it entirely behind the IOMMU.

Unix mode bits are one cell-compression scheme; least privilege, complete mediation and fail-safe defaults are the principles the matrix makes precise.

POSIX ACLs and file descriptors are the two encodings you already use; a capability delegates by passing the token, while an ACL delegates by editing the object. Revocation is free in one model and a hunt in the other; ambient authority is the ACL model’s blind spot.

Real/effective/saved UIDs let passwd write /etc/shadow; dropping privilege correctly needs all three. The compiler-into-TMPDIR attack is the pattern: the deputy checks the caller’s authority but acts on its own.

Permitted/effective/inheritable sets transform at exec by rules that decide what a setuid-root binary actually keeps. File capabilities attach the set to the binary, so a daemon can bind port 80 without owning the machine.

Timer sampling is cheap but blind to its own period; PMU overflow sampling counts real events. Error bars are binomial — n = z²p(1−p)/e² samples for ±e at confidence z — and unwinding is the choice between frame pointers, DWARF and ORC.

Utilisation is time-busy; saturation is queued work (run queue depth, PSI stall); errors are the explicit counter. USE catches the burst hidden inside an average — the figure shows how a 50%-busy disk can carry a 100%-saturated window.

The fix is open-loop arrival and service-time vs response-time separation; Tene’s QCon result is the canonical example. Every load generator that waits synchronously inherits the bias.

O_NONBLOCK turns a blocking read into a question; busy-polling burns U = np/Δ of a core per descriptor. The thread-per-connection alternative fails at scale because a thread’s cost is a stack plus a scheduler slot, not zero.

fd_set is consumed by the call and capped at 1024; pollfd separates requested events from returned revents so the array survives. The cost is the scan, not the wait — it scales with what you watch, not what fires.

Wait-queue callbacks on the file move a descriptor to the ready list — the kernel never scans. Edge-triggered requires drain-to-EAGAIN discipline (the pipe-hang example); EPOLLEXCLUSIVE splits wakeups to kill the thundering herd.

A 5 ms blocking read delays all queued work behind it; libuv’s answer is a small threadpool (default 4) for genuinely blocking calls. One loop per core removes the shared-state question entirely.

One logical update fans out into several disk writes; any suffix of them may land. Append corrupts data, lose-a-block leaks it, and a torn write leaves the block half-old, half-new — the state enumeration is the argument.

Reference counts get reconciled (nlink, block bitmaps, inode bitmaps) and unreachables get filed into lost+found. The cost is proportional to capacity, not damage — minutes on small disks, unbounded on modern ones, which is why journaling replaced it.

Commit ordering is the correctness: data/metadata to the journal, TxEnd last, then checkpoint to home locations. Replay idempotence means re-running an already-applied transaction is harmless.

Metadata-only journaling plus ordered data-before-commit is the ext4 default: it keeps old blocks unreachable after a crash without paying double writes for file contents. Writeback loses even that; full journal costs the most and protects the most.

Overwrite-in-place enumerates 2ⁿ−2 corrupt states; rename gives exactly two (old or new). The directory fsync after rename is the step everyone forgets — the name itself must reach the disk.

The layout answers “where does inode 32’s bytes live” with pure arithmetic: table block + (ino − 1)/per-block to get the sector. xv6’s variant renames the regions but keeps the division of labour.

Capacity is B(d+p+p²+p³) — one block address fanning out quadratically. I/O per offset climbs with tier: direct is one read, triple-indirect costs four. Sparse files leave holes as zero pages for free.

ext4 packs the extent tree root inside the inode and grows through extent nodes; uninitialized extents reserve space without leaking stale bytes. The cost shows up at fragmentation, where runs shrink and the index reverts toward per-block.

ext4_dir_entry_2 packs name→inode records; dx_root/dx_node hash filenames (siphash) into leaf blocks. The open path’s real cost is the I/O count per component, not the entry format.

McKusick’s FFS measured file-system locality: most files are small, directories are used together. The 48 KB/1 MB large-file rule caps one file’s group residency to preserve space for siblings — locality bought with a 10% capacity reserve.

exec needs a map, not a table of contents — the program header carries loadable segments with permissions and p_vaddr ≡ p_offset (mod p_align) so each segment lands page-aligned. .bss exists only in headers: file bytes end, memory continues zeroed.

Arguments land before a format is chosen so the new image can see them; once a handler commits, there is no old program to return to. The initial stack is the argument-passing ABI: argv, envp and the auxiliary vector.

The PLT defers relocation cost to first use — the table you filled is also a target, which is why RELRO/BIND_NOW exist. What “first definition wins” means: symbol interposition lets an earlier object override even the owner’s own references.

Load order becomes semantics: LD_PRELOAD works by inserting itself early in the search order, and a library’s own calls can be intercepted by a later-loaded sibling.

read() is a lookup then a copy; the cache deliberately occupies otherwise-idle memory and yields it under pressure. Expected read cost is a hit-rate question, and a cache can never help the first read.

msync flushes a range but is not the durability contract. The edges are SIGBUS on accessing past a truncated end and the zeroed partial last page.

A flagged folio acts as the tripwire that triggers the next window; fadvise/madvise let the caller declare the pattern instead. The arithmetic: one large request replaces a page fault or read per page.

Buffered writes are a promise the flusher threads keep; the throttle shapes how much dirty data can accumulate — the loss window between write() and media. The balance protects readers and devices, not your data.

fdatasync skips metadata readers cannot see; a name lives in its directory, so durability of a create needs the directory fsynced too. The device cache sits below the filesystem — fsync flushes it, and an fsync can still lie about the past on misbehaving hardware.

Alignment is a contract (logical-block granularity, discoverable via STATX_DIOALIGN/BLKSSZGET); EINVAL or silent buffered fallback are the failure modes. Direct is not durable — fsync is still owed.

stat reports the inode, not the content. Names live in directories and point at inodes; the inode itself has no name.

Two descriptors can share one description (after fork or dup), so their reads advance a common offset; a second open() gets an independent offset.

Resolution walks one lookup per component from / or the working directory; openat names the starting point explicitly. Each lookup is a scan of one directory file.

link() cannot name a directory or cross filesystems. The open-but-unlinked file is a real state: the inode outlives its names, which is how anonymous temporary files work.

A symlink can point across filesystems and at directories, but it can dangle — the target path may name nothing. Resolution bounds the substitution chain (ELOOP) to kill loops.

The check picks exactly one class — owner bits decide for the owner even when group would deny. Directories reuse the bits with different verbs: x is search, w is create/remove, r is listing.

umask subtracts bits at creat/open; the sticky bit is what makes shared /tmp safe. Together they are the permission model’s configuration surface.

The mount table records grafts so one tree covers many devices. Propagation types decide whether a new mount is visible in other namespaces — the detail that makes container mounts private.

ext4, tmpfs, NFS and procfs all answer read through the same surface: the objects dispatch per-filesystem work through ops tables. Resolution stitches dentries; the objects buy a uniform API, not uniform performance.

Without it every open() re-scans every directory on its path. Expected step cost is h·c_hit + (1−h)·c_miss, so hit rate — not lookup speed — decides what resolution costs.

Magnetic geometry decides where a byte lives; a random 4 KB read is hundreds of times slower per byte than sequential because positioning, not transfer, is the cost. Drive internals — remapping, zoned density — blur the clean numbers.

The elevator algorithms trade a little positioning for a guarantee every request is reached. Positioning time is more than distance — rotation matters too, which is what SPTF weighs.

Erase blocks are big, program pages small, and a page cannot be rewritten in place — so the FTL writes elsewhere and remaps. A direct map fails immediately; hybrid mapping trades translation-table memory for copying.

A switch merge works only when the log block fully shadows its data block; a full merge copies every live page. The merge choice is where GC cost is actually decided.

Adjacent bios coalesce into one request, which is where most of the block layer’s value sits. Requests then flow through per-CPU software queues mapped onto hardware queues (blk-mq) and are found at completion by tag, not search.

RAID 0 spends nothing and survives nothing; RAID 1 halves capacity for a mirror; RAID 10 stripes mirrors and survives more second failures than RAID 01’s mirrored stripes. S/R/T scorecards make the comparison mechanical.

The access crosses three namespaces — virtual, physical, bus — and the target is memory that is not memory: reads can have side effects and the region cannot be cached or reordered like DRAM. Registers concentrate authority, so they stay kernel-only.

The driver polls status, writes command, then moves data. Every richer interface — descriptor rings, doorbells — is this protocol scaled; count register touches, not bytes, when costing it.

Mogul’s measurements: interrupts run at the highest priority, so each packet’s fixed IRQ cost is paid before any packet is processed. Beyond saturation the system is busy doing nothing.

Interrupts handle the idle end, polling handles the loaded end — the hybrid removes the saturation threshold rather than moving it. The poll budget bounds both latency and how long the CPU serves one device.

Coalescing stretches the overload threshold by dividing c_i by k, but adds latency per batch — it moves the cliff, the hybrid removes it.

Programmed I/O pays a register access per word; DMA pays a setup cost once per transfer. The saving is a whole copy the CPU never performs.

Buffers must be pinned and translated — a virtual address means nothing to hardware. The descriptor ring is the status/command/data protocol expressed in memory.

Uniform discovery over non-uniform hardware: the kernel asks the class, the driver answers for its device. New interfaces get added where the three genuinely cannot express the device.

Chou’s SOSP’01 study found driver error rates several times the rest of the kernel. The count motivates containment: IOMMU bounds what a driver bug can reach; user-space drivers trade performance for a crash boundary.

Reads block while empty and writes block while full — the wait at each end is the flow control, and capacity sizes only the burst slack. Both ends are reference-counted: EOF and SIGPIPE are the signals those counts send.

The bound is what makes a shared write end usable for records — concurrent small writes never interleave. Larger writes may split arbitrarily, so framing above the bound is the application’s problem.

mkfifo creates the name; open-for-read and open-for-write meet at the same kernel object a pipe() call would have made. The name persists; the buffer exists only while ends are open.

shm_open names it, ftruncate sizes it, mmap with MAP_SHARED shares the pages — the transfer path is then ordinary loads and stores with no per-byte kernel copy.

PTHREAD_PROCESS_SHARED mutexes and futexes key on the physical word, so they name the same state in every mapping. A private-process synchroniser placed in shared memory coordinates nothing.

Acquisition returns EOWNERDEAD plus a duty to repair the protected state and call consistent(); skipping it poisons the lock permanently with ENOTRECOVERABLE.

mq_send/mq_receive move whole messages. The queue pays the same two copies as a pipe; what it buys is boundaries, priority order and a blocking discipline on a bounded capacity.

Priority orders the queue; FIFO orders equal priorities. A reader that wants strict chronological order must send everything at one priority.

bind names the endpoint; listen and connect choose who initiates. accept returns a second socket drawn from a bounded queue — the listener and the connection are different objects.

A completed handshake sits in the queue until accepted; when the queue fills, new handshakes are refused or dropped. Backlog absorbs burst arrivals, not a sustained rate above the accept loop.

send blocks when its buffer is full; recv blocks when its buffer is empty. Readiness APIs report the state of those objects, and errors are reported deferred at the next call.

Pathnames persist and need unlink; abstract names (Linux, a leading NUL byte) live in a separate namespace with no filesystem entry; socketpair needs no name at all.

The kernel installs the received description as a new descriptor in the receiver — an integer copied as data would name nothing there. This is how a privileged daemon hands a client an opened resource.

Finer granularity buys parallel access at the price of more lock records, more acquisition order obligations and new deadlock edges. The serial fraction, not the lock count, sets the speedup ceiling.

The coupling preserves reachability of the node being locked but serialises concurrent traversals over the same prefix — the throughput gain lives in the disjoint subtrees, not the shared head.

Accuracy degrades to ±(S × P) for threshold S on P CPUs in the classic design. Reads pay a global lock; the trade is exactness for update contention.

Removed at 2.6.39 after a decades-long push to per-subsystem locking. Its lesson generalises: a global lock is a migration path, not an end state.

Writes on different words of one line still invalidate each other’s copies. Padding to a line boundary or per-CPU allocation removes the ping-pong; the variables were never logically shared.

Eliminates coherence traffic for that datum at the cost of an aggregate-read pass and T × footprint. Correct only when readers accept a merged or sampled value.

Waiting atomically releases the associated lock; returning waiters reacquire it before proceeding. A condition is checked, never stored, in the variable itself.

Signal and broadcast both require re-testing in a loop. Direct handoff can transfer ownership to a woken waiter but is a distinct, stronger discipline.

Sleep must be atomic with lock release, or a wakeup landing between predicate check and block is missed. Missed wakeups are a protocol failure, not a scheduling accident.

The invariant s = s₀ + n_V − n_P holds only if every caller honours the discipline. A semaphore admits no inspection of which thread released it or why.

A binary semaphore used for ordering (starting at 0) is not a lock; a counting semaphore used as a mutex is not an ordering device. Role confusion produces subtle deadlocks.

The reusable barrier needs two phases: reusing one turnstile lets a fast thread lap a slow one and pass twice. Counting arrivals alone does not order departures.

The implicit entry lock serialises method bodies but does not choose a handoff discipline. Java’s synchronized/wait is Mesa-style; signal-and-urgent-wait (Hoare) is not.

The signaller then waits. J { c.wait } J ∧ B_c and J ∧ B_c { c.signal } J characterise the proof contract; Mesa’s weaker guarantee forces the while-loop idiom.

Each condition alone is insufficient; deadlock needs all four simultaneously. Denying any one of them prevents deadlock, which is why prevention proofs name the condition they remove.

A cycle is necessary but not sufficient when resources have multiple instances; sufficiency additionally needs every resource in the cycle to have exactly one instance.

Symmetric pickup order is what makes the cycle reachable. Breaking symmetry (one reversed philosopher, a waiter, or global ordering) each removes a different condition.

A consistent order makes the lock graph a DAG, so circular wait cannot arise. Dynamic order discovery and hidden nested acquisitions are the practical failure modes.

It breaks hold-and-wait but adds livelock risk and forces unwinding of partial work. Bounded retries need a live progress argument, not just a probability claim.

It flags an order violation the first time an inverted edge appears — it proves correctness for observed behaviour only, not for unexecuted interleavings.

An unsafe state is not yet a deadlock — it means the system can no longer promise completion. Avoidance keeps the system in safe states by pretending each grant.

Each check runs an n × m simulated-completion search. The scheme needs declared maximums and a fixed resource pool — requirements real workloads rarely satisfy.

A cycle in the wait-for graph is deadlock regardless of instance counts. Keeping it current costs an update on every wait edge, which is why detection runs periodically.

The victim’s cost and starvation bound matter: repeatedly picking the cheapest thread starves it. Rollback needs a checkpoint the application actually provides.

Atomicity violations (unprotected check-then-use) and order violations (missing happens-before) cover ~97% of the studied non-deadlock bugs — and almost all reproduce with two threads.

The lost-update simulator assumes atomic instruction steps and sequential consistency. Conflicting unsynchronized ordinary C++ accesses can instead produce undefined behavior; atomic accesses can still implement a higher-level race.

A protocol must cover every conflicting participant and the entire invariant, not merely one write or one processor.

Bounded waiting counts competing admissions, not elapsed time. Eventual scheduling and finite holds remain explicit assumptions.

The proof assumes indivisible sequentially consistent accesses. Ordinary language variables or buffered machine stores do not inherit that proof automatically.

Exchange, compare-and-swap and fetch-and-add provide different transitions. Atomicity does not imply fairness, bounded latency or a multiword transaction.

A failed update must recompute and revalidate from the new observation. Equality does not certify that the value never changed in between.

RISC-V SC returns zero for success and nonzero for failure and consumes the reservation either way. Constrained-loop eventuality is not per-hart starvation freedom.

Per-location cache coherence and individually atomic accesses do not by themselves establish this cross-location model.

The restricted x86-TSO model uses FIFO publication and newest-own-write forwarding. A different-address load can proceed while an earlier store remains buffered.

An acquire that observes the relevant release can establish publication. The operation names alone do not impose a full fence or validate later unsynchronized mutations.

Combine an atomic claim with ordering. True kernel spinning locks prohibit sleeping; local interrupt safety is separate from cross-CPU exclusion.

Ticket waiters poll one serving counter; MCS waiters poll their own nodes. Both depend on scheduled participants completing their obligations; FIFO does not bound elapsed waiting.

Waking is neither immediate execution nor necessarily ownership. Free-and-recheck and direct handoff are distinct policies.

Registration and scheduler-state publication must coordinate with wakeup. Park must not overwrite an early runnable transition with blocked state.

Classic Linux futex words are aligned 32-bit values. WAIT/WAKE alone supplies neither owner tracking nor FIFO admission; the ordinary three-state model retains a conservative wake obligation.

A fixed budget equal to block/resume CPU cost is two-competitive only in the stated independent-wait model. Owner-running hints do not decide ownership or guarantee latency.

Inheritance propagates transitively and changes when dependencies disappear. It does not repair lock cycles, shorten I/O or supply a universal blocking-time bound.

A ceiling is the highest priority of any potential user. Its single-critical-section blocking theorem has fixed-priority uniprocessor and resource-discipline assumptions; immediate-ceiling variants are not interchangeable.

Read-only refers to the protected invariant, not an operation’s name. Shared reader admission may still modify centralized metadata.

Readers can indefinitely extend a reader phase; continuous writers can exclude readers. FIFO leading-reader batches prevent later-request bypass under finite-hold and eventual-scheduling assumptions.

Both parent and child lose writable access to a shared frame. A COW fault copies for a shared owner or promotes an exclusive owner; immutable pages must not gain write permission.

The marker distinguishes private writable data from immutable code. The teaching reference count tracks mapping owners; production page references include other uses and pins.

A VMA can contain many absent pages. Splitting its policy record does not necessarily allocate or copy data frames.

These operate at page-covered granularity. PROT_NONE retains a mapped reservation; a hole has no mapping. MAP_FIXED can overwrite existing mappings.

Linux v6.12 documents a B-tree with range iteration and optional gap searching. Its inclusive range endpoints differ from half-open VMA notation.

An order-k block contains 2^k pages. XOR of its aligned page offset with 2^k identifies a candidate buddy, whose state and allocation domain still require validation.

Adjacent equally sized blocks need not be siblings. Total free capacity does not establish an eligible high-order contiguous extent.

Chunk extent includes bookkeeping and slack. Bins locate a fit, while physical boundary information locates neighbors for coalescing.

In glibc 2.40 PREV_INUSE describes the previous chunk. A previous-size field is meaningful under the matching free-state condition; it must not be read blindly.

glibc 2.40 can adapt the initial threshold. Existing free space can satisfy larger requests, so a size above the initial default does not guarantee a syscall.

Legal region, permitted operation and current residency are distinct. Populate successfully before publishing the mapping, then retry the faulting instruction.

Backing may be file contents, zero-fill or saved private data. A swap location is not a physical frame number, and not every page fault requires a storage read.

Minor does not mean free. Exact counters follow OS accounting, while a TLB miss can occur without either class of page fault.

Replacement comparisons hold the trace, frame count, initial state and cost model fixed. Multiprocess page identities must distinguish contexts or identify real shared backing.

Offline optimality minimizes unit-cost faults for equal pages and interchangeable frames. It does not automatically minimize dirty writes or elapsed time.

Reloading a previously evicted page creates a new admission. More capacity changes the miss history and can change later queue order unfavorably.

The canonical FIFO trace has nine faults at three frames and ten at four. This is not a claim that extra RAM generally hurts performance.

With compatible initial states, every larger-cache miss is also a smaller-cache miss, giving nonincreasing fault counts. This stack is unrelated to a call stack.

Exact recency gives the stack property, but not a guarantee of beating FIFO on every trace. Maintaining OS-visible order on every memory reference is costly.

Under this convention a repeated page hits in k-frame exact LRU when distance is less than k. A first touch remains a cold miss.

Sleator–Tarjan compares LRU with k frames to MIN with h ≤ k, including an initial-state allowance. The bound is not a latency prediction.

A hit sets its bit without moving the hand. The quiescent all-set case needs k+1 inspections; concurrent references and ineligible frames need additional progress controls.

Submission is not completion. Reuse requires successful preservation when needed, handling redirtying and safe retirement of old mappings.

At constant shared scan speed v and separation d frame positions, the observation interval is d/v seconds. Variable movement changes that interval.

Denning uses process time; the executable lesson uses the last Δ references. The estimate is not resident size or guaranteed future demand.

A threshold band reduces oscillation. Compulsory faults, phase changes and unavailable spare frames limit what growth can accomplish.

Full RAM alone is not evidence. Repeated displacement of active pages can leave CPUs idle while paging work and storage waits grow.

Memory some tracks partial stalls; full tracks simultaneous stalls of all non-idle tasks in scope. Overlapping task waits must not be added as elapsed pressure.

Reducing concurrency can outperform increasing runnable work during memory pressure. Suspending a task alone does not release its physical pages.

Commit charge differs from virtual size and resident usage. Linux strict admission includes configured allowance and applicable reserves.

Optimism helps sparse reservations but moves some failures later. Strict accounting does not remove local allocation constraints or guarantee absence of OOM.

Linux v6.12 counts resident, swap and page-table pages plus an integer-scaled adjustment. Adjustment −1000 excludes a task before scoring.

The same numeric VA can reach different physical bytes in different contexts. Intentional shared mappings do not imply that all memory is shared.

The teaching model adds base to VA only after checking the entire access fits. A size bound is not an ending physical address.

Its interface depends on the architecture: historical base-and-bounds is not the contemporary Sv39 page-table mechanism.

Independent placement avoids reserving inter-region gaps. Each physical segment remains contiguous in this model, creating variable-size allocation constraints.

An embedded list stores nodes in the free blocks themselves. Splitting must leave enough bytes for a usable node or absorb the remainder.

List adjacency alone is not address adjacency. Coalescing cannot cross live storage, and release returns headers and padding as well as payload.

Keep metadata overhead distinct from slack. A largest-hole ratio describes a snapshot, not the future fraction of unusable storage.

First fit depends on list order. None of the names establishes universal performance; request sizes, lifetimes and representation matter.

Neighbouring virtual pages can map to nonadjacent frames. Fixed-size frame allocation does not remove heap fragmentation or guarantee large contiguous physical runs.

Frame number, permissions and state have distinct roles. Conceptual validity and residency need not be separate hardware bits.

Metadata depends on distinct occupied prefixes, not only mapped-page count. Base-page Sv39 walks three nine-bit indices.

Sv39 requires bits 63–39 to equal bit 38. Canonical does not mean mapped, resident or user-accessible.

A hit still checks permission. A miss can refill from an already resident mapping without a page fault or disk access.

It need not equal an OS PID. Recycling a finite tag requires retiring stale translations before the new identity uses it.

Entries times page size applies to one uniform page size. Conflicts, replacement and competing contexts can reduce effective coverage.

The scheduling mean usually weights each job equally. Completed-only statistics can hide unfinished or starving work.

This is not application end-to-end latency. A tiny first turn can improve the metric without producing useful output.

The batch exchange proof assumes common arrival, known demands and unweighted turnaround. Unknown lengths and interactive goals require different choices.

Shorter turns offer more frequent opportunities but increase handoff overhead. Delay bounds also need bounded competition and interference.

An allotment can span several turns and I/O-separated bursts. Blocking must not erase it in the anti-gaming policy.

A wait bound additionally needs bounded population and turn costs, limited interference and queue progress preserved across boosts.

An owner with t of T runnable tickets wins with probability t/T. Expected proportional service is not a finite-window quota.

A group subdivides its rights without inflating its outside share. Changing denominations alone does not change entitlement.

Select minimum pass and advance by its stride. Static bounds require stated initialisation; new arrivals need a live reference.

Larger weight advances virtual runtime more slowly for equal service. Historical CFS orders waiting entities by this progress.

Higher nice reduces weight. It is neither a fixed CPU percentage nor an absolute consumption cap.

Nonnegative lag establishes eligibility; earliest virtual deadline orders eligible requests. Lag is not time since wake-up.

Request-start virtual runtime plus requested service divided by normalised weight. Not a wall-clock completion guarantee.

Its record links memory, saved continuations, identity, scheduling state and open resources. Ready means eligible, not currently executing.

A trap need not switch processes. xv6 swtch transfers a kernel continuation using ra, sp and saved registers; the user trap frame is separate.

Success returns the child PID to the parent and zero to the child. Ordinary private memory starts equal but later writes are independent; inherited kernel resources may remain shared.

Success does not return to the old image. Descriptor and credential inheritance have explicit exceptions; common early failures leave the old image available.

It is not runnable. Orphanhood instead describes a child whose parent exited; an orphan may still be alive.

It holds the offset and file status flags. Fork copies descriptor-table entries without creating independent open-instance offsets; separate opens normally do.

It is not a shared open-file-description status flag. Equal-slot dup2 leaves descriptor flags unchanged, unlike duplication into a distinct slot.

posix_spawn can express redirection. It is often simpler than arbitrary post-fork setup when the launch fits its supported actions and attributes.

Blocking defers delivery; disposition chooses the response. Repeated instances of the same pending standard signal coalesce, so notification count is not event count.

Threads share memory and the descriptor table. Stack ownership does not protect its bytes from other threads; kernel-scheduled user threads are distinct from kernel workers.

User-space libraries can request its services but cannot replace hardware-enforced isolation merely by exposing functions.

RISC-V U, S and M distinguish authority. Memory access permissions complement instruction and control-register checks.

RISC-V hardware records control information in CSRs; it does not automatically save every general register or select a kernel stack.

It specifies entry, service number, arguments and return values. A source-language wrapper can translate the raw return convention.

Pending work may be delivered later. Local masking does not stop another core accessing shared memory.

Privilege, safe trap paths and independent control recovery work together. A timer provides a mechanism, not a fairness policy.

Distinguish this contract from a core implementation that overlaps or rearranges internal work.

Sequential advance depends on instruction length; branches and jumps select another address.

General-purpose registers hold values and addresses; the PC records control state. Register width does not establish installed memory capacity.

A w-bit address can name 2^w byte positions. Implemented, mapped and accessible addresses can be a smaller set.

It may contain saved registers, local data and stack arguments. Releasing it ends the lifetime without necessarily erasing its bytes.

Separately compiled functions must agree. The standard RISC-V integer ABI uses a downward-growing stack aligned to 16 bytes.

The callee may overwrite it. RISC-V ra is caller-saved, so a function making a nested call preserves its own live incoming return link.

This moves preservation work to functions that use the register, rather than forcing every caller to save everything.

Sections, symbols and relocations let compilation finish before final addresses are known.

Its type defines the reference point, addend, encoding, range and alignment requirements. Resolving a name alone is insufficient.

The line can contain several objects or part of one. Tags identify its memory block and valid bits establish whether it can serve a hit.

More ways can remove placement conflicts at fixed capacity, but add lookup hardware and replacement work.

Temporal locality reuses data; spatial locality uses neighbours fetched in the same line. Allocating a small object does not by itself ensure either.

Coherence does not make a multi-instruction update atomic or establish every ordering across distinct locations.

Its stable states encode permission and dirty-data responsibility. Real protocols require transient states and may extend the model.

M_static = N·S pays the library per binary; dynamic pays once but inherits search order, interposition and version coupling. A statically linked binary is also the only kind that survives an empty filesystem.

mmap wins on repeated random access and when kernel and user must share data structures; read() wins on one sequential pass and on code simplicity. msync is a flush, fsync remains the durability contract.

Buffered is the default because the kernel already runs the hit-rate policy; O_DIRECT is for applications that already cache (databases); sendfile/splice/MSG_ZEROCOPY are for movers, not users, of bytes — and only past a size threshold.

Paying per write buys latency isolation at throughput cost; batching amortises the flush but widens the loss window. The contract ends at media — a name needs its directory fsynced and the device cache sits below everything.

Hard links share content and lifetime — no dangling, but no directories and no crossing filesystems. Symlinks reach anywhere and can point at nothing. Deleting through a hard link is just unlink; the inode stays.

A bind mount makes the target part of the namespace — chroot and mount-namespace boundaries included — where a symlink depends on the new context resolving the path the same way.

The three-class check is compact and fast but cannot say “user X may read” — that requires an access-control list or capability scheme layered on top.

SSTF inherits SJF’s flaw — requests far from the head can wait forever. SCAN and C-LOOK serve in position order so every request is reached; C-LOOK skips the empty return sweep.

Page-level maps are fast but cost ~1 GiB of tables per TiB; block-level maps are tiny but force full merges. Hybrid and demand-based (DFTL) schemes pick the middle.

Pure polling wins only when the answer is usually ready now; pure interrupts lose at overload to livelock. Interrupt-then-poll-under-a-budget (NAPI) is the standard answer for high-rate devices.

DMA saves a whole CPU copy but costs descriptor setup, pinning and translation. Control traffic stays PIO; bulk data moves by descriptor ring.

Sharing removes 2βN per byte but hands the synchronisation protocol, robust-mutex repair and channel structure to the application. Small transfers rarely repay the fixed costs.

A queue’s priority and whole-message delivery beat a pipe when records matter; both lose to shared memory on bulk payload. The composite — message pointing at shared pages — is the bulk-data pattern.

Unix sockets skip protocol processing, admit pathname and abstract names, and uniquely carry SCM_RIGHTS descriptor passing. TCP loopback remains the answer when the protocol stack itself is what you need.

Every additional lock is an ordering obligation and a deadlock edge candidate. Split only where contention is measured; hand-over-hand traversal rarely pays on shallow structures.

Padding costs footprint and cache capacity; per-CPU copies need a merge step for reads. Confirm a shared-line bounce exists before paying either.

Condition variables express a predicate over shared state with explicit rechecking; semaphores express counts and event orderings. A counting semaphore used for arbitrary predicates loses the predicate; a CV used as a counter reimplements one.

Signal suffices for a uniform queue and a single consumable condition. Broadcast trades extra wakeups for safety when predicates differ; covering conditions are the disciplined middle ground.

Ordering and negating a condition are cheap but constrain design; avoidance needs declared maximums real code rarely knows; detection plus recovery pays runtime cost and needs rollback-able victims.

Short nonblocking kernel regions may require spinning. Long or uncertain holds favor a sleeping mutex where permitted; a bounded adaptive spin does not replace the safe sleep protocol.

Rare contention favors a simple lock. Tickets order admission; MCS changes polling locality. Neither FIFO nor locality guarantees that a descheduled owner will run.

PI removes intermediate-priority interference under suitable assumptions. Ceiling protocols add admission restrictions; neither configuration is a substitute for a full resource and timing analysis.

Tiny reads, frequent writers or little concurrency can favor a mutex. Reader/writer preference can starve the other class; specify queue policy and evaluate writer latency separately.

COW avoids copying discarded or unchanged pages. Eager copying can win when most pages will immediately diverge or predictable later latency matters.

Many tiny objects benefit from an allocator-owned region. Large independently released buffers or protected reservations can justify explicit mmap ranges.

Sparse unused regions benefit from deferred population. Known imminent use may justify eager work, without implying immunity from later reclaim.

Exact LRU has precise nesting guarantees; clock reduces observation cost but does not inherit those guarantees merely by approximating recency.

MIN provides an offline count yardstick. Sustained pressure and oversized working sets can require fewer concurrent jobs, not a more elaborate victim rule.

Strict accounting reduces late promise failures but does not guarantee all physical allocations. Application budgets and bounded concurrency remain necessary.

Segments use compact region descriptors but require contiguous variable-size physical storage. Pages scatter frames while adding table metadata and tail slack.

Flushes simplify correctness for infrequent switches. Tags need safe reuse and do not prevent capacity eviction or stale mappings after edits.

SJF minimises mean turnaround under its batch assumptions; RR offers bounded turns without a length oracle. First service is not useful completion.

Lottery offers expected shares, not finite wait guarantees. Stride needs progress counters and careful arrival placement.

Spawn file actions support redirection. Fork permits more general composition, but a multithreaded parent imposes strict child-side safety limits before exec.

Separate opens do not isolate underlying file contents. A duplicate is an alias, not a copy of data or an independent seek position.

One thread avoids coordination for short sequential work. Threads share heap and descriptors; processes can provide stronger fault and authority separation. Stack reservation is not resident memory.

Batching can reduce crossings but increase latency and memory use. Preserve partial-result and error semantics.

Compute depth from actual frame sizes and available stack. A loop or valid tail-call optimisation avoids accumulating frames for suitable computations.

The two-block trace fits in capacity but maps both blocks to one direct-mapped slot; two-way placement removes repeated conflicts.

Small tightly shared work can lose to one core. Batching writes reduces handoffs when delayed combination is acceptable.