An algorithm for locating adjacent storage blocks in the buddy system

ABSTRACT

A simple scheme for the determination of the location of a block of storage relative to other blocks is described. This scheme is applicable to the buddy type storage allocation systems.

REFERENCES

• 1: Kenneth C. Knowlton, A fast storage allocator, Communications of the ACM, v.8 n.10, p.623-624, Oct. 1965 [doi>10.1145/365628.365655]
• 2: Daniel S. Hirschberg, A class of dynamic memory allocation algorithms, Communications of the ACM, v.16 n.10, p.615-618, Oct. 1973 [doi>10.1145/362375.362392]
• 3: Hinds, James A. A design for the buddy system with arbitrary sequences of block sizes. Tech. Rep. 74, State U. of New York at Buffalo, Mar. 27, 1974.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Theory

Keywords:
buddy system, dynamics storage allocation, generalized Fibonacci sequences