Zum Abschluss noch ein kurzer Überblick über die Aufgabe Halte und einige weitere

Beispiele zur Implementierung einer Freispeicherliste.

Zu den Zielen der Aufgabe gehört, dass ihr den Zusammenhang zwischen nacktem Speicher,

den ihr einfach irgendwie benutzt, und typisierten Datenbereichen versteht.

Also, dass ihr einfach in Speicher einen Typ hineinlegen könnt.

Außerdem sollt ihr eigene C-Bibliotheksfunktionen selbst realisieren.

Das heißt, ihr sollt malloc, realoc, caloc und free implementieren.

Dabei soll euch helfen, dass ihr euer Programm mit make kompiliert.

Dies stellt vor allem eine Unterstützung für die weiteren Aufgaben dar, da diese aus mehreren

Dateien bestehen werden.

Außerdem sollt ihr euch eigene Testfälle überlegen, wie ihr prüfen könnt, ob euer

Code überhaupt richtig ist.

Da eine gute Implementierung einer Speicherverwaltung alles andere als trivial ist, gibt es hier

einige Vereinfachungen.

Als Allokationsstrategie nutzen wir einfach Firstfit.

Das bedeutet, der erste Block in der freispeicherliste, der von der Größe groß genug ist, wird genommen.

Außerdem braucht ihr nicht zusätzlichen Speicher vom Betriebssystem anzufordern.

Stattdessen wird einmal statisch ein 1 Mb-Großer Speicherblock allokiert, in dem dieser einfach

als statisch globale Variable deklariert wird.

Innerhalb dieses Speicherblocks könnt ihr eure Freispeicherliste unterbringen.

Diese besteht aus einer einfach verketteten Liste, die nicht sortiert werden muss und

benachbarte Blöcke müssen ebenfalls nicht verschmolzen werden.

Bei Realloc sollt ihr auf die Funktionen malloc, memcpy und free zurückgreifen.

Hier noch einige Beispiele, wie die Freispeicherverwaltung aussieht.

Diese könnt ihr am besten selbstständig am Plattpapier bearbeiten und an die folgenden

Folien einfach nur noch dazu benutzen, zu kontrollieren, ob ihr alles richtig skizziert

habt.

In den Beispielen gehen wir davon aus, dass wir einen 64-byte großen Speicherblock verwalten

und dass die Verwaltungsstruktur 16 byte groß ist.

Im Szenario 1 wird einfach einmal malloc aufgerufen von 5 byte.

Das bedeutet, wir haben eine neue Restliste mit einem Element, die noch 27 byte verwaltet.

Beim zweiten malloc werden diese 27 byte weiter aufgeteilt und wir haben eine Restliste,

die noch 4 byte verwaltet und aus einem Element besteht.

Wenn wir darauf ein free aufrufen, wird die Liste um ein Element erweitert und der Kopfte-Liste

wird umgesetzt.

Im zweiten Beispiel allokieren wir zu Beginn 20 byte.

Das bedeutet, die Restliste verwaltet noch 12 byte.

Im nächsten Schritt wird der eben allokierte Speicher sofort wieder freigegeben.

Also haben wir nun eine zweielementige Liste, die einmal 20 und einmal 12 byte freien Speicher

beinhaltet.

Der Kopfte-Liste ist dabei das neu freigewordene Speicher-Element, der Größe 20 byte.

Wenn wir im nächsten Schritt wieder 4 byte allokieren, werden wir feststellen, dass der

Kopfte-Liste groß genug ist, um dieser Allokation zu genügen.

Gleichzeitig sehen wir aber, dass wenn wir 4 byte freigeben, wir noch 16 byte weiter

zur Verwaltung haben, innerhalb dieses Speicherblocks.

Die restlichen bytes würden aber durch eine Verwaltungsstruktur, die 16 byte groß ist,

vollständig aufgebraucht werden.

Das bedeutet, die Verwaltungsstruktur würde 0 byte verwalten.

Da sich dies nicht lohnt, wird die Größe des Blocks nicht geändert.

Es bleibt also bei 20 byte und dem Nutzer wird mehr Speicher zugewiesen, als er angefordert