- Buddy-System
-
Das Buddy-Verfahren nach Donald E. Knuth ist 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 2k 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.
Der Vorteil des Verfahren besteht in der einfachen Implementierbarkeit und erfordert keine besondere Hardware-Unterstützung, wie das zum Beispiel beim Paging aktueller Betriebssysteme der Fall ist.
Siehe auch
Literatur
- Donald 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
Wikimedia Foundation.