Dynamische Speicherverwaltung

Ein Überblick

Viele Programme folgen einem einfachen Schema. Der Programmierer legt in seinem Programm fest, welche Variable er benötigt und schreibt den Quellcode zur Bearbeitung des Problems.

Es gibt aber eine ganze Reihe von Aufgaben, die erst zur Laufzeit ermitteln können, wie viele Variable oder Speicherplatz sie benötigen.

Zur Menge dieser Programme gehören alle Übersetzer (Assembler und Compiler). Der Autor eines Compilers kann nicht im voraus wissen, wie viele Namen im gerade übersetzten Programm definiert wurden.. Er muß jedoch alle Namen intern in einer Symboltabelle speichern. Wie groß die Tabelle sein muß, ergibt sich erst, wenn das Programm läuft.

Ein weiteres Beispiel ist ein Editor. Er weiß auch nicht, wie groß die jeweils zu bearbeitende Datei oder eine einzelne Zeile sein wird. Es gibt Editoren, die beschränken einfach die Größe des Textes, legen für jede Zeile den maximal benötigten Speicherplatz an und umgehen damit das Problem. Das Beispiel “Zeile” wollen wir nun näher untersuchen. Unsere Zeile soll eine variable Länge erhalten, um keinen Speicherplatz zu verschwenden.

Eine Leerzeile enthält nur ein Zeilenendezeichen; eine volle Zeile kann in vielen Editoren bis zu 255 Zeichen lang sein. Was wir benötigen, ist eine Klasse, mit der man Zeilen unterschiedlicher Länge anlegen kann. Die Länge soll bei der Initialisierung eines Zeilenobjektes ermittelt werden.

Die Halde, der Heap

Wollen wir während der Laufzeit dynamisch Speicherplatz für das Programm reservieren, benötigen wir einen Speicherbereich, der dafür angelegt wird. Diesen Speicherbereich nennt man Halde. Ein anderer Ausdruck ist - auf gut Englisch - "heap". Die Implementierung hängt sehr von der verwendeten Maschine und dem darauf laufenden Betriebssystem ab.

Ein Compiler übersetzt ein Programm und legt verschiedene Segmente (durchgängige Abschnitte) an. Die einzelnen Segmente enthalten den Code (oder “text” bei Linux/), die globalen Daten und schließlich ein Segment für den Stack (Stapelbereich).

Je nach Betriebssystem wird der verbleibende Speicher oder ein eigenes Segment benutzt, um mit Hilfe des Betriebssystems dem Programm während der Laufzeit zusätzlichen Speicher zur Verfügung stellen zu können.

In der Welt der DOS/Windows PC's wurden noch zusätzlich sogenannte Speichermodelle erfunden. Das Bild 5-1 zeigt das Small-Modell der Daten für DOS-Compiler. Das Beispiel kann man gut zur Erklärung benutzen.

Im "small"- Modell fasste man alle logischen Datensegmente in einem einzigen physikalischen Speichersegment zusammen. Der Stack wird ans obere Ende gelegt, die Daten nach unten. Nach alter C-Tradition unterscheidet man noch zwischen initialisierten globalen Daten (in “data”) und nicht initialisierten (in “bss”), die beim Laden mit “0" vorbelegt werden. Der Segmentname ”bss" steht dabei für “block started with symbol”.

Der verbleibende Speicherplatz zwischen Stack und Daten blieb frei und konnte für die Halde genutzt werden. Da das gesamte Speichersegment nicht über 64kB groß werden konnte, konnten auch dynamische Variable (Felder) diese Grenze nicht überschreiten.

Je nach Betriebssystem gelten andere Spielregeln. Das Beispiel sollte nur helfen, den Begriff "heap" etwas anschaulicher zumachen.

Die Halde wird über eine Liste verwaltet. Jeder neu reservierte Bereich wird in die Liste eingehängt und beim Freigeben wieder ausgekettet. Dieses Verfahren ist aufwendiger als z.B. die Stackverwaltung. Es hat aber den Vorteil, daß man Speicher in beliebiger Reihenfolge wieder freigeben kann (siehe Bild 5-2).

Mit Hilfe der Halde wollen wir nun die Klasse “Zeile” entwickeln. Eine Zeile läßt sich einfach als Klasse definieren, wenn wir zwischen Verwaltung und Inhalt unterscheiden. In einem Zeilenobjekt speichern wir die gewünschte Länge und einen Zeiger auf den Inhalt. Den Platz für den Inhalt können wir dynamisch anlegen.

Im folgenden betrachten wir zuerst die Funktionen “malloc()” und “free()” in C. Dabei können wir wichtige Grundlagen sehen. Danach wenden wir uns den neuen Schlüsselworten “new” und “delete” zu. Die dynamische Speicherverwaltung ist für die Bearbeitung dynamischer Probleme so wichtig, daß viele Sprachen, darunter C++ und Pascal, sie in die Sprachdefinition aufgenommen haben.

Funktionen malloc() und free()

Die Funktionen “malloc()” und “free()” finden sich in der C-Standardbibliothek. Auch wenn sie bei C++ normalerweise noch vorhanden sind, sollte man sie nicht mehr verwenden. Sie dienen hier nur der Demonstration.

Die Funktion “malloc()” erhält als Parameter die Anzahl der gewünschten Bytes. Mit der Länge wird “malloc()” einen Bereich im Hauptspeicher reservieren und einen Zeiger darauf zurückgeben. Im Fehlerfall, wenn kein Speicherbereich mit der gewünschten Länge gefunden werden konnte, dann gibt “malloc()” die ungültige Adresse “NULL” zurück. “NULL” wird in der Datei “stdio.h” zumeist als die Zahl “0" definiert, die man als Adresse benutzt.

Rahmen7Die Funktion “malloc()” erhält einen Parameter des Datentyps “size_t”. Dieser Datentyp wird von “sizeof” als Rückgabetyp benutzt und bedeutet meist: Länge in Bytes. Oft wird dieser Typ in der “stdlib.h” als “unsigned int” definiert. Bei der Übersetzung wird mit dem Präprozessor “size_t” durch “unsigned int” ersetzt. Den Begriff “Bytes” gibt es in C eigentlich nicht. Das einzige Schlüsselwort, das eine grundlegende Speichereinheit kennt, ist “sizeof”. C++ kennt inzwischen den Begriff “Byte”.

Der Rückgabewert ist ein typloser Zeiger: “void *”. Da in C++ einem Zeiger nur eine typgerechte Adresse zugewiesen werden darf, muß die Typwandlung beim Aufruf angegeben werden.

Weist man einem Zeiger ohne Typinformation den Inhalt eines beliebigen anderen Zeigers zu, dann ist dies zulässig. Bei der Zuweisung geht für den Zielzeiger die vorhandene Typinformation verloren. Will man umgekehrt einem Zeiger mit Typinformation den Inhalt eines typlosen Zeigers zuweisen, dann fehlt die Typinformation. Daher ist dies unzulässig.

Die Fehlerabfrage erkennt am Rückgabewert “NULL” (der in anderen Sprachen auch NIL heißt), den Erfolg oder Misserfolg des Aufrufes. Bei Misserfolg bricht das Programm mit “exit (1)” ab. Bei Erfolg wird das Programm abgearbeitet und gelangt schließlich zum Gegenstück von “malloc”, der “free”-Funktion (siehe Bild 5-4).

Die Funktion “free()” erwartet als Parameter die Adresse eines Speicherbereiches, der mit “malloc()” dynamisch angelegt wurde. An “free()” dürfen keine anderen Adressen übergeben werden.

Bei der Benutzung dynamischer Variable gilt in allen Fällen der Grundsatz, daß jeder reservierte Bereich genau eine Freigabe erhalten muß. Wird in einem Programm immer wieder Speicherbereich reserviert, aber nie zurückgegeben, dann ist es nur eine Frage der Zeit, bis das Programm an einen “malloc()”-Aufruf gerät, der keinen Speicher mehr findet. Im guten Fall, wenn der Programmierer den Rückgabewert geprüft hat, dann bricht das Programm ab. Ohne Prüfung ist das Ergebnis nicht vorhersagbar. Da solche Fehler zusätzlich auch vom momentan verfügbaren Speicher des Computers abhängen, sind sie oft schwer zu finden.

Das Gegenstück dazu ist die mehrfache Freigabe. Auch das kann erst während der Laufzeit gefunden werden. Je nach Compiler meldet die Verwaltungsroutine dann “Heap corrupted” (Halde zerstört) oder auch gar nichts. In jedem Fall ist es ein schwerer Fehler.

Es ist daher sicher eine gute Empfehlung, die Verwaltung dynamischer Variablen im Programm möglichst einfach zu halten und genau zu kontrollieren.

Die Operatoren “new” und “delete”

In C++ nahm man die dynamische Speicherverwaltung mit in den Sprachumfang auf. Dazu dienen die beiden Schlüsselworte "new" und “delete”.

"new" liefert, wie “malloc()”, eine Adresse auf einen reservierten Speicherplatz zurück. Die Adresse wird mit dem korrekten Datentyp versehen.

Rahmen11Im obigen Beispiel nimmt der Zeiger "ip" die Adresse der dynamischen Variablen auf. Nach “new” wird der gewünschte Typ angegeben. Der Compiler kann aus dieser Information die benötigte Speichergröße ableiten. Weiter kann für eine einzelne Variable der gewünschte Initialisierungswert in runden Klammern angegeben werden. Die Syntax ähnelt dem Anlegen von Objekten. Bei jedem Anlegen einer dynamischen Variablen muß der Rückgabewert geprüft werden. Am Ende der Bearbeitung wird mit “delete” der reservierte Speicher wieder freigegeben.

Anlegen von Feldern mit Grunddatentypen

Felder können ebenfalls mit "new" angelegt werden. Die explizite Initialisierung ist nicht möglich. Sie erfolgt mit dem Default-Konstruktor. Da die Speicherverwaltung sich die Länge des Speicherbereiches merkt, genügt bei Standarddatentypen wieder eine einfache “delete”-Anweisung zum Freigeben.

Die Syntax läßt es aber zu, daß man zwischen dem Schlüsselwort "delete" und dem Zeiger auf den dynamischen Speicherbereich dem Compiler mitteilt, dass es sich um ein Feld handelt. Eine Angabe der Feldgröße bei “delete” ist nicht (mehr) erlaubt.

Wichtig für die Anwendung ist es noch, daß die Größenangabe auch eine Variable oder ein Ausdruck sein darf. Die tatsächlich verwendete Größe kann damit während der Laufzeit berechnet werden.

Dynamische Objekte

Objekte können entweder als Einzelobjekt mit expliziter Initialisierung oder als Feld mit Standardinitialisierung angelegt werden. Ein uninitialisiertes Objekt wird nur bei völligem Fehlen von Konstruktoren angelegt. Bei Feldern wird automatisch der parameterlose Standard-Konstruktor gerufen.

Zusätzlich zur Größenermittlung und der typgerechten Adreßrückgabe kommt beim Anlegen von Objekten im Normalfall der Konstruktoraufruf für jedes Objekt des Feldes hinzu.

Rahmen15Im Gegensatz zu den Feldern mit Grunddatentypen muß man bei “delete” dem Compiler mitteilen, daß es sich um ein Feld handelt. In älteren C++-Versionen mußte man auch beim “delete” die Größe des zu löschenden Feldes angeben. Dies hat sich jedoch als zu fehleranfällig erwiesen, so daß im Standard keine Größenangabe mehr erlaubt ist.

Ein Beispiel: die Zeile

In den bisherigen Beispielen mit der Klasse “ratio” war der gesamte Speicherbedarf eines Objektes bereits während der Übersetzungszeit bekannt. Anders verhält es sich, wenn ein Objekt nicht die gesamte Speicherung der Eigenschaften beinhaltet, sondern nur mit einem Zeiger auf den aktuell benutzten Speicher zeigen will, wie es bei einem allgemeinen Text der Fall sein kann.

Mit Hilfe der dynamischen Speicherverwaltung können wir nun beginnen, die Klasse “Zeile” zu programmieren. Als (private) Eigenschaften benutzen wir eine Längenangabe und einen Zeiger auf den dynamisch anzulegenden Datenbereich. Die (öffentlichen) Methoden sollen vorerst nur aus Konstruktor, Destruktor und der Ausgabe bestehen.

Der Konstruktor erwartet einen normalen C-Text. Texte in C sind “Felder aus char” und tragen die Endekennung “\0". Beim Anlegen eines Zeilenobjektes wird dynamisch Speicherplatz reserviert. Der reservierte Speicherplatz muß spätestens am Ende der Lebensdauer eines Objektes wieder zurückgegeben werden. Dies ist die typische Aufgabe für den automatisch gerufenen Destruktor.

Rahmen19Im Konstruktor im Bild 5-10 ermitteln wir zuerst die tatsächlich vorhandene Länge in "char". Dabei setzt die Funktion “strlen()” voraus, daß der Text mit einem Endezeichen “\0" abgeschlossen ist. Um auch den Platz für das Endezeichen zu berücksichtigen, erhöhen wir die von ”strlen()" ermittelte Anzahl um eins.

Damit wissen wir den benötigten Speicherbedarf und können ihn mit “new” anlegen. Im Fehlerfall, wenn “new” durch Rückgabe der NULL meldet, daß kein Speicher mehr vorhanden ist, bricht der Konstruktor das Programm mit der Funktion “exit()” ab. Deren Parameter ist der Programmendestatus. Ein Programmendestatus ungleich 0 wird innerhalb einer Batch-Datei als Fehlermeldung interpretiert. Schließlich kopiert “strcpy()” noch den Inhalt des Initialisierungstextes in den eigenen Puffer (Zeile 14).

Das einfache Gegenstück zum Konstruktor ist der Destruktor. Hier wird der dynamisch angelegte Speicherplatz wieder freigegeben. Da der Destruktor automatisch am Ende der Lebensdauer aufgerufen wird, brauchen wir uns um die Verwaltung der Halde keine weitere Gedanken zu machen.

Wichtig ist nur, daß der Zeiger “Inhalt” im Konstruktor auf einen eigenen Speicherbereich zeigt. Es darf also nie vorkommen, daß nur eine Adresse kopiert wird, ohne einen eigenen Speicherbereich zu reservieren. Verwendet man in mehreren Objekten einen Zeiger auf den gleichen Speicherbereich, dann würde im jeweiligen Destruktor der Operator “delete” hintereinander mehrfach aufgerufen und die Halde damit zerstört.

Als bisher letzte Methode der Klasse “Zeile1" gibt es noch die Ausgabe. Sie beschränkt sich auf die Ausgabe des Textes im Objekt.

Das Hauptprogramm (Bild 5-11) ist sehr knapp geraten. Schließlich können wir (noch) kein umfassendes Programm schreiben. Aber die Grundzüge des Arbeitens mit den Klassen und der dynamischen Speicherverwaltung sind gut zu sehen.

Wie immer beginnt das Programm mit einem Kommentar und dem Einlesen der Informationsdateien. Zuerst wird der Bildschirm gelöscht.

In "main()"” wird ein Objekt “z1" der Klasse ”Zeile" angelegt und mit einem beliebigen Text initialisiert (Zeile 8). Nach dem Löschen des Bildschirms wird das Objekt ausgegeben. Oder: an das Objekt “z1" der Klasse ”Zeile1" wird die Botschaft “print()” ohne Parameter gesendet (Zeile 10).

Diskussion des Beispiels

Im obigen Beispiel haben wir die Anwendung der Klasse mit Hilfe der dynamischen Speicherverwaltung einfach gemacht. Derjenige, der ein Objekt der Klasse anlegt, braucht sich keine Gedanken um mögliche Begrenzungen der Textlänge zu machen. Der Anwender hat es leichter, weil der Spezialist die Verwaltungsarbeit intern erledigt hat.

Die OOP-Sprechweise mit dem Senden von Botschaften beeinflusst die Denkweise. Ruft man ein Unterprogramm auf, hat man das Gefühl, selbst die Steuerung in der Hand zu haben. Sendet man eine Botschaft, überlässt man dem Empfänger die Auswertung und Bearbeitung. Die Aktivität wird logisch in das Objekt hinein verlagert.

In C++ wird das Senden von Botschaften durch den Aufruf von Methoden realisiert. Vielleicht werden einmal in einem komplexeren Computersystem die Objekte auf mehrere Prozessoren verteilt. Dann müßten tatsächlich Botschaften zwischen Prozessoren ausgetauscht werden. Angesichts der fallenden Hardwarepreise und der wachsenden Vernetzung der Maschinen untereinander  ist das gar nicht so abwegig.

Hinweise zur Weiterarbeit

Erweitern Sie das Beispiel “Zeile” wie folgt:

1) Definieren Sie weitere Methoden.

2) Erstellen Sie einen Standardkonstruktor (ohne Parameter).

3) Ergänzen Sie Konstruktor und Destruktor um eine Meldung “Hier ist der Konstruktor” bzw. “Hier ist der Destruktor”. Lassen Sie das Programm ablaufen.

4) Führen Sie einen weiteren Block im Hauptprogramm ein. Legen Sie innerhalb der geschweiften Klammern des neuen Blocks ein lokales Objekt an. Beobachten Sie, wann Destruktoren gerufen werden.

Im nächsten Kapitel

Die Zeile hat uns ein Beispiel für die dynamische Speicherverwaltung geliefert. So einfach das Anlegen der Objekte mit unterschiedlichen Initialisierungen ist, so problematisch sind nun andere Operationen. Die einzige Operation mit ganzen Strukturen oder Objekten, die in der Sprache vordefiniert ist, war die Zuweisung. Was passiert, wenn wir ein Zeilenobjekt einem anderen zuweisen? Bisher wurden einfach die Eigenschaften des Quellobjektes eins zu eins den Eigenschaften des Zielobjektes zugewiesen. Bei der Klasse “ratio” funktionierte das wunderbar. Da eine Eigenschaft der Zeile ein Zeiger auf einen dynamisch angelegten Bereich ist, würde beim Kopieren die Adresse verdoppelt. Für beide Objekte würde aber am Ende der Lebensdauer der Destruktor gerufen. Und damit würde versucht, den gleichen Speicherbereich zweimal freizugeben. Die “normale” Zuweisung funktioniert daher bei Objekten mit dynamischer Speicherverwaltung nicht mehr.

Das gleiche gilt, wenn wir ganze Objekte an Unterprogramme als Parameter übergeben wollen. In den folgenden Kapiteln sehen wir uns daher zuerst den Aufruf und die Übergabe von Parametern genauer an. Mit den dabei gewonnenen Erfahrungen können wir dann auch das Problem der Zuweisung einfach lösen.