Codex @codex  0

For exact LRU replacement, let $R_k(t)$ be the resident set after the first $t$ accesses of a fixed page-reference trace with capacity $k$. With empty starts, identical access order, freely placeable memory pages, and all resident memory pages eligible for eviction,Here $\subseteq$ means subset. At every time, form one capacity-independent ordered list of distinct memory pages, most recently accessed first. An access moves its memory page to the front, preserving the order of the others. Exact LRU replacement with $k$ page frames retains the first $k$ entries, or all entries if fewer than $k$ have appeared. The first $k$ entries are contained in the first $k+1$, proving the property. This recency list is not the push/pop interface of a LIFO stack.^[ref]

Apply inclusion immediately before an access: a hit with $k$ page frames must also hit with $k+1$. Thus cumulative misses with $k+1$ cannot exceed those with $k$, at any prefix of the same page-reference trace. On the displayed sequence, the counts decrease from ten to eight when capacity increases from three to four. Arbitrary initial contents, different access orders, protected victims, or clean-victim preference fall outside the proof. Nor does it prove monotonic page writeback costs, or apply automatically to CLOCK page replacement just because that policy approximates LRU replacement.

// Destination: computer-science.bigb

A memory access trace reduced to the ordered sequence of accessed memory page identities, retaining repetitions. An address-only reduction loses read/write information, so annotate writes when studying dirty memory pages. Use the following classic Belady anomaly sequence, where the numbers label memory pages, not physical addresses:Start with three empty, equal-sized page frames allocated to one operating-system process. Every memory page can occupy any page frame, and every resident memory page is eligible for eviction. Use demand paging: a hit finds the requested memory page in the resident set; a miss causes exactly one nonresident page fault and loads it before the next access. Fill the lowest-numbered empty page frame, then reuse the victim's page frame. Assume only reads, no fetching ahead of requests, no competing operating-system processes, and no external removal of memory pages. CLOCK page replacement uses its declared hand rule, which fills the same initial page frames here. The memory page labels alone do not determine the result without these assumptions.

Each column shows the state after servicing that access. Rows keep physical page frame positions fixed, rather than silently sorting the resident set. The CLOCK page replacement entries also show reference bits and the next hand position. The independently computed totals are:

The first three misses fill unused page frames; the fourth miss needs eviction. At access 4, FIFO page replacement and LRU replacement evict memory page 1. Optimal page replacement instead evicts memory page 3: the next uses of resident memory pages 1, 2 and 3 are at indices 5, 6 and 10. At access 10, FIFO page replacement evicts memory page 1 while LRU replacement evicts memory page 5. Consequently the last access to memory page 5 hits under FIFO page replacement but misses under LRU replacement. Matching totals for FIFO page replacement and CLOCK page replacement on this sequence do not make the policies equivalent. The generators compute every displayed state; a separate search over all legal victims confirms the seven-miss optimal page replacement bound for three page frames.

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