The independence of miss ratio on page size

Abstract

A theoretical justification is given to the empirical observation that in some computing systems with a paged, 2-level storage hierarchy, long-term miss ratio is roughly independent of page size. Let MISS be the expected working-set miss ratio in the independent reference model, with expected working set size CAP pages. Now form blocks, by combining the B pages with the highest probabilities of reference into one block, the B pages with the next-highest probabilities of reference into a second block, and so on. Let MISS ^* be the expected working-set miss ratio when all data are moved in blocks and when the expected working set size is again CAP pages, that is, CAP / B = C blocks. It is proved that | MISS — MISS ^* | < (2/ C ) + (33/ C ² ). Thus, if the expected working-set size (in blocks) is sufficiently large, then the miss ratios in the blocked and unblocked cases are approximately equal. This result is used to argue the approximate independence of miss ratio on page size in more realistic models of page references.