- Buddy-Speicherverwaltung
-
Die Buddy-Speicherverwaltung bezieht sich auf das Buddy-Verfahren nach Donald E. Knuth, eine Technik zur Zuweisung von Speicher an Prozesse. Es zeichnet sich insbesondere durch seine Einfachheit und leichte Implementierbarkeit aus.
Inhaltsverzeichnis
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.
Kritik
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.
Nachteil ist, dass es sowohl zu interner als auch zu externer Fragmentierung kommen kann.
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.
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
Weblinks
- Erklärung mit anschaulichem Beispiel (PDF, 241 KiB)
Kategorien:- Theoretische Informatik
- Speicherverwaltung
- Betriebssystemtheorie
Wikimedia Foundation.
