Relative interval analysis of paging algorithms on access graphs

DOI10.1007/978-3-642-40104-6_17MaRDI QIDQ2842157zbMATH OpenOpenAlexFDO

Authors Sushmita Gupta, Kim S. Larsen, Joan Boyar

Publication date 12 August 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.0669

Mathematics Subject Classification ID

Theory of operating systems (68N25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the expected results are obtained. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from [Dorrigiv, Lopez-Ortiz, Munro, 2009], obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis.

Recommendations

• Relative interval analysis of paging algorithms on access graphs
• Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
• scientific article; zbMATH DE number 1303543
• Competitive paging with locality of reference
• LRU is better than FIFO

Cited in

(7)

• Quantifying competitiveness in paging with locality of reference
• Relative interval analysis of paging algorithms on access graphs
• Online Bin Covering: Expectations vs. Guarantees
• Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
• Online bin covering: expectations vs. guarantees
• Quantifying competitiveness in paging with locality of reference
• scientific article; zbMATH DE number 1755579 (Why is no real title available?)

This page was built for publication: Relative interval analysis of paging algorithms on access graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842157)