On paging with locality of reference

ABSTRACT

Motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and in developing alternative models for studying online paging. The goal is to devise models in which theoretical results capture phenomena observed in practice.In this paper we propose a new, simple model for studying paging with locality of reference. The model is closely related to Denning's working set concept and directly reflects the amount of locality that request sequences exhibit. We demonstrate that our model is reasonable from a practical point of view.We use the page fault rate to evaluate the quality of paging algorithms, which is the performance measure used in practice. We develop tight or nearly tight bounds on the fault rates achieved by popular paging algorithms such as LRU, FIFO, deterministic Marking strategies and LFD. It shows that LRU is an optimal online algorithm, whereas FIFO and Marking strategies are not optimal in general. We present an experimental study comparing the page fault rates proven in our analyses to the page fault rates observed in practice. This is the first such study for an alternative/refined paging model.

REFERENCES

• 1: L.A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78--101, 1966.
• 2: Allan Borodin , Sandy Irani , Prabhakar Raghavan , Baruch Schieber, Competitive paging with locality of reference, Journal of Computer and System Sciences, v.50 n.2, p.244-258, April 1995
• 3: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 4: Marek Chrobak , John Noga, LRU is better than FIFO, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.78-81, January 25-27, 1998, San Francisco, California, United States
• 5: H.M. Deitel. Operating Systems. Addison-Wesley, 1990.
• 6: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 7: P.J. Denning. Working sets past and present. IEEE Transactions on Software Engineering, 6:64--84, 1980.
• 8: Amos Fiat , Anna R. Karlin, Randomized and multipointer paging with locality of reference, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.626-634, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225280]
• 9: A. Fiat , M. Mendel, Truly online paging with locality of reference, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.326, October 19-22, 1997
• 10: P. A. Franaszek , T. J. Wagner, Some Distribution-Free Aspects of Paging Algorithm Performance, Journal of the ACM (JACM), v.21 n.1, p.31-39, Jan. 1974 [doi>10.1145/321796.321800]
• 11: Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly Competitive Algorithms for Paging with Locality of Reference, SIAM Journal on Computing, v.25 n.3, p.477-497, June 1996 [doi>10.1137/S0097539792236353]
• 12: A. Karlin, S. Phillips und P. Raghavan. Markov paging. Proc. 33rd Annual Symposium on Foundations of Computer Science, 208--216, 1992.
• 13: E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. Proc. 35th Annual Symposium on Foundations of Computer Science 394--400, 1994.
• 14: New Mexico State University. Homepage of New Mexico State University TraceBase (Online). Available: http://tracebase.nmsu.edu/tracebase.html.
• 15: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 16: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 17: E. Torng. A unified analysis of paging and caching. Algorithmica, 20:175-200, 1998.
• 18: N.E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11:525--541, 1994.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Experimentation, Performance, Theory