An heuristic model for analysis of memory use under static partition allocation strategies

ABSTRACT

This paper examines minimum memory wastage strategies for partitioning and allocating main memory to a stream of jobs, in a context where each job resides throughout its execution in a frame to which it is assigned. In contrast to usual approaches, the present one considers core memory as the main limiting resource, and assumes that job competition for other resources can be neglected. From job mix characteristics, a condition for a given memory partition to avoid system saturation is postulated. Then, among such partitions avoiding saturation, we are interested in 1) those requiring the least amount of space, 2) those leading to the lowest core fragmentation. Concerning the first problem, we give a simple method for generating the smallest partition, and show that “exact fit” allocation should be used. As for the second problem, if a partition is given so that exact fit meets the overload constraint then this algorithm is optimal; otherwise, best fit would be the best algorithm.

REFERENCES

• 1: Betteridge, T., "An Analytic Storage Allocation Model," Acta Informatica, vol. 3, pp. 102-122 (1974).
• 2: Buzen, J.P. and Rubin, D.B., "Effects of Compaction on Memory Utilization in Multiprogramming Systems," Computer Architecture and Networks, Gelenbe and Mahl (eds.), North Holland Publishing Co. pp. 113-124 (1974).
• 3: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 4: Gelenbe, E., "The Two-Thirds Rule for Dynamic Storage Allocation under Equilibrium," Inf. Proc. Letters, vol. 1, pp. 59-60 (1971).
• 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: Stuart E. Madnick , John J. Donovan, Operating Systems, McGraw-Hill, Inc., New York, NY, 1974
• 7: B. Randell, A note on storage fragmentation and program segmentation, Communications of the ACM, v.12 n.7, p.365-ff., July 1969 [doi>10.1145/363156.363158]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Management