16.6 Die Freispeicherverwaltung
 
Ohne mich hier zu sehr in die Details der Freispeicherverwaltung zu verstricken, soll dieses Thema kurz behandelt werden. Als Programmierer kann es Ihnen im Prinzip egal sein, wie ein Betriebssystem seinen Speicher reserviert. Aber wenn Sie irgendwann professionelle Programme schreiben, die häufig Speicher vom Heap anfordern, wäre manches Mal ein wenig Hintergrundwissen wünschenswert.
Außer dem Hauptspeicher und dem Festplattenspeicher gibt es noch weitere Möglichkeiten, Daten zu speichern und zu verarbeiten. Es wird dabei von einer Speicherhierarchie gesprochen, die sich in die folgenden sechs Schichten aufteilt:
|
Prozessor-Register |
|
|
First Level Cache der CPU (On-chip Cache, 8–64 kB) |
|
|
Second Level Cache der CPU (128–512 KB) |
|
|
Hauptspeicher (RAM, z.B. 128–512 MB) |
|
|
Sekundärspeicher (Festplatte, 10–120 GB) |
|
|
Tertiärspeicher (Magnetband, 20–160 GB) |
Als C-Programmierer bedienen Sie sich allerdings vorwiegend vom Hauptspeicher. Das Betriebssystem verwendet dabei das so genannte Paging zur Verwaltung des Speichers. Als Paging wird die Unterteilung des virtuellen Speichers in Seiten (pages) und des physischen Speichers in Seitenrahmen (page frames) bezeichnet. Die Größe einer Seite beträgt bei den gängigen Betriebssystemen 512 KB oder 1024 KB. Ein virtuelles Speichersystem ist erforderlich, damit auch mehrere Programme laufen können, die nicht alle in den physischen Speicher (echter vorhandener Speicher, RAM) passen würden. Dafür stellt Ihnen das Betriebssystem eine so genannte Adresskonvention zur Verfügung, womit aus einer virtuellen Adresse wieder eine physische Adresse wird. Denn mit virtuellen Adressen allein könnte kein Programm laufen.
|
Hinweis Jedem Prozess steht ein eigener virtueller Adressraum und darin eine eigene Speicherverwaltung zur Verfügung. Meistens wird hier auch noch das Swapping benutzt. Dabei wird ein Prozess in den Hauptspeicher geladen und läuft eine gewisse Zeit, bis dieser anschließend auf die Festplatte ausgelagert wird. Dieses Swapping findet z.B. statt, wenn nicht mehr genügend Speicherplatz vorhanden ist, um einen Prozess ausführen zu können.
|
In Abschnitt 16.1 haben Sie bereits etwas über den Heap erfahren. Sie wissen, dass der Heap ein zusammenhängender Speicherplatz im Arbeitsspeicher ist, von dem Sie als Programmierer Speicher alloziieren können. Das Betriebssystem verwaltet diesen Speicherbereich als eine Kette von freien Speicherblöcken, welche nach aufsteigenden Speicheradressen sortiert ist. Jeder dieser Blöcke enthält Informationen wie die Gesamtlänge oder den nächsten freien Block. Benötigen Sie jetzt Speicherplatz, durchläuft das Betriebssystem diesen Speicherblock nach verschiedenen Verfahren. Dabei wird von einer prozessinternen Freispeicherverwaltung gesprochen.
16.6.1 Prozessinterne Freispeicherverwaltung
Durch einen Aufruf von malloc() sucht das Betriebssystem jetzt einen zusammenhängenden Speicherblock, welcher den Anforderungen entspricht. Auf der Suche nach diesem Speicherplatz gibt es verschiedene Strategien bzw. Algorithmen, die im Betriebssystem (genauer: im Kernel) implementiert sind.
Als Beispiel dienen freie Speicherbereiche, die folgendermaßen im System angeordnet sind:
Hier klicken, um das Bild zu Vergrößern
Abbildung 16.3
Freie Speicherbereiche im System
Sie fordern jetzt von diesen freien Speicherbereichen mit der Funktion malloc() folgende Speicherblöcke an:
ptr1 = malloc(10);
ptr2 = malloc(12);
ptr3 = malloc(9);
Anhand des freien Speicherbereichs (siehe Abbildung 16.3) und den drei Speicheranforderungen will ich Ihnen die einzelnen Verfahren erklären.
First-Fit-Verfahren
Die Speicherverwaltung durchläuft die Liste der Reihe nach und alloziiert den erstbesten freien Bereich, der groß genug ist. Somit sieht die Speicherbelegung im First-Fit-Verfahren folgendermaßen aus:
Hier klicken, um das Bild zu Vergrößern
Abbildung 16.4
First-Fit-Verfahren
Next-Fit-Verfahren
Next-Fit funktioniert wie First-Fit, nur merkt sich das Next-Fit-Verfahren die aktuelle Position und fährt bei der nächsten Suche nach freiem Speicher von dieser Position aus fort.
Best-Fit-Verfahren
Es wird die gesamte Speicherliste durchsucht, bis ein kleinstmögliches Loch gefunden wird. Mit diesem Verfahren wird eine optimale Speicherausnutzung garantiert.
Hier klicken, um das Bild zu Vergrößern
Abbildung 16.5
Best-Fit-Verfahren
Worst-Fit-Verfahren
Das Gegenteil von Best-Fit; es wird in der Liste nach dem größten verfügbaren freien Bereich gesucht, und dieser wird verwendet.
Hier klicken, um das Bild zu Vergrößern
Abbildung 16.6
Worst-Fit-Verfahren
Quick-Fit-Verfahren
Das Quick-Fit-Verfahren unterhält getrennte Listen für freie Bereiche gebräuchlicher Größe.
Buddy-Verfahren
Das Buddy-Verfahren verwendet für jede Speichergröße eine eigene Liste. Die Zeiger auf die Listenköpfe werden dabei in einem Array zusammengefasst. Bei diesem Verfahren werden nur Blöcke von Zweierpotenzen verwendet (1 Byte, 2 Byte, 4 Byte, 8 Byte, 16 Byte, 32 Byte, 64 Byte, … , 512 Byte, 1 KB, …, 512 KB, 1 MB, …). Wird Speicher angefordert, der nicht diesem Block entspricht, wird ein Block mit der nächsten Zweierpotenz verwendet. Die Blöcke werden außerdem dahin gehend markiert, ob sie zur Anwendung frei sind. Ist bei Speicheranforderung kein gewünschter Block frei, wird ein Block in zwei gleich große Blöcke aufgeteilt.
|
Hinweis Solche Strategien der Freispeicherverwaltung haben natürlich auch ihren Sinn. Vorwiegend dienen solche Verfahren dazu, einen Verschnitt des Speichers zu vermeiden. Das bedeutet, der Speicher wird schlecht ausgenutzt, wenn sehr viele unterschiedliche Stücke verwaltet werden müssen. So kann es passieren, dass einzelne Fragmente des Speichers wahrscheinlich nicht mehr verwendet werden können.
|
|
Ein zweiter Grund für diese Freispeicherverwaltung ist natürlich die Geschwindigkeit. Je schneller wieder auf einen Speicherblock zurückgegriffen werden kann, umso besser.
|
Freigabe von Speicher
Der Speicherplatz, der wieder freigegeben wird, wird nicht an das Betriebssystem zurückgegeben, sondern in die Freispeicherliste eingehängt.
Nach diesem Ausflug, der schon mehr in Richtung Programmierung von Betriebssystemen ging, nun wieder zurück zur Praxis.
|
