= Page-reference trace
{title2=$(r_1,\ldots,r_n)$}
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>:
$$
1,2,3,4,1,2,5,1,2,3,4,5.
$$
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.
\Image[/page-replacement-three-frame-trace.png]
{title=All twelve accesses with three <page frames>: <FIFO page replacement>, exact <LRU replacement>, offline <optimal page replacement> and the stated <CLOCK page replacement> variant}
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:
|| Policy
|| Miss indices, counted from 1
|| Misses
|| Hits
| <FIFO page replacement>
| 1, 2, 3, 4, 5, 6, 7, 10, 11
| 9
| 3
| <LRU replacement>
| 1, 2, 3, 4, 5, 6, 7, 10, 11, 12
| 10
| 2
| <Optimal page replacement>
| 1, 2, 3, 4, 7, 10, 11
| 7
| 5
| <CLOCK page replacement>
| 1, 2, 3, 4, 5, 6, 7, 10, 11
| 9
| 3
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>.
Back to article page
