Programmieren mit Harald R. Haberstroh

Implementieren Sie eine einfache dynamische Speicherverwaltung, die nach dem in der folgenden Skizze gezeigten Prinzip funktioniert.

Diese Speicherverwaltung soll es ermöglichen, Speicher in beliebiger Reihenfolge zu allozieren und wieder freizugeben. Siehe auch Dynamische Speicherverwaltung
Schreiben Sie ein Modul heap für die Speicherverwaltung selbst, welches folgende Funktionen enthält (exportiert):

• void *halloc(size_t size); zum Anfordern von Speicher der Größe size
• void hfree(void *p); zum Freigeben des Speichers, auf den der Zeigern p zeigt.

Erstellen Sie eine weitere Version des Moduls heap, welches bei jedem Aufruf von halloc() bzw. hfree() den gesamten Speicher in lesbarer Form auf stderr ausgibt, damit man das Allozieren der Speicherblöcke sehen kann (die Größe des Heaps sollte dabei eher klein gewählt werden!).
Schreiben Sie weiters ein Modul, welches Ihre Speicherverwaltung testet durch Anfordern von Speicher, belegen und lesen des allozierten Speichers und wieder Freigeben des Speichers in verschiedenen Varianten.
Erstellen Sie dazu eine Liste von Testfällen und beschreiben Sie das Ergebnis der Tests (die Speicherauszüge bekommen Sie mit obiger Variante des Moduls).
Beispiele von Testfällen:
n. Test: allozieren eines Strings der Länge HEAPSIZE - sizeof(heap_t), füllen des Strings mit lauter 'A' und ausgeben des Strings. OK
n+1. Test: freigeben des Speichers aus Test n. OK

Zu jedem Test ist anzugeben, ob der Test erfolgreich war. Falls ein Test nicht erfolgreich war, so ist festzustellen, warum und ggf. der Fehler zu beheben. Wird am Programm etwas verändert, so müssen alle Tests noch einmal gemacht werden!
Schreiben Sie ein passendes Makefile, mit dem man alternativ die normale Variante von heap und die Testvariante von heap erzeugen kann!
Organisieren Sie sich in Kleingruppen und versuchen Sie die einzelnen Funktionen gemeinsam zu entwerfen und zu programmieren. Welche Hilfsfunktionen braucht z.B. das halloc()?
Erweitern Sie die Speicherverwaltung um eine "Garbage Collection", die freie Speicherbereiche, die hintereinanderliegen zusammenfasst.
Erstellen Sie eine geeignete Verzeichnisstruktur und verwenden Sie CVS.
Tauschen Sie die Module mit anderen Gruppen aus (das müßte ganz einfach sein, da die Schnittstellen immer gleich sind (s.o.).
Abgabe:
Nennen Sie das Projekt 5ad-name-heap bzw. 5bd-name-heap und checken Sie es ein.
Beantworten Sie weiters folgende Fragen (die Antworten müssen in der Datei heap.txt gespeichert werden):

1. Was passiert, wenn man einen String der Länge n alloziert und einen String der Länge n speichert?
2. Was passiert, wenn man einen String der Länge n alloziert und einen String der Länge n + 1 speichert?
3. Sie allozieren einen String der Länge 11 und speichern "0123456789" und geben den String wieder frei. Danach allozieren Sie einen String der Länge 20 und geben diesen String aus. Was passiert? (die Speicheranforderungen bzw. die Freigabe muss unmittelbar hintereinander erfolgen).
4. Welche Speicheranforderungen benötigen mehr Speicher - 10 Strings der Länge 100 oder 100 Strings der Länge 10? Begründen Sie die Antwort.
5. Wie könnten Sie im Modul heap sicherstellen, dass bei einem Aufruf von hfree(p); der Parameter p tatsächlich auf einen mit halloc() allozierten Speicherbereich zeigt?

heap.txt muss auch die Liste der Testfälle mit ihren Ergebnissen enthalten.
Geben Sie einen Ausdruck der ausgearbeiteten Fragen ab!

Labels: Aufgabe, C, PR5