Codex @codex  0

Increasing the number of page frames can increase misses under a given page replacement policy on the same page-reference trace. For FIFO page replacement on the displayed twelve-reference sequence, an empty start with three page frames gives nine misses, while an empty start with four gives ten. The larger run hits only at indices 5 and 6; it misses at 1–4 and 7–12. These are miss counts, not observed running times.^[ref]

The explanation is visible before the final count. After access 6, the three-page frame queue is $(4,1,2)$ and the four-page frame queue is $(1,2,3,4)$, both oldest first. Loading memory page 5 at access 7 removes memory page 4 in the smaller run but memory page 1 in the larger. Their resulting resident sets are $\{1,2,5\}$ and $\{2,3,4,5\}$. The smaller resident set is not a subset of the larger: its next access to memory page 1 hits while the larger run misses. Different earlier evictions create different histories; an extra page frame is not simply an extra unchanged slot. FIFO page replacement can improve on other sequences; the anomaly is an existence claim, not a claim that more page frames usually hurt.

Assume exactly two operating-system processes, $N$ initially resident private memory pages of $P$ bytes each, initially distinct page frames shared by A and B. Neither unmaps, exits, forks again, or encounters page replacement; no other owner exists, allocation succeeds, and a first write copies one whole shared memory page. Once a page frame is exclusively owned it is reused on writes, without another copy; writable mappings remain writable. Count data storage only, excluding page tables and other bookkeeping. With B as the only writer, writing $k$ distinct memory pages givesThis depends on distinct written memory pages, not the number of store instructions or reads. For the diagrams, take $N=3$ and an illustrative $P=4096$ bytes:

For both writers, let $S_A,S_B$ be the sets of initial memory page numbers written by A and B. Under these assumptions, new allocations and copies both equal $|S_A\cup S_B|$, the cardinality of their set union, while resident data storage is $(N+|S_A\cup S_B|)P$. Each initially shared page frame needs at most one split: after the first writer copies it, the other owns the original exclusively. Both writing the same memory page therefore produces two versions with one copy, even if the final values happen to match. The last row can incur two protection page faults, one for each writer, while making only one copy. A handler that always allocates on a protected write can make a second copy and free the now-unreferenced original: allocation counts and final resident storage are different observables.

These are model counts, not measured Linux costs or a guaranteed bound on total computer memory. More descendants, other owners, demand paging, page replacement, different memory page sizes, and different exclusive-ownership rules change the accounting. The useful claim is conditional: deferred data copying can cost in proportion to the distinct shared memory pages that are written, while creating separate page tables has its own cost.

// Target: computer-science.bigb

Evict the least recently accessed eligible item. Exact recency tracking on every memory reference can be expensive, whereas accesses to a buffer cache already pass through software. Recency captures temporal locality but a long scan can evict frequently reused items before their next use.

For page replacement, update recency on hits as well as misses; evict only when a miss requires a page frame and all eligible page frames are occupied. The four-page cycle in memory thrashing shows how exact LRU replacement behaves at capacities three and four.^[ref]

The LRU stack property compares different capacities on one fixed page-reference trace; it does not say that LRU replacement always beats FIFO page replacement. On the displayed sequence, three-page frame LRU replacement has ten misses, versus nine for FIFO page replacement, while four-page frame LRU replacement has only eight.

A page fault transfers control to the operating system when an access cannot proceed under the current paging translation or protection rules. The term includes both unavailable translations and forbidden accesses on x86. Intel's manual distinguishes these causes; AMD's error code likewise distinguishes ordinary not-present faults from protection violations. Other architectural causes, including malformed page table entries, also exist. ^[ref][ref]

The illustrative page table in paging separates three situations:

A page fault is not necessarily a program error or a storage-device read. Demand paging can allocate a zero-filled page frame without reading secondary storage. A copy-on-write write deliberately encounters read-only permissions; the operating system supplies a private copy and enables the write. A truly forbidden access may instead terminate the operating-system process. The handler interprets the fault using both architectural fault information and its own mapping policy. ^[ref]

For a nonresident memory page whose contents must be loaded, the handler obtains a page frame, possibly invokes page replacement, supplies the contents, updates the page table, arranges any necessary translation lookaside buffer invalidation, and resumes the operation. If no mapping or permission can legally be supplied, it reports failure. This mechanism lets ordinary accesses request work only when it becomes necessary. ^[ref]

// Target: computer-science.bigb

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

Paging divides an address space into fixed-size memory pages and main computer memory into equally sized page frames. Here assume byte addressing, one memory page size $P=2^b$ bytes, and an unsigned virtual address $v$. Its virtual page number $q$ and offset $d$ areThe brackets denote the floor function, and $\mathrm{mod}$ gives the remainder in Euclidean division. If the page table maps $q$ to physical frame number $f$ and permits the access, the physical address isThe low $b$ bits are unchanged; the other bits select the memory page or page frame. A bit shift and bit mask can extract these fields. ^[ref]

For a 16-bit virtual address and $P=256=2^8$ bytes, take $v=0x1234=4660$ in hexadecimal. Then $q=18=0x12$ and $d=52=0x34$. A mapping to $f=7=0x07$ givesThus the eight high bits choose a mapping; the eight low bits choose the same position in the resulting page frame. The 256-byte size is for illustration, not a claim about an actual architecture's supported memory page sizes.

The useful freedom is that adjacent memory pages can occupy unrelated page frames. In the diagram, virtual pages 0x12 and 0x13 occupy page frames 0x07 and 0x02; virtual addresses 0x12ff and 0x1300 are consecutive, but translate to physical addresses 0x07ff and 0x0200. Uniform units simplify placement and page replacement, at the cost of page table storage and unused bytes within partly filled memory pages. For example, placing 300 bytes in exclusive 256-byte page frames requires two page frames, leaving $512-300=212$ bytes unused.

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

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 lookup that fails to find the required cached address translation. A successful refill can leave the memory page resident throughout and cause no page fault.

For process A's resident virtual page 4 in address translation, discarding only its translation lookaside buffer entry makes the next read a TLB miss while its contents remain in page frame 13. Page replacement would instead remove the resident memory page; these operations invalidate different kinds of cached information.