×

Engineering efficient paging algorithms. (English) Zbl 1347.68373

MSC:

68W27 Online algorithms; streaming algorithms
68N25 Theory of operating systems
68W40 Analysis of algorithms

Software:

OnlineMin
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dimitris Achlioptas, Marek Chrobak, and John Noga. 2000. Competitive analysis of randomized paging algorithms. Theor. Comput. Sci. 234, 1-2 (2000), 203-218. · Zbl 0944.68194
[2] Wolfgang W. Bein, Lawrence L. Larmore, John Noga, and Rüdiger Reischuk. 2011. Knowledge state algorithms. Algorithmica 60, 3 (2011), 653-678. · Zbl 1223.68124
[3] Laszlo A. Belady. 1966. A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5, 2 (1966), 78-101.
[4] Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. 1995. Competitive paging with locality of reference. J. Comput. Syst. Sci. 50, 2 (1995), 244-258. · Zbl 0827.68027
[5] Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. 2007. The relative worst-order ratio applied to paging. J. Comput. Syst. Sci. 73, 5 (2007), 818-843. · Zbl 1115.68159
[6] Gerth Stølting Brodal, Gabriel Moruz, and Andrei Negoescu. 2013. OnlineMin: A fast strongly competitive randomized paging algorithm. In Theory of Computing Systems, Special Issue of the 9th Workshop on Approximation and Online Algorithms. DOI: http://dx.doi.org/10.1007/s00224-012-9427-y · Zbl 1242.68375
[7] Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. 1991. Competitive paging algorithms. J. Algorithms 12, 4 (1991), 685-699. · Zbl 0753.68018
[8] Amos Fiat and Ziv Rosen. 1997. Experimental studies of access graph based heuristics: Beating the LRU standard? In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. 63-72.
[9] Scott F. Kaplan, Yannis Smaragdakis, and Paul R. Wilson. 2003. Flexible reference trace reduction for VM simulations. ACM Trans. Model. Computer Simul. 13, 1 (2003), 1-38. · Zbl 1390.68259
[10] Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic Sleator. 1988. Competitive snoopy caching. Algorithmica 3 (1988), 77-119. · Zbl 0645.68034
[11] Elias Koutsoupias and Christos H. Papadimitriou. 2000. Beyond competitive analysis. SIAM J. Comput. 30, 1 (2000), 300-317. · Zbl 0959.68131
[12] Lyle A. McGeoch and Daniel Dominic Sleator. 1991. A strongly competitive randomized paging algorithm. Algorithmica 6, 6 (1991), 816-825. · Zbl 0731.68040
[13] Gabriel Moruz and Andrei Negoescu. 2012. Outperforming LRU via competitive analysis on parametrized inputs for paging. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. 1669-1680. · Zbl 1422.68031
[14] Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28, 2 (1985), 202-208.
[15] Andrew S. Tanenbaum. 2008. Modern Operating Systems (3rd ed.). Pearson Education. · Zbl 0801.68001
[16] Neal E. Young. 1994. The k-server dual and loose competitiveness for paging. Algorithmica 11, 6 (1994), 525-541.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.