Buddy-Speicherverwaltung

Die Buddy-Speicherverwaltung bezieht sich auf das Buddy-Verfahren nach Donald Ervin Knuth, eine Technik zur Zuweisung von Speicher an Prozesse. Es zeichnet sich insbesondere durch seine Einfachheit und leichte Implementierbarkeit aus.

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 der einfachen Implementierbarkeit und erfordert keine besondere Hardware-Unterstützung, wie das zum Beispiel beim Paging aktueller Betriebssysteme der Fall ist.

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

Weblinks

• Erklärung mit anschaulichem Beispiel (PDF, 241 KiB)