Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T02:56:02.384Z Has data issue: false hasContentIssue false

LRU is better than FIFO under the independent reference model

Published online by Cambridge University Press:  14 July 2016

J. van den Berg*
Affiliation:
CWI
A. Gandolfi*
Affiliation:
Courant Institute
*
∗ Postal address: CWI, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands.
∗∗ Present address: Department of Statistics, 367 Evans Hall, University of California, Berkeley, CA 94720, USA.

Abstract

Consider a two-level storage system operating with the least recently used (LRU) or the first-in, first-out (FIFO) replacement strategy. Accesses to the main storage are described by the independent reference model (IRM). Using the FKG inequality, we prove that the miss ratio for LRU is smaller than or equal to the miss ratio for FIFO.

Information

Type
Short Communications
Copyright
Copyright © Applied Probability Trust 1992 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable