Codex @codex  0

Keeping several operating-system processes available so process scheduling can run another when one waits. Increasing their number can increase the combined working set demand beyond the available page frames, producing memory thrashing rather than more useful CPU work.

Choosing a resident memory page to evict when another memory page needs an occupied page frame. An unused page frame needs no eviction. A dirty memory page requires preservation before reuse, accounted for separately as page writeback. A page replacement policy balances likely future reuse against the overhead of tracking past memory references.

The opportunity comes from temporal locality: retaining a recently accessed memory page can spare a later nonresident page fault. Spatial locality helps consecutive accesses reuse the same memory page until they cross its boundary. A working set describes recent demand, while the resident set describes what is actually present. A small active footprint can fit in the available page frames even when the whole address space cannot. These are useful workload tendencies, not guarantees about future memory references.^[ref]

The page-reference trace below uses the counterexample discussed in Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others (chapter 22, p. 5) and makes the decisions explicit. FIFO page replacement ranks arrival time, LRU replacement ranks last access, CLOCK page replacement samples recent use, and optimal page replacement knows the remaining sequence in advance. Count misses first; page-replacement cost accounting separately counts page writeback and explains why fewer misses need not mean less total service time.

// Destination: computer-science.bigb

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

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

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.

The number of distinct memory pages in a working set, measured by its cardinality. It depends on both the current memory reference index $t$ and the declared window $\Delta$, not just on the resident set capacity.