NDLI: An approximate analysis of the LRU and FIFO buffer replacement schemes

Content Provider	ACM Digital Library
Author	Towsley, Don Dan, Asit
Abstract	In this paper, we develop approximate analytical models for predicting the buffer hit probability under the Least Recently Used (LRU) and First In First Out (FIFO) buffer replacement policies under the independent reference model. In the case of the analysis of the LRU policy, the computational complexity for estimating the buffer hit probability is O(KB) where B is the size of the buffer and K denotes the number of items having distinct access probabilities. In the case of the FIFO policy, the solution algorithm is iterative and the computational complexity of each iteration is O(K). Results from these models are compared to exact results for models originally developed by King [KING71] for small values of the buffer size, B, and the total number of items sharing the buffer, D. Results are also compared with results from a simulation for large values of B and D. In most cases, the error is extremely small (less than 0.1%) for both LRU and FIFO, and a maximum error of 3% is observed for very small buffer size (less than 5) when the access probabilities are extremely skewed. To demonstrate the usefulness of the model, we consider two applications. In our first application, we compare the LRU and FIFO policies to an optimal static buffer allocation policy for a database consisting of two classes of data items. We observe that the performance of LRU is close to that of the optimal allocation. As the optimal allocation requires knowledge of the access probabilities, the LRU policy is preferred when this information is unavailable. We also observe that the LRU policy always performs better than the FIFO policy in our experiments. In our second application, we show that if multiple independent reference streams on mutually disjoint sets of data compete for the same buffer, it is better to partition the buffer using an optimal allocation policy than to share a common buffer.
Starting Page	143
Ending Page	152
Page Count	10
File Format	PDF
ISSN	01635999
DOI	10.1145/98460.98525
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	18
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Segmented FIFO page replacement

An approximate analysis of the lru and fifo buffer replacement schemes (1990).

An approximate analysis of the LRU and FIFO buffer replacement schemes

Analysis of the generalized clock buffer replacement scheme for database transaction processing

The performance impact of kernel prefetching on buffer cache replacement algorithms

Queueing analysis of finite buffer token networks

On adaptive replacement based on LRU with working area restriction algorithm

TS-CLOCK:temporal and spatial locality aware buffer replacement algorithm for NAND flash storages

Solution properties and convergence of an approximate mean value analysis algorithm

An approximate analysis of the LRU and FIFO buffer replacement schemes

Similar Documents

Segmented FIFO page replacement

An approximate analysis of the lru and fifo buffer replacement schemes (1990).

An approximate analysis of the LRU and FIFO buffer replacement schemes

Analysis of the generalized clock buffer replacement scheme for database transaction processing

The performance impact of kernel prefetching on buffer cache replacement algorithms

Queueing analysis of finite buffer token networks

On adaptive replacement based on LRU with working area restriction algorithm

TS-CLOCK:temporal and spatial locality aware buffer replacement algorithm for NAND flash storages

Solution properties and convergence of an approximate mean value analysis algorithm

An approximate analysis of the LRU and FIFO buffer replacement schemes