| Zeile 1: | Zeile 1: | ||
Die '''Heapverwaltung''' ist ein Teil der [[Speicherverwaltung]], der aufbauend auf der virtuellen Speicherverwaltung Funktionen zur Verwaltung dynamisch allozierten Speichers beliebiger Größe – dieser Speicher zusammengenommen wird dann auch als [[Heap]] bezeichnet – bereitstellt. In der C-Standardbibliothek sind damit die Funktionen malloc/free (und Konsorten) bzw. in der C++-Laufzeitumgebung new/delete gemeint. Gelegentlich werden die beiden Funktionen auch als Bestandteil der virtuellen Speicherverwaltung bezeichnet, da sie ebenfalls mit virtuellen Adressen arbeiten. Sie sind aber nicht mit [[Paging]] – d. h. dem, was in diesem Wiki als [[Speicherverwaltung#Virtuelle Speicherverwaltung | virtuelle Speicherverwaltung]] beschrieben wird – zu verwechseln. | Die '''Heapverwaltung''' ist ein Teil der [[Speicherverwaltung]], der aufbauend auf der virtuellen Speicherverwaltung Funktionen zur Verwaltung dynamisch allozierten Speichers beliebiger Größe – dieser Speicher zusammengenommen wird dann auch als [[Heap]] bezeichnet – bereitstellt. In der C-Standardbibliothek sind damit die Funktionen malloc/free (und Konsorten) bzw. in der C++-Laufzeitumgebung new/delete gemeint. Gelegentlich werden die beiden Funktionen auch als Bestandteil der virtuellen Speicherverwaltung bezeichnet, da sie ebenfalls mit virtuellen Adressen arbeiten. Sie sind aber nicht mit [[Paging]] – d. h. dem, was in diesem Wiki als [[Speicherverwaltung#Virtuelle Speicherverwaltung | virtuelle Speicherverwaltung]] beschrieben wird – zu verwechseln. | ||
| + | |||
== Überblick == | == Überblick == | ||
| Zeile 5: | Zeile 6: | ||
== Freispeicherliste == | == Freispeicherliste == | ||
| − | |||
| − | + | Die einfachste Möglichkeit malloc() und free() zu implementieren ist eine (meist einfach verkettete) Liste aus freien Speicherbereichen zu verwalten. Während malloc() wird dann diese Liste durchlaufen, um nach einem Speicherstück ausreichender Größe zu suchen. Diese Suche kann nach mehreren Strategien erfolgen: | |
| + | * Exact fit: ein Speicherstück das exakt die geforderte Größe hat wird gesucht | ||
| + | * First fit: das erstbeste, ausreichend große Speicherstück wird gesucht | ||
| + | * Best fit: das kleinste, gerade noch ausreichend große Speicherstück wird gesucht | ||
| + | Falls Eines gefunden wird, wird dieses aus der Liste entfernt und einen Zeiger auf den Speicherbereich zurückgegeben, ansonsten wird die virtuelle bzw. physische Speicherverwaltung aufgerufen, um neue Speicherseiten zu allozieren. Um Speicher zu sparen, ist es sinnvoll einen Speicherbereich, falls er viel zu groß - d.h. ein muss noch Platz für eine weitere Header (siehe unten) und zumindest ein bisschen Speicher danach sein - ist, in zwei Teile zu splitten, wobei der erste zurückgegeben wird und der zweite der Freispeicherliste hinzugefügt wird. | ||
| + | |||
| + | Bei einem free() wird der freizugebende Speicherbereich der Liste der freien Speicherbereiche einfach vorne hinzugefügt. | ||
| + | |||
| + | Damit man für die Liste keinen eigenen Speicher allozieren muss, wird beim malloc bewusst einige Bytes mehr Speicher alloziert, um - '''vor''' dem von der anschließend benutzten Speicherbereich (genannt Header) - die Größe und den next-Zeiger (und je nach Bedarf weitere Werte, wie z.B. Flags oder einen previous-Pointer) zu speichern. | ||
| + | |||
| + | ''Beispielimplementierung:'' [https://svn.lcube.de/dev34/pdclib/trunk/functions/stdlib/malloc.c Public-Domain C Library] | ||
| + | |||
| + | == Buddy-Speicherverwaltung == | ||
| + | ''siehe'' [http://de.wikipedia.org/wiki/Buddy-Speicherverwaltung Wikipedia: Buddy-Speicherverwaltung] | ||
== Andere Implementierung portieren == | == Andere Implementierung portieren == | ||