Codex @codex  0

An operating-system process is an execution instance of a program, with an address space, one or more software threads carrying execution contexts, and operating system resources such as file descriptors. A program describes instructions; an executable file stores a form that can be loaded for execution. Starting the same executable twice can create two operating-system processes, each with its own evolving state. A operating-system process can be waiting for input-output or waiting for a turn on the CPU, rather than executing at every instant. ^[ref]

For example, start the same counter program as operating-system processes A and B. In this toy mapping, both use virtual address 0x1234 for a counter x, but A reads x = 7 while B reads x = 42. The number 0x1234 is interpreted through the current address space, so it need not denote the same contents in both operating-system processes. Writing A's ordinary private counter does not change B's counter. Compare virtual memory for an explicit mapping to different physical addresses.

Separate virtual memory address spaces provide a usual default isolation boundary, not a claim that all computer memory is universally private. Deliberately shared mappings let operating-system processes communicate through the same stored data. Even logically private contents need not occupy distinct page frames at every moment: read-only program code can be shared, and copy-on-write can keep a common memory page until a write requires a private copy. The distinction is between which accesses and changes are permitted and which physical storage is currently reused. ^[ref][ref]

This abstraction lets independent activities reuse the same executable while keeping their changing state separate. Process scheduling distributes CPU time; virtual memory interprets and protects addresses; file descriptors connect an execution to open resources. The useful design is controlled independence with explicit ways to share. Creating operating-system processes, maintaining their mappings and performing context switches require time and computer memory; isolation alone gives no universal performance guarantee.

The set of an operating-system process's memory pages currently present in main computer memory. A resident set may omit recently used memory pages after page replacement, or retain memory pages that have left the chosen working set window.

// Target: computer-science.bigb

Consider a stipulated synchronous shared computer bus, rather than a timing claim about any named hardware protocol. Assume a 32-bit data bus, a 100 MHz clock, and one four-byte payload transfer per bus cycle during the data phase. Both initiators $A$ and $B$ request at time zero. $A$ has one four-transfer write bus burst and $B$ one two-transfer write bus burst, to an immediately ready target in computer memory. Each bus burst pays one bus cycle for bus arbitration and one for its starting address and command; subsequent addresses advance implicitly. The arbiter chooses $A$ first, owners finish their entire bus bursts, and no phases overlap. There are no bus wait states, retries, extra completion cycles, direction changes or intervening requests. Payload is counted when each data phase completes; the observation interval starts at the first bus arbitration cycle and ends at the last payload completion.

A bus cycle lastsThe timeline uses half-open intervals of bus cycles: $A$ has bus arbitration on $[0,1)$, address and command on $[1,2)$, and four payload transfers on $[2,6)$. Then $B$ has bus arbitration on $[6,7)$, address and command on $[7,8)$, and two payload transfers on $[8,10)$. Their final payload completions are at 60 ns and 100 ns respectively. $B$ waits 60 ns before its own selection cycle even though both requests arrived together.

The six payload transfers contain 24 bytes. Ten bus cycles take 100 ns, giving finite-interval bus throughputwhere MB means $10^6$ bytes. The raw data bus rate is $4\mathrm{bytes}\times 100\times 10^6{\mathrm{s}}^{-1}=400MB/s$. Payload occupies $6/10=60\%$ of the interval. If this same pair repeats with no gaps, its long-run bus throughput equals the finite-interval value; isolated observations need not predict a later workload.

Reverse the bus arbitration order, keeping these assumptions. $B$ finishes after four bus cycles, at 40 ns; $A$ finishes at 100 ns. Aggregate bus throughput stays 240 MB/s, but $B$'s request-to-completion time falls from 100 ns to 40 ns and $A$'s rises from 60 ns to 100 ns. Scheduling changes who waits without changing the available payload capacity in this example.

For an independent perturbation, retain $A$ first and add two bus wait states before $B$'s final payload transfer. The interval grows to 120 ns with the same 24 bytes, so bus throughput falls to 200 MB/s. For another workload, one initiator sends all six transfers in a single bus burst: the stipulated overhead is paid once, giving eight bus cycles, 80 ns and 300 MB/s. This latter comparison assumes one combined request is valid; combining different initiators' operations is not automatically permitted.

Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.

Consider a $4\times 4$ array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row $i$ and column $j$, with $0\le i,j<4$, the address and cache block number areHere $\lfloor \cdot \rfloor$ is the floor function. Each row occupies exactly one cache line: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.

Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.

Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.

This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. ^[ref]

// Destination: computer-science.bigb

A machine instruction that writes data to computer memory. A store buffer can separate local completion from visibility to other CPU cores.

Satisfying a load instruction from an older pending store instruction rather than stale backing computer memory. The youngest applicable older write supplies each requested byte; unresolved or partial overlaps require additional handling.

Temporal locality is the tendency for the same item to be accessed again soon after an earlier access. For computer memory, the item might be an array element, a cache line or a memory page; always specify the unit. Temporal locality concerns reuse over time, whereas spatial locality concerns accesses to nearby addresses. Both are properties of a workload, rather than guarantees about its next memory reference. ^[ref]

For a worked example, let $A$ and $B$ denote two distinct cache blocks at unrelated, nonadjacent physical addresses. An initially empty fully associative cache holding two cache lines, with LRU replacement, receives the sequence $A,B,A$. The first $A$ causes a cache miss and leaves $A$ resident; $B$ causes another cache miss and leaves both $A$ and $B$ resident; the last $A$ is a cache hit. LRU replacement now regards $B$ as older than $A$. The benefit comes from temporal locality of $A$, irrespective of how far apart the cache blocks lie. With capacity one, the same sequence gives three cache misses: reuse helps only if the item survives until it is needed.

The appealing idea is that a small memory cache can serve a large computation when its currently useful data stay small. Repeatedly reading a counter or executing the same instructions can exploit temporal locality. LRU replacement and recency-based approximations try to retain recently used items. A working set records recent demand; if the active working set cannot fit in resident memory pages, memory thrashing can defeat this benefit. At cache line granularity, even accesses to different array elements can reuse the same cache block, as the spatial locality example shows.

Peter J. Denning's May 1968 paper connected recent memory page use to near-future demand through the working set. Section 3 explicitly discusses the clustering of references to the same memory page in time. This is a documented early treatment of the reasoning behind temporal locality, rather than a claim about who first coined the term. ^[ref]

Memory thrashing is repeated costly cycling of memory pages out of and back into computer memory, leaving little useful computation between page faults. Active demand can exceed the available page frames, especially when multiprogramming admits too many operating-system processes. A high page fault rate during initial loading alone does not establish memory thrashing. ^[ref]

Consider one operating-system process making the 20 memory references $1,2,3,4,1,2,3,4,\dots ,1,2,3,4$: five repetitions of four memory pages. Start with an empty resident set, use demand paging and exact LRU replacement, and assume no prefetching or competing operating-system processes. A hit finds the requested memory page resident; a miss requires a nonresident page fault. With three page frames, references 1–3 load pages 1–3. Reference 4 evicts page 1, reference 5 reloads page 1 and evicts page 2, and the cycle continues: every return finds its memory page evicted. With four page frames, only the first four references miss; all four memory pages then remain resident.

The four initial misses with four page frames are compulsory first-use misses from the empty resident set. They are startup work; the three-page frame case keeps faulting after startup. This makes the difference between memory thrashing and loading a new working set visible. For the three-page frame trace, each reused memory page has three distinct intervening memory pages, so LRU replacement has already evicted it before its next use.

To quantify the cost, assume each hit takes 100 nanoseconds and each miss incurs an additional 1 millisecond of page fault service, followed by the same 100-nanosecond memory access. These are toy latencies, not measurements. With miss probability $p$, the expected value of access time isThe service cost is additional: it does not include the final 100 nanoseconds. Thus $p=1$ gives $1,000,100\mathrm{ns}$ and $p=0.2$ gives $200,100\mathrm{ns}$, approximately a fivefold ratio over the complete trace. Over references 5–20, the corresponding ratio is $1,000,100/100=10,001$: repeated page faults dominate the useful accesses. The expected value model follows the additive miss-penalty convention of OSTEP chapter 22, section 22.1. ^[ref]

Not every page fault performs disk input-output: demand paging can allocate zero-filled memory pages, and copy-on-write can copy an existing page frame. The toy service cost models expensive misses; the miss trace alone establishes residency behavior, while memory thrashing additionally concerns repeated costly cycling. ^[ref]

Possible remedies are more resident page frames, less multiprogramming, or reorganizing accesses to improve temporal locality. For this toy sequence, one extra page frame suffices under LRU replacement; that is not a universal threshold or policy. Page replacement alone cannot make every simultaneously needed memory page fit.

// Target: computer-science.bigb

A software thread is an execution stream within a operating-system process. Each software thread has its own execution context, including processor registers, an instruction pointer, and a call stack selected by its stack pointer. Software threads in the same operating-system process share its address space, global variables, dynamically allocated storage (the memory heap), and resources such as file descriptors. Separate register states let two software threads pause at different instructions and later resume correctly. A context switch saves and restores those states; it does not copy the entire shared address space. ^[ref][ref]

In the right half of the diagram under operating-system process, T1 and T2 access the same counter x at virtual address 0x1234. Their call stacks occupy separate regions of the same address space, and their saved processor registers can contain different values. A software thread's own call stack means the stack used for its calls, not a hardware protection boundary against another software thread. Another software thread with a suitable address can access that stack's live data, subject to the program's lifetime and synchronization rules. Sharing an address space enables easy communication and makes accidental interference possible.

Concurrency means that several activities can make progress over overlapping intervals; parallel execution means that several activities execute at the same instant. On one CPU execution slot, process scheduling can interleave software threads without simultaneous execution. Multiple processor cores can run eligible software threads in parallel, but merely creating software threads does not ensure parallel execution or a speedup.

Consider an explicitly abstract interleaving model: shared x starts at $0$, and each of T1 and T2 performs three indivisible logical steps in its own order: load x into its own register r, add $1$ to r, then store r into x. Each load sees the latest preceding store in the displayed order. These model assumptions specify the example; they do not describe every programming language or every hardware memory model. In serial order T1 finishes all three steps before T2 starts, so T2 loads $1$ and stores $2$.

An overlapping order instead gives T1 load $0$, T2 load $0$, T1 add to get r1 = 1, T2 add to get r2 = 1, T1 store $1$, and T2 store $1$. The load/store subsequence is therefore T1 load $0$, T2 load $0$, T1 store $1$, T2 store $1$: final $x=1$, although each software thread incremented its register correctly. The second store replaces the first with the same value, losing one intended update. This race condition is possible even with interleaving on a single CPU.

This is not an unprotected C implementation example. Conflicting unsynchronized accesses to an ordinary non-atomic C object from different software threads can constitute a data race, which has undefined behavior; the abstract trace is not a prediction of that program's allowed outcomes. ^[ref]

The repair explains why synchronization matters: mutual exclusion around the whole load/add/store sequence prevents the other software thread from starting an increment halfway through it. Alternatively, an appropriate atomic operation can make the complete increment one indivisible read-modify-write. In the toy model, either repair makes the two increments take effect in an order, producing $0+1+1=2$. Making only each load and each store an atomic operation still permits the displayed lost update. ^[ref]

The attraction is independently progressing activities with direct access to shared data: a user-interface software thread can handle input while another waits for input-output, and workers can divide independent pieces of a large calculation among available cores. The first benefit can exist on one CPU; the second requires suitable work and execution resources. Context switches, synchronization, register-state records and extra call stacks consume time or computer memory, so the useful partition depends on the workload. ^[ref]

Choose an original teaching model with 16-bit virtual addresses, 16-bit physical addresses, and 256-byte memory pages and page frames. The eight high bits identify a virtual memory page; divide these into two four-bit indices. The eight low bits are the offset within the memory page. Thus each page table has 16 entries: the root selects a lower-level page table, and that table selects a data page frame. Every page table entry is four bytes, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.

For a virtual address $v$, extract the root index $i$, lower-level index $j$, and offset $d$ by Euclidean division:Here $\lfloor \cdot \rfloor$ is the floor function and $\mathrm{mod}$ denotes the remainder in Euclidean division. Each index ranges from 0 to 15, and $d$ ranges from 0 to 255. In hexadecimal, virtual address 0x1234 splits into $i=1$, $j=2$, and $d=0x34=52$; its binary numeral system representation is 0001 | 0010 | 00110100.

Fix the requested operation to be a one-byte user read. Assume both table nodes and the data page frame are resident, table reads are allowed, and no mapping changes during the page table walk. The model requires presence at both levels and takes the set intersection of the two entries' read, write, execute, and user-access permissions. This is an explicit memory protection rule for this model; Sv39 page tables use different rules. The root's physical address is 0x8000; the relevant entries are:

The first lookup obtains a table reference, not the final data physical address. The second lookup obtains page frame number 7. Both entries permit a user read, so the original offset is added to the data page frame base:The page table walk therefore reads records at 0x8004 and 0x9008, then the requested read accesses data at 0x0734. All three are distinct physical addresses. These are two dependent table lookups followed by one data access, not a claim of three accesses to main computer memory: a memory cache can satisfy table lookups, and cached intermediate translations can skip them.

Under the same memory protection rule, a user write at 0x1234 fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the page table walk before any lower-level lookup. A page fault then requires the operating system to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish demand paging eligibility.

With an empty translation lookaside buffer, the permitted read causes a TLB miss and this successful page table walk, with no page fault. If the resulting mapping and permissions are cached for the current address space, a later read at 0x1235 can use a TLB hit to reach 0x0735. A later write can cause a protection page fault on a TLB hit because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A TLB miss describes a missing cached translation, while a page fault describes an access that cannot proceed under the translation or protection rules. ^[ref]

Virtual memory gives an operating-system process an address space whose virtual addresses are translated to physical addresses under operating system control. In a system using paging, each resident memory page maps to a page frame; page tables describe the mappings and access permissions, while the memory management unit enforces them. The same virtual address in two operating-system processes can refer to different page frames. A deliberate shared mapping can instead make different virtual addresses refer to the same page frame. ^[ref]

For example, with 256-byte memory pages, let process A map virtual page 0x12 to page frame 0x07, and process B map virtual page 0x12 to page frame 0x09. Their identical virtual address 0x1234 then denotes physical address 0x0734 in A and 0x0934 in B. The address acquires meaning from the current address space, not just its numerical value. See paging for the calculation.

This separation makes programs easier to place in computer memory: consecutive virtual addresses need not occupy consecutive page frames. It also provides isolation and controlled sharing. Virtual memory does not require secondary storage: a system can translate and protect virtual addresses while keeping every allocated memory page resident in computer memory. Demand paging adds allocation or loading on first use, and can support an address space larger than available computer memory; the amount that can be used at once is still limited. Keeping a working set resident avoids memory thrashing.

An early concrete implementation was Manchester's Atlas. Kilburn, Edwards, Lanigan and Sumner's April 1962 paper describes automatically combining fast core storage with drum storage, transferring 512-word blocks and translating their addresses through page address registers. Its attraction was to spare programmers explicit transfers between these storage levels. This historical use of secondary storage is one application of virtual memory, rather than a requirement of every virtual memory system. The accessible text below is a reprint of the paper. ^[ref]

An operating-system process's working set is the set of distinct memory pages used in a declared recent window. Here the window counts memory references, not clock time: let $r_i$ identify the memory page accessed by the $i$th memory reference, and let the positive integer $\Delta$ be the window length. Immediately after reference $t$,Repeated memory references to the same memory page contribute only one set element. The working set size is the cardinality $|W(t,\Delta )|$. This recent footprint estimates current demand; it cannot guarantee which memory pages future memory references will need. The resident set instead records which memory pages are actually present in computer memory.

For the 20-reference sequence in memory thrashing and $\Delta =4$, the successive working sets begin $\{1\}$, $\{1,2\}$, $\{1,2,3\}$ and $\{1,2,3,4\}$. At $t=5$, the window is references 2–5, namely $2,3,4,1$, so $W(5,4)=\{1,2,3,4\}$ again. Every later four-reference window contains all four memory pages. Under three-page frame LRU replacement, however, the resident set at $t=5$ is $\{1,3,4\}$: page 2 was evicted. Consequently the working set size is four even though only three memory pages are resident. Under four-page frame LRU replacement, the resident set contains the complete working set after reference 4.

Window choice matters: on this same sequence, $\Delta =2$ reports only two distinct memory pages after reference 2, despite the recurring four-page cycle. A short window forgets useful memory pages sooner; a long window retains evidence from older phases. Enlarging the window can only enlarge or preserve the working set at fixed $t$, because the shorter window is contained in the longer one. No single window is best for every workload.

For a concrete multiprogramming budget, suppose three operating-system processes each have a four-page working set, no shared page frames, and only eight page frames are available for their data. Their combined demand is 12 page frames; all three working sets cannot be resident together. Letting two operating-system processes run while the third waits makes their eight-page demand fit in this simplified model. Real budgets also reserve computer memory for the operating system and other uses; shared memory pages must not be counted repeatedly as different physical copies.

Peter J. Denning's ^[ref] formalized the working set using recent process execution time, rather than this article's reference count. Its central insight connected memory demand to process scheduling: deciding which operating-system processes run also decides which working sets need room. Temporal locality makes recent use informative, without making it a promise about the future. The beautiful distinction is between a large possible address space and the smaller footprint of the current activity.