Das Buddy-System (auch Halbierungsverfahren) ist ein Verfahren zur Verwaltung und Vergabe von Speicherblöcken, bei dem nur Blockgrößen verwendet werden, die einer Zweierpotenz entsprechen (2k). Es wird unter anderem im Linux-Kernel als Basis der Seitenverwaltung eingesetzt und zeichnet sich durch schnelles Allokieren und Freigeben aus.
So funktioniert der Buddy-Allokator
Der freie Speicher ist in Listen von Blöcken organisiert — je eine Liste pro Zweierpotenz-Größe. Eine Anforderung wird auf die nächstgrößere Zweierpotenz aufgerundet. Existiert kein passender freier Block, wird ein größerer Block halbiert: Die beiden Hälften sind Buddies, also Partnerblöcke gleicher Größe, die sich an einer bekannten Adressgrenze berühren. Die Halbierung wird wiederholt, bis ein Block der gewünschten Größe entsteht. Bei der Freigabe wird geprüft, ob der Buddy-Partner ebenfalls frei ist; wenn ja, werden beide zum doppelt so großen Block verschmolzen (Buddy-Merge). Dieser Vorgang kann sich rekursiv fortsetzen und hält die externe Fragmentierung gering.
Vorteile und Nachteile
- Vorteil: Allokation und Deallokation sind sehr schnell (O(log n)); durch die Verschmelzung freier Buddies bleibt der Speicher gut nutzbar.
- Nachteil: Es entsteht interne Fragmentierung (Verschnitt), weil auf Zweierpotenzen aufgerundet wird — eine 70-KB-Anforderung belegt 128 KB und lässt 58 KB ungenutzt.
- Variante: Beim gewichteten Buddy-System werden Blöcke nicht zwingend halbiert, sondern etwa im Verhältnis 1:3 geteilt; das reduziert Verschnitt, erzeugt aber mehr Fragmentierung bei der Verwaltung.
Einsatz im Linux-Kernel
Der Linux-Kernel nutzt den Buddy-Allokator zur Vergabe von Speicherseiten (page frames, siehe Seitenrahmen). Darauf setzt der SLUB-Allocator für kleine Kernel-Objekte auf. Auch andere Allokatoren wie jemalloc verwenden teils Buddy-artige Strukturen für große Blöcke.
Verwandte Grundlagen: Fragmentierung, Speichersegmentierung, Memory Paging, Virtueller Speicher.