Fragmentation
Two things go wrong with memory and only one of them is the famous one. The first happens inside a block: this allocator hands out powers of two, so a request for thirty-three words occupies sixty-four and the other thirty-one are gone until it is handed back. The second happens between blocks: free space can be ample and in pieces, and a request larger than any single piece fails while the total sits there unused. The allocator here is Knowlton's, published in 1965 and small enough to run in full, and the middle panel is the situation his paper states outright along with the answer, so it is a test rather than a picture. He never calls it a buddy system. The word he uses is mate.
New to how memory is handed out? Start here
A program asking for memory does not get to choose where it goes. Something keeps track of which parts of a region are in use and which are not, hands out a piece when asked, and takes it back when the program is done with it. That bookkeeping is an allocator, and the region it manages is just a range of words with no structure except the structure the allocator imposes.
The allocator here keeps blocks whose sizes are powers of two. A request is served by taking a block that is big enough, or by halving a larger one until it is the right size, and the halves of a split are tracked so they can be joined back together later. That is the entire scheme, and both kinds of waste on this page fall out of it.
Fast and forgetful, or slow and permanent
Memory is quick and loses everything when the power goes. A disk keeps what it was given and is slower by a factor with several zeroes in it. Parts that are both do exist and none has been cheap or plentiful: battery-backed memory modules are still made, and the fastest persistent part on the market was discontinued.
So nearly every design in this topic is buying one with the other. Keep it in the fast part and you are quick until the lights go out. Write it to the slow part first and you are safe but waiting. The machines here are the arrangements people found in between, and each of them is honest about which half it gave up.
The machine for this idea on its own is Write-Ahead Log, if you would rather press it than read about it.
There is enough free memory for the request and the request still fails
1 A request rounded up to a power of two, and the words left stranded inside the block
Every block this allocator hands out is a power of two words, so a request is rounded up to the next one and the difference is gone until the block is freed. That waste has nothing to do with how anything is arranged, and no amount of tidying recovers it. Move the request and watch where it lands.
| block size | holds the request | words wasted |
|---|
2 Knowlton's own worked example, run rather than drawn, against the free lists his paper states
Knowlton's paper states one situation and its outcome outright: four eight-word blocks, a request for a single word, and the free lists that result. That makes it a test rather than an illustration, so this panel runs the allocator on exactly that arrangement. At one word the answer has to be three eight-word blocks and one each of four, two and one. Ask for more and watch the splitting stop earlier.
| block size | blocks free | words |
|---|
3 An arena that is half free in pieces, and a request larger than any piece
Now the other kind. This arena is filled completely with eight-word blocks and then every other one is handed back. Each freed block's mate is still in use, so nothing can be recombined: the free space is real and it is in pieces. Ask for something larger than a piece and the request fails with plenty of memory available, which is the whole sentence this machine is named for.
| quantity | value |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| Knowlton's worked example comes out as the paper states it: three eight-word blocks and one each of one, two and four | yes | free lists after one single-word request from four eights: 1 x 1, 1 x 2, 1 x 4, 3 x 8 |
| a block's mate is its address with one bit flipped, and the bit is the block size | yes | 0 and 8 are mates at size 8; 24's mate is 16; and flipping twice returns the original, which is what makes it a pairing |
| every size the allocator hands out is a power of two, so a request of 33 words occupies 64 | yes | the paper's L6 sizes are 1, 2, 4, 8, 16, 32, 64, 128 words, and rounding up is where internal waste comes from |
| with 64 words free the allocator cannot satisfy a request for 16 | yes | 64 words are free in 8 blocks and the largest is 8, so there is room and nowhere to put it |
| five awkward requests waste 57 words before any arrangement is considered | yes | 3 takes 4, 5 takes 8, 9 takes 16, 17 takes 32, 33 takes 64: that is internal waste, and freeing everything does not recover it |
What is real here, and what is not
Knowlton never writes the word buddy, and the paper says so by omission
The familiar name for this is the buddy system and it does not appear in the paper. Knowlton calls the other half of a split a MATE, and that is the word used throughout. The name arrived later. This matters because attributing the term to the 1965 paper is the sort of thing that gets copied forward, and the document is one search away from settling it.
The idea is older than the paper, and Knowlton says so himself
A note at the end records that on completing the paper the author learned a similar storage handling system was already in use in SIMSCRIPT, where the block sizes are one, two, four and eight words, citing Markowitz, Hausner and Karr. So this is the first published description rather than the invention, and the roster's line about Markowitz being credited in 1963 comes from Knowlton's own acknowledgement rather than from a later history.
The mate rule is derived here, and the paper's example addresses do not establish it
The paper illustrates the rule by complementing one address bit, and gives worked addresses ending in 011001 and 010110. Those addresses are not aligned to the block sizes they describe: a two-word block beginning at an odd word cannot exist in this scheme. So they show WHICH bit flips rather than a legal placement, and the rule used here is derived instead: two halves of one split differ by exactly the block size, so the mate is the address exclusive-ored with it. The test asserts alignment on every live block across two hundred runs, which is the property that makes the rule valid at all.
The scan is poor and this page quotes nothing from it
The archived copy is a two-column scan whose text layer is badly degraded: the size list reads 1, 2, ,t, 8 and one of the worked addresses comes out as 01101-1. Every reference to the paper here is therefore a description rather than a quotation, which is the studio's rule when a scan cannot be quoted faithfully. The figures that matter, the size set and the worked example, are legible enough to read and are reproduced by running them.
An allocator, not a memory system
There is no operating system here, no virtual memory, no compaction and no garbage collector. The arena is a range of words and the requests are yours. Real allocators are not all buddy allocators and most modern ones are not; they use size classes, per-thread arenas and a good deal else, and they trade internal waste against speed differently. What survives all of that is the shape: rounding up wastes space inside a block, and a free list of small pieces cannot answer a large request.
The boundary with Garbage is already written down
Garbage is about reclaiming what nobody refers to any more, and every cell in that machine is one size, so nothing there can fragment. This machine is about where a block goes and what is left between blocks. The two do not overlap, and a collector that compacts is a third thing neither page models.
Sources
- Kenneth C. Knowlton, A Fast Storage Allocator, Communications of the ACM 8(10), October 1965, pages 623 to 625, Bell Telephone Laboratories. The footnote for the L6 size set of 1 to 128 words; the recombination section for the mate rule and the worked example; the closing note for the SIMSCRIPT acknowledgement.
- Logical Art, the studio this belongs to.