Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Buddy-Allokation
Nachdem ich vorhin per Mail eine Frage zu den Speicherverwaltungs-Aufgaben in Altklausuren beantwortet habe, dachte ich, ich stelle meine Antwort auch gleich der Öffentlichkeit zur Verfügung.
Das Besondere am Buddy-Verfahren ist ja, dass der Speicher nur in Blöcken in Zweierpotenzgröße rausgegeben wird. Diese Eigenschaft kann man ausnutzen, indem man eine andere, effizientere Verwaltungsstruktur verwendet als die verkettete Liste, die beim {First, Best, Worst}-Fit-Verfahren zum Einsatz kommt.
Und zwar verwendet man eine Tabelle, in der jede Zeile eine Blockgröße repräsentiert. Jedes Element der Tabelle ist eine Liste der Anfangsadressen der aktuell freien Blöcke dieser Größe.
Angenommen, man hat die folgenden drei Freispeicherblöcke (Adresse, Größe):
(A 384, G 128)
(A 512, G 256)
(A 768, G 128)
Dann sieht die Freispeichertabelle folgendermaßen aus:
Größe | Anfangsadressen
------+----------------
2^9 | -
2^8 | 512
2^7 | 384, 768
2^6 | -
... | -In der Tabelle stehen also nur die Anfangsadressen der freien Blöcke drin. Die Größe selber wird gar nicht explizit in der Tabelle vermerkt, sondern nur implizit - sie lässt sich trivial über die Zeilennummer ausrechnen (per Zweierpotenz).
Wenn jetzt jemand ein Stück Speicher mit einer bestimmten Größe allozieren will, wird diese zunächst auf die nächste Zweierpotenz aufgerundet. Dann wird in der entsprechenden Zeile der Tabelle (Zweierlogarithmus der aufgerundeten Größe) nachgeguckt, ob ein freier Block dieser Größe existiert.
Wenn ja: Block aus der Tabelle rausschmeißen, fertig.
Wenn nein, dann existiert vielleicht ein größerer Block, aus dem man sich ein passendes Stück rausschneiden kann. Also läuft man in der Tabelle die Zeilen drüber ab und guckt, ob da irgendwelche Einträge existieren. Falls man einen findet, halbiert man ihn so oft, bis die gewünschte Größe erreicht ist, und fügt die jeweils anderen Hälften wieder in der jeweils richtigen Zeile ein.
Dazu ein Mini-Beispiel: [m]malloc(50)[/m] mit der obigen Tabelle
Nächste Zweierpotenz: 64 = 2^6
In Zeile 6 steht nichts drin, also guckt man in Zeile 7.
In Zeile 7 wird man fündig! \o/ Man schnappt sich den ersten Block (an Adresse 384) und schmeißt ihn aus der Tabelle raus.
Man halbiert diesen Block, gibt die erste Hälfte (A 384, G 64) als Ergebnis der Allokation zurück und klebt vorher noch schnell die zweite Hälfte (A 448, G 64) zurück in Zeile 6 der Tabelle.
Die schaut danach folgendermaßen aus:
Größe | Anfangsadressen
------+----------------
2^9 | -
2^8 | 512
2^7 | 768
2^6 | 448
... | -Was passiert, wenn der Aufrufer den soeben allozierten Block (A 384, G 64) wieder freigeben will?
Als erster (Zwischen-)Schritt wird der freigegebene Block ganz normal in die Tabelle geklebt. [In der Klausur gehen wir davon aus, dass ihr diesen Zwischenschritt im Kopf oder auf Schmierpapier macht und nur das Endergebnis hinschreibt.]
64 = 2^6, also muss man ihn in Zeile 6 eintragen:
Größe | Anfangsadressen
------+----------------
2^9 | -
2^8 | 512
2^7 | 768
2^6 | 384, 448
... | -Jetzt stellt man fest: In Zeile 6 steht bereits ein anderer Eintrag. Die beiden Blöcke liegen im Speicher direkt hintereinander, und wenn man sie zusammenfassen würde, würde der resultierende Block (A 384, G 128) auf einem Vielfachen seiner eigenen Größe liegen. Die beiden 64-Byte-Blöcke sind also Buddys! Würde der resultierende Block nicht auf einem Vielfachen seiner Größe liegen, wären die beiden keine Buddys und dürften nicht zusammengefasst werden.
Hier geht’s aber, also kickt man die beiden Buddys aus Zeile 6 raus und fügt den verschmolzenen Block in Zeile 7 ein. Danach guckt man in Zeile
7, ob vielleicht dort wiederum Buddys entstanden sind, die man verschmelzen könnte - ist bei unserem Beispiel jetzt aber nicht der Fall. Das Endergebnis sieht also folgendermaßen aus:
Größe | Anfangsadressen
------+----------------
2^9 | -
2^8 | 512
2^7 | 384, 768
2^6 | -
... | -Und damit haben wir wieder dieselbe Situation hergestellt wie oben vor der Allokation.
Hierfür muss man sich aber noch gesondert merken, wie groß der Block eigentlich war, oder? Also in ner gesonderten Datenstruktur speichern oder ähnlich zu der Halde (super Aufgabenname!) am Anfang des Blocks.
Das ist nicht nötig, denn der Block wird in genau die Zeile der Tabelle eingetragen, die mit seiner Größe korrespondiert. Wenn du weißt, in welcher Zeile der Block steht, kennst du automatisch auch seine Größe (und umgekehrt).
Siehe unten.
Mir ging es jetzt um die konkrete Implementierung von [m]free[/m], da steht der Block ja nicht in der Freispeichertabelle und ich brauche seine Größe, um ihn einsortieren zu können, die lässt sich aber nicht irgendwie magisch aus der Adresse ermitteln, oder?
Ahso, das meintest du! Ja, die Größeninformation muss irgendwo mitgeführt werden, solange der Block vergeben ist: entweder am Blockanfang (dafür müsste man bei der Allokation entsprechend ein paar Bytes draufaddieren) oder irgendwo separat.
Nur solange der Block in der Freispeicher-Tabelle drinsteht, braucht man seine Größeninformation nicht explizit zu speichern.
Perfekte Erklärung, thx von mir und meiner Übungsgruppe
Was passiert bei Buddy wenn ich kein passendes Loch mehr finden kann?
Also wenn ich z.B. 300 anfordere und ich habe nur noch Löcher mit 2x 128, 1x256 und 1x64?
Ich führe ja kein Buch über den Rest von meinen vergebenen Löchern. Z.b. wenn 70 von 128 belegt ist, ist da intern noch 58 frei, aber das kann ich nicht mehr nutzen, richtig?
Ist das eben dieser Nachteil des Verfahrens, dass (viel) interner Verschnitt entsteht?
Dann sollte die Speicherallokation bei einfachen Implementierungen failen.
Bin vorhin auch erschrocken, als ich beim durcharbeiten der Klausuraufgabe auf einmal zum Ergebnis kam Speicher nicht rausgeben zu können.
Interner Verschnitt kann rein theoretisch nur von dessen „Besitzer“ verwendet werden. Externer Verschnitt kann ohne Umordnung hingegen gar nicht mehr verwendet werden (mit irgendwelchen Fancy-Methoden könnte man da womöglich noch etwas zusammen hacken, aber das nur als Vermutung meinerseits). Wie du richtig erkannt hast liegt hier interner Verschnitt vor und dieser Speicherbereich kann nicht an andere [m]allocs()[/m] ausgegeben werden.
Edit: man könnte versuchen beim Fail einer allocation Umstrukturierungen vorzunehmen, so dass ein genügend großes Speicherstück zusammen gekratzt werden kann. Ob dies in der Klausuraufgabe allerdings zum geforderten Teil gehört, weiß ich nicht.
Edit2: mir fällt gerade auf, dass deine Zahlen gar nicht zu denen der Klausuraufgabe passen. Dort konnte man, sofern meine Kritzeleien stimmen, auch nach Umstrukturierung nichts verschmelzen. Folglich könnte ich mir durchaus vorstellen diesen Versuch beim fail auch in der Klausur vornehmen zu müssen, da dieser Prozess streng genommen noch zur Aufgabe der [m]allocs()[/m] gehört.
Wenn du keinen Bereich der passenden Größe hast, dann ist das einfach [m]ENOMEM[/m] und [m]malloc(3)[/m] gibt [m]NULL[/m] zurück. Zusammenkratzen kannst du da nichts mehr, da du ja die schon rausgegeben Pointer nicht verändern kannst, und du keine Löcher der passenden Größe mehr frei hast (sonst hättest du diesen Bereich ja verwenden können).
Ich dachte bei dem “Zusammenkratzen” eher an Auflösung externer Fragmentierung. War hier aber quatsch^^
Edit: Wobei wer weiß, vielleicht wird das Buddy-Verfahren auch auf Datenträgern verwendet und das [m]malloc[/m] soll gar keinen Speicher vom Heap rausgeben. 
/troll