A time invariant working set model for independent reference

ABSTRACT

Under the Independent Reference Model (IRM) of program behavior, we study properties of the C space-time products as defined by Prieve and Fabry [21] for variable memory management algorithms. In particular, we look at the behavior of Denning's Working Set [11] and VMIN [21] algorithms. From the observed properties of these algorithms, we derive an algorithm which either keeps a page always in memory, or does not keep it at all. We show the online optimality of this algorithm under the assumption that the access probabilities are known a priori. Further, we propose a practical version of this algorithm for database and disk buffer management. By using our algorithm, we obtained space-time product improvements up to 41% over the Working Set algorithm.

REFERENCES

• 1: O. I. Aven, L. B. Boguslavsky, and Y. A. Kogan. Some results on distribution-free analysis of paging algorithms. IEEE Transactions on Computers, 25(7), July 1976.
• 2: Oleg Ivanovich Aven , E. G. Coffman, Jr. , Y. A. Kogan, Stochastic Analysis of Computer Storage, Kluwer Academic Publishers, Norwell, MA, 1987
• 3: Ozalp Babaoglu and Domenico Ferrari. Two-level replacement decisions in paging stores. IEEE Transactions on Computers, 32(12), December 1983.
• 4: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• 5: J. van den Berg , D. Toswley, Properties of the Miss Ratio for a 2-Level Storage Model with LRU or FIFO Replacement Strategy and Independent References, IEEE Transactions on Computers, v.42 n.4, p.508-512, April 1993 [doi>10.1109/12.214697 ]
• 6: R. I. Budzinski, E. S. Davidson, W. Mayeda, and H. S. Stone. DMIN: an algorithm for computing the optimal dynamic allocation in a virtual memory computer. IEEE Transactions on Software Engineering, SE-7(1), January 1981.
• 7: M. J. Carey, D. J. DeWitt, and J. F. Naughton. The OO7 benchmark. In Proceedings of 1993 ACM SIGMOD, June 1993.
• 8: Wesley W. Chu and Holger Opderbeck. Program behavior and the page-fault-frequency replacement algorithm. Computer, pages 29--38, November 1976.
• 9: P. Denning. Working sets past and present. IEEE Transactions on Software Engineering, SE-6, January 1980.
• 10: Peter J. Denning and G. Scott Graham. Multiprogrammed memory management. In Proceedings of the IEEE, June 1975.
• 11: 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]
• 12: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 13: M.C. Easton. A model for interactive data base reference strings. IBM Journal of Research and Development, 19(6):550--556, 1975.
• 14: Ronald Fagin , Malcolm C. Easton, The independence of miss ratio on page size, Journal of the ACM (JACM), v.23 n.1, p.128-146, Jan. 1976 [doi>10.1145/321921.321935]
• 15: Ram K. Gupta and Mark A. Franklin. Working set and page fault frequency algorithms: A performance comparison. IEEE Transactions on Computers, C-27(8), August 1978.
• 16: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 17: W.F. King. Analysis of paging algorithms. In Proceedings of IFIP Congress, Ljublanjana, Yugoslavia, August 1971.
• 18: James B. Morris, Demand paging through utilization of working sets onr the MANIAC II, Communications of the ACM, v.15 n.10, p.867-872, Oct. 1972 [doi>10.1145/355604.361592]
• 19: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 20: Vidyadhar Phalke , B. Gopinath, Program Modelling via Inter-Reference Gaps and Applications, Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.212-216, January 10-18, 1995
• 21: Barton G. Prieve , R. S. Fabry, MIN—an optimal variable-space page replacement algorithm, Communications of the ACM, v.19 n.5, p.295-297, May 1976 [doi>10.1145/360051.360231]
• 22: Gururaj S. Rao, Performance Analysis of Cache Memories, Journal of the ACM (JACM), v.25 n.3, p.378-395, July 1978 [doi>10.1145/322077.322081]
• 23: A.J. Smith. A modified working set paging algorithm. IEEE Transactions on Computers, 25(9), September 1976.
• 24: Alan Jay Smith. Analysis of optimal look -ahead demand paging algorithms. SIAM Journal of Computing, 5(4), December 1976.
• 25: A. Inkeri Verkamo, Empirical results on locality in database referencing, Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.49-58, August 1985, Austin, Texas, United States

INDEX TERMS

Keywords:
independent reference model, space-time product, trace driven simulation, variable memory management