Page replacement and working sets

Define a working set as the distinct pages referenced within a stated recent interval. That definition needs both a page granularity and a window. A short window can describe a hot inner loop; a longer one may include the model weights and input blocks needed across several requests. Neither number is universally correct. A service alternating between two phases can have small per-phase working sets but a much larger union. Record the phase and interval before comparing estimates or promising that a machine has enough memory.

Resident-set size counts pages currently resident under a metric's rules, including pages that may not have been used recently. It can therefore exceed a current working-set estimate. It can also be smaller than the pages the workload will shortly need, causing repeated loading or reconstruction. Sharing complicates host totals further. When planning placement, distinguish an application's useful hot data, reclaimable cold cache, kernel overhead, pinned memory, and room for bursts. A single resident-size snapshot is not a complete future demand forecast.

For a fully associative least-recently-used teaching cache, retain the most recently referenced distinct pages up to capacity. A hit moves its page to the most-recent position. A miss inserts it and evicts the least-recent page when full. Count cold misses separately from misses caused by insufficient capacity when the distinction helps. This small model is useful because you can verify each decision by hand. Real operating-system reclaim has multiple page classes, writeback costs, protection constraints, and sampled access information rather than an exact global reference order.

Reuse distance counts distinct intervening pages between two references to the same page. In the ideal fully associative LRU model, a repeated reference hits when that distance is below capacity in pages. Consider a sequential scan repeatedly cycling through one more page than the cache holds: the newest page displaces a page needed again soon. Repeated refaults can consume capacity without useful progress, a form of thrashing. Blocking work into smaller reusable regions may help, but an algorithm with no reuse might instead benefit from avoiding pollution of valuable hot data.

Linux reclaim policies evolve and may use mechanisms such as multi-generation aging rather than a literal textbook LRU stack. Read the deployed kernel's counters and interfaces before interpreting a named statistic. A rise in refault activity alongside memory stalls and lower useful throughput supports a locality-pressure hypothesis; a fault count by itself does not establish it. Compare controlled changes such as a smaller batch or fewer workers while preserving the same useful output. That helps distinguish insufficient useful capacity from a slow storage device or unrelated CPU contention.

The probability lab supplies a contrast to a correlated reference trace. Set success probability to 0.75 and twenty trials, predicting fifteen hits in an independent constant-probability model. Keep those controls fixed and imagine two traces: five misses evenly distributed versus five misses clustered in a burst. The binomial distribution does not encode either order, so it cannot reproduce their latency or LRU outcome. Use that limitation to explain why average hit probability alone is an inadequate working-set measurement, even though its expected count is simple.