Dynamisches Speichermanagement und Heap-Strukturen

Dynamisches Speichermanagement

1 Allgemeine Merkmale

Es wurde eingeführt, um dynamische Strukturen zu verwalten: Listen, Bäume, Graphen usw. Objektorientierte Programmierung macht ausgiebig Gebrauch von diesem Speicher, da jedes Objekt im Heap gespeichert ist.

Die grundlegenden Operationen auf dem Heap sind die *Allokation* (Reservierung) und die *Freigabe* (Deallokation): in C-orientierten Sprachen mittels malloc/free oder in objektorientierten Sprachen mittels new/delete (oder ähnlichen Verfahren). Die Allokations- und Freigabeoperationen werden in einer speziellen Bibliothek durchgeführt, die der Compiler für alle Programme bereitstellt und die für die Verwaltung des dynamischen Speichers verantwortlich ist.

Die Allokation besteht aus der Zuweisung eines Speicherblocks einer bestimmten Größe. Die Freigabe kennzeichnet einen Speicherblock als frei, sodass der Raum für neue Allokationen wiederverwendet werden kann. Die Heap-Verwaltung erfordert geeignete Techniken, um die Fläche zu optimieren und die Ausführungszeit der Allokations- und Freigabeoperationen zu minimieren.

2 Blöcke fester Länge

Der Heap wird hier als eine verkettete Liste von Blöcken gleicher Größe verwaltet. Es wird nur der Zeiger auf den ersten freien Block gespeichert. Die Allokation erfolgt durch Zuweisung des ersten freien Blocks. Die Freigabe erfolgt, indem der freigegebene Block wieder als erster Block in die Liste eingefügt wird.

3 Heap mit variabler Struktur (Blöcke unterschiedlicher Größe)

Der Heap wird als eine verkettete Liste von Blöcken unterschiedlicher Größe verwaltet. Es wird nur der Zeiger auf den ersten Block gespeichert. Die Struktur eines jeden Blocks ist:

Allokationsstrategien (Reservierung):

• Strategie des ersten passenden Blocks (First Fit): Durchsuchen der Liste, bis ein Block gefunden wird, der größer oder gleich dem angeforderten Speicher ist. Der Block wird in zwei Teile geteilt: Der erste Teil wird als reservierter Speicher zurückgegeben, und der zweite Teil wird als neuer Block geringerer Größe gespeichert.
• Strategie des besten passenden Blocks (Best Fit): Durchsuchen der Liste, um den Block zu finden, dessen Größe dem angeforderten Speicher am nächsten kommt. Diese Strategie erzeugt eine starke Fragmentierung und wird daher selten genutzt.
• Strategie des schlechtesten passenden Blocks (Worst Fit): Es wird immer der größte verfügbare Block zugewiesen. Das Problem ist, dass dadurch gerade die großen Blöcke eliminiert werden, die für sehr große Objekte benötigt werden.

Freigabestrategien (Deallokation):

Einfache Freigabe: Weisen Sie den Block zu und setzen Sie ihn an den Anfang der Liste. Dies führt dazu, dass lange Blöcke schnell aufgeteilt werden, erschwert jedoch die Zusammenführung (Fusion) benachbarter Blöcke.

Freigabe mit Fusion: Eine Liste von Speicherblöcken wird sortiert gehalten (z. B. nach Adresse). Dies erfordert das Einfügen des freigegebenen Blocks an der korrekten Position (was langsamer ist), ermöglicht aber die schnelle Zusammenführung (Fusion) benachbarter Blöcke.