Access Restriction

Author Fagin, Ronald ♦ Easton, Malcolm C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1976
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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 $\textit{MISS}$ be the expected working-set miss ratio in the independent reference model, with expected working set size $\textit{CAP}$ pages. Now form blocks, by combining the $\textit{B}$ pages with the highest probabilities of reference into one block, the $\textit{B}$ pages with the next-highest probabilities of reference into a second block, and so on. Let $\textit{MISS}*$ be the expected working-set miss ratio when all data are moved in blocks and when the expected working set size is again $\textit{CAP}$ pages, that is, $\textit{CAP}/\textit{B}$ = $\textit{C}$ blocks. It is proved that | $\textit{MISS}$ — $\textit{MISS}*$ | < $(2/\textit{C})$ + $(33/\textit{C}2).$ 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1976-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 23
Issue Number 1
Page Count 19
Starting Page 128
Ending Page 146

Open content in new tab

   Open content in new tab
Source: ACM Digital Library