| Zeile 39: | Zeile 39: | ||
== Buddy == | == Buddy == | ||
| − | Beim Buddy Verfahren wird | + | Beim Buddy Verfahren wird Speicher ausschließlich in verschiedenen festgelegten Größen allokiert, wobei diese Blöcke auf ein vielfaches ihrer Größe ausgerichtet sind. Für jede Größe existiert eine Menge mit freien Blöcken ("free list"), von denen einer gewählt wird, um die Anfrage zu erfüllen. Existiert kein freier Block der angeforderten Größe, wird ein Block der nächstgrößeren verfügbaren Größe gewählt und geteilt, wobei die ungenutzte Hälfte wieder in die entsprechende Freelist eingetragen wird. Jede Hälfte eines derartig geteilten Blocks ist der Buddy von der jeweils anderen Hälfte. |
| + | |||
| + | Gibt man Speicher wieder frei, so will man zwei direkt nebeneinander liegende freie Blöcke wieder zu einem großen freien Block zusammenfügen. Damit man dafür nicht die free list durchsuchen muss, was relativ aufwändig ist, verwaltet man für jede Blockgröße in einer Bitmap den Status eines Blocks. | ||
=== Allokation & Freigabe von Speicherseiten === | === Allokation & Freigabe von Speicherseiten === | ||
| + | |||
=== Implementierungsvorschlag === | === Implementierungsvorschlag === | ||
| + | * Für die Blockgrößen wählt man in der Regel Potenzen von 2 beginnend mit der Größe einer Seite (4 KiB), bis zu einem bestimmten sinnvollen Wert (z.B. 4 MiB). | ||
| + | * Da in jeder Menge nur gleich große Blöcke sind, kann man diese als verkettete Liste implementieren und beim Allokieren einfach immer das erste Listenelement nehmen. (First Fit -> konstanter Zeitaufwand) | ||
| + | |||
=== Eigenschaften === | === Eigenschaften === | ||
+ Schnelle Reservierung von Speicherseiten<br> | + Schnelle Reservierung von Speicherseiten<br> | ||
+ Schnelle Freigabe von Speicherseiten<br> | + Schnelle Freigabe von Speicherseiten<br> | ||
- Recht komplizierte Implementierung<br> | - Recht komplizierte Implementierung<br> | ||
| + | - Allokierbare Größen sind auf bestimmte Werte eingeschränkt, damit anfällig für interne Fragmentierung<br> | ||
== Fazit == | == Fazit == | ||