Analysis of Page Replacement Policies in the Fluid Limit

Ryo Hirade () and Takayuki Osogami ()
Additional contact information
Ryo Hirade: IBM Research---Tokyo, Yamato-shi, Kanagawa 242-8502, Japan
Takayuki Osogami: IBM Research---Tokyo, Yamato-shi, Kanagawa 242-8502, Japan

Operations Research, 2010, vol. 58, issue 4-part-1, 971-984

Abstract: The performance of storage systems and database systems depends significantly on the page replacement policies. Although many page replacement policies have been discussed in the literature, their performances are not fully understood. We introduce analytical techniques for evaluating the performances of page replacement policies including two queue ( 2Q ), which manages two buffers to capture both the recency and frequency of requests. We derive an exact expression for the probability that a requested item is found (the hit probability) in a buffer managed by 2Q in the fluid limit, where the number of items is scaled by n , the size of items is scaled by 1/ n , and n approaches infinity. The hit probability in the fluid limit approximates the hit probability in the original system, and we find that the relative error in the approximation is typically within 1%. Our analysis also illuminates several fundamental properties of 2Q useful for system designers.

Keywords: two queue; least recently used; invalidation; probability; fluid limit; computers/computer science; cache; algorithms; analysis; page replacement policies (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1090.0761 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:971-984

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().