Buddy-Speicherverwaltung

Die Buddy-Speicherverwaltung (Buddy: engl. für "Kumpel") bezieht sich auf das Buddy-Verfahren nach Donald Knuth, eine Technik zur Zuweisung von Speicher an Prozesse. Das Verfahren ist einfach und leicht zu implementieren.

Veranschaulichung des Verfahrens. Die Fragmentierung in der Grafik gibt dabei jeweils die Interne Fragmentierung an. Aufgrund der Externen Fragmentierung können Teilweise nur Blöcke eingelagert werden, die eine geringere Größe haben als der Gesamte verfügbare Speicher. Bspw. beträgt die maximale Blockgröße nach der Allokation von W 64 Bytes, trotz einer Restkapazität von 112 Bytes.

Funktion

Der Speicher wird in Bereiche der Länge 2^k aufgeteilt. Zu Beginn gibt es nur einen Block, der möglichst den gesamten Speicher abdeckt; wenn die Größe des Speichers sich nicht als Zweierpotenz ausdrücken lässt, können es auch mehrere Blöcke unterschiedlicher Größe sein. Fordert nun ein Prozess eine bestimmte Menge Speicher an, so wird zur nächsthöheren Zweierpotenz aufgerundet und ein entsprechender Block gesucht. Falls es noch keinen Block dieser Größe gibt, wird nach einem Block doppelter Größe gesucht, der dann in zwei Hälften (bzw. Buddies) aufgeteilt wird, und einer dieser Blöcke wird dem Prozess zugewiesen. Gibt es auch keinen Block doppelter Größe, wird ein Block vierfacher Größe gesucht usw. Sobald Speicher wieder freigegeben wird, wird geprüft, ob zwei durch Teilung entstandene Buddies gleicher Größe sich wieder zu einem größeren Block zusammenfassen lassen.

Vor- und Nachteile

Der Vorteil dieser Speicherverwaltung besteht in ihrer einfachen Implementierbarkeit. Sie erfordert keine besondere Hardware-Unterstützung, wie das z. B. beim Paging aktueller Betriebssysteme der Fall ist.

Der Nachteil ist, dass es sowohl zu interner als auch zu externer Fragmentierung kommen kann. Auch kann durch die Art der Zuteilung Speicher verschwendet werden, was sich durch die Angabe einer kleinsten Blockgröße jedoch begrenzen lässt.

Erweiterungen

Eine Erweiterung stellt die gewichtete Buddy-Speicherverwaltung dar. Hierbei wird nicht immer im Verhältnis 1:1 geteilt, sondern zum Beispiel im Verhältnis 1:3, wobei der zweite Zweig dann im Verhältnis 1:2 geteilt wird. Dadurch entstehen unterschiedlichere Buddygrößen. Dafür wird aber der Verwaltungsaufwand höher und die Adressberechnung wird schwieriger.

Literatur

• Donald E. Knuth: The Art of Computer Programming Volume 1: Fundamental Algorithms. Second Edition (Reading, Massachusetts: Addison-Wesley, 1997) (engl.), S. 435–455. ISBN 0-201-89683-4