Buddy memory allocation

According to Donald Knuth, the buddy system was invented in 1963 by Harry Markowitz, and was first described by Kenneth C. Knowlton (published 1965).

Typically the lower limit would be small enough to minimize the average wasted space per allocation, but large enough to avoid excessive overhead.

The programmer then has to decide on, or to write code to obtain, the highest possible order that can fit in the remaining available memory space.

Since the total available memory in a given computer system may not be a power-of-two multiple of the minimum block size, the largest block size may not span the entire memory of the system.

One version of the buddy allocation algorithm was described in detail by Donald Knuth in volume 1 of The Art of Computer Programming.

[2] The Linux kernel also uses the buddy system, with further modifications to minimise external fragmentation, along with various other allocators to manage the memory within blocks.