Worst-case analysis of memory allocation algorithms

ABSTRACT

Various memory allocation problems can be modeled by the following abstract problem. Given a list A &equil; (&agr;1,&agr;2,...&agr;n,) of real numbers in the range (0, 1], place these in a minimum number of “bins” so that no bin holds numbers summing to more than 1. We let A* be the smallest number of bins into which the numbers of list A may be placed. Since a general placement algorithm for attaining A* appears to be impractical, it is important to determine good heuristic methods for assigning numbers of bins. We consider four such simple methods and analyze the worst-case performance of each, closely bounding the maximum of the ratio of the number of bins used by each method applied to list A to the optimal quantity A*.

REFERENCES

• 1: P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting stock problem II, Oper. Res. 11 (1963), pp. 863-;888.
• 2: R.W. Conway, W. L. Maxwell and L. W. Miller, Theory of Scheduling, Addison-Wesley, Reading, Mass. (1967).
• 3: S. Eilon and N. Christofides, The loading problem, Manag. Sci. 17, no. 5 (1971), pp. 259-;268.
• 4: R. C. Prim, private communication.
• 5: J. Curry, private communication.
• 6: R. L. Graham, Bounds on multiprocessing anomalies and related packing algorithms, to appear in Proc. of 1972 SJCC.
• 7: A. Demers and J. D. Ullman, (in preparation).

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

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

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

General Terms:
Management, Performance