Adaptive exact-fit storage management

ABSTRACT

Tested against extremes in the characteristics of arrival patterns to dynamic allocation software, the working-set approach outperforms the FIFO method except in the case of completely random request patterns—where the working-set method performs as well as the FIFO method.

REFERENCES

• 1: Bozman. G., Buco, W.. Daly, T.. and Tetzlaff, W. Analysis of free storage algorithms-Revisited. IBM Syst. 1. 23, 1 (Feb. 1984). 44-64. A study of VM/SP shows problems with conventional methods, the predictive value of known distributions of request sizes, and the value of caching free blocks.
• 2: Gerald Bozman, The software lookaside buffler reduces search overhead with linked lists, Communications of the ACM, v.27 n.3, p.222-227, March 1984 [doi>10.1145/357994.358020]
• 3: 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]
• 4: Denning. P.J. Working sets past and present. IEEE Trans. Softw. Eng. SE-6.1 (Jan. 1960). 64-64. This is a review of research with working sets up to the date of publication.
• 5: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 6: Leverett. B., and Hibbard, P. An adaptive system for dynamic storage allocation. Sofrtu. Pracf. Exper. 12,3 (Mar. 1962). 543-555. An adaptive method in support of an ALGOL 66 implementation is explained.
• 7: Margolin, B.. Parmelee. R.. and Schatzoff, M. Analysis of free storage algorithms. IBM Syst. 1. 10, 4 (Dec. 1971). 263-304. An empirical study of CP-67 behavior, a new algorithm with variations, and performance improvements are discussed.
• 8: McGraw, J.. et al. SISAL: Streams and iteration in a singleassignment language. Lang. Ref. Man., Ver. 1.2, Lawrence Livermore National Laboratory M-146, Livermore. Calif.. 1964. This is the current reference manual for a functional language being implemented on several parallel computer systems.
• 9: Timothy George Saponas, Distributed and decentralized control in fully distributed processing systems, 1981
• 10: Smith, B. A pipelined, shared resource MIMD computer. In Proceodings of the International Conference on Parallel Processing (Bellaire, Mich.. Aug. 22-25). IEEE, New York, 1976, pp. 6-6. This is e short introduction to the architecture of the Denelcor HEP multiprocessor system.
• 11: Charles Burr Weinstock, Dynamic storage allocation techniques., 1976

INDEX TERMS

Classification:
  C. Computer Systems Organization

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Algorithms, Performance