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.

Keep page frames in a circular list with a reference bit and a scanning hand. Clear set reference bits while scanning; choose the first eligible page frame with a clear reference bit. This second chance approximates LRU replacement with cheaper tracking. When hardware reference flags are absent, revoking a mapping and handling its first later page fault can supply a software reference observation.

For the page-reference trace, number the three page frames 1–3 and initially point the hand at 1. Every access sets the referenced page frame's reference bit to 1. On a miss, scan from the hand: stop at an empty page frame or a resident one with reference bit 0; otherwise clear its reference bit and advance cyclically. Install the requested memory page with reference bit 1 and advance the hand to the next page frame. Hits leave the hand where it is. This fixes a particular variant; clean-victim preference is excluded.^[ref]

After the first three accesses, all reference bits are 1 and the hand is back at page frame 1. Access 4 clears all three reference bits, returns to page frame 1, evicts memory page 1, installs memory page 4, and leaves the hand at page frame 2 with reference bits $(1,0,0)$. This variant gives nine misses for three page frames and ten for four on the displayed sequence. Approximating LRU replacement therefore does not inherit the LRU stack property.

// Destination: computer-science.bigb

Evict the memory page loaded earliest among currently resident memory pages, without refreshing its position on access. It is simple but ignores temporal locality and can evict a frequently accessed memory page.

Implement this ranking with a FIFO queue of resident memory pages: append on loading, remove the oldest on eviction, and leave the queue unchanged on a hit. Belady anomaly shows why preserving arrival order can give more misses with more page frames. The comparison uses the same page-reference trace and empty initial resident sets in both runs.^[ref]

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.

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

On a miss with all page frames occupied, evict the resident memory page whose next access is farthest in the remaining page-reference trace. Treat no further access as farther than any finite next-use index; in the diagram, ties choose the lowest-numbered page frame. This is an offline, clairvoyant benchmark: a general operating system cannot know its future memory references. It minimizes miss count in the stated fixed-capacity demand paging model, rather than predicting the future from temporal locality.^[ref]

In the page-reference trace, seven misses with three page frames is therefore a lower bound for any policy using the same assumptions; with four page frames the corresponding minimum is six. The benchmark is useful for judging how much improvement is possible on a recorded workload. Its objective counts each miss equally. Different page writeback costs or unequal loading costs require a different objective; minimum misses alone does not prove minimum elapsed time.

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

Let $n$ be the number of accesses, $M$ the miss count and $D$ the number of dirty-victim page writebacks. Assume every requested memory page has a backing copy, every miss reads it, writes modify only part of its contents, transfers succeed and occur serially, and there is no background or final flushing. With common access cost $h$, additional load cost $r$ per miss, and additional outgoing write cost $w$ per dirty victim, an illustrative total service time isBookkeeping and other operating system costs are omitted. The two transfer directions are separate: a miss can require a read with no write, or both a victim write and a requested-page read. A retained dirty memory page contributes no outgoing write to this finite-page-reference trace count until evicted. Future flushing would need its own accounting boundary.

For three-page frame FIFO page replacement on the displayed page-reference trace, all reads give $(n,M,D)=(12,9,0)$. Change only access 1 to a partial write of memory page 1. Its initial miss still loads the old contents, the write marks it dirty, and eviction at access 4 adds exactly one page writeback. Later loads of memory page 1 are clean because the remaining accesses read. The result is $(12,9,1)$: identical residency and nine misses, but one extra outgoing write. With illustrative $h=100$ nanoseconds, $r=1$ millisecond and $w=2$ milliseconds, total service time changes from $9.0012$ to $11.0012$ milliseconds. These are model costs, not hardware measurements.

Preferring a clean victim can save an immediate page writeback, but evicting a soon-needed clean memory page can add later misses. This tradeoff is why a miss-minimizing optimal page replacement benchmark and a minimum-cost policy are different questions. Real page faults can also initialize a new memory page or perform copy-on-write without reading backing storage; those cases require different load costs.

// Destination: computer-science.bigb