14.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 sogenannte 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 sogenannte Adresskonvention zur Verfügung, mit der 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 er 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 14.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 allozieren können. Das Betriebssystem verwaltet diesen Speicherbereich als eine Kette von freien Speicherblöcken, die 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.
14.6.1 Prozessinterne Freispeicherverwaltung
Durch einen Aufruf von malloc() sucht das Betriebssystem jetzt einen zusammenhängenden Speicherblock, der 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 so im System angeordnet sind, wie Sie es in Abbildung 14.3 sehen.
Abbildung 14.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 14.3) und den drei Speicheranforderungen will ich Ihnen die einzelnen Verfahren erklären.
First-Fit-Verfahren
Beim First-Fit-Verfahren durchläuft die Speicherverwaltung die Liste der Reihe nach und alloziert den erstbesten freien Bereich, der groß genug ist. Somit sieht die Speicherbelegung im First-Fit-Verfahren so aus wie in Abbildung 14.4 gezeigt.
Abbildung 14.4 First-Fit-Verfahren
Next-Fit-Verfahren
Das Next-Fit-Verfahren 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
Beim Best-Fit-Verfahren wird die gesamte Speicherliste durchsucht, bis ein kleinstmögliches Loch gefunden wird. Mit diesem Verfahren wird eine optimale Speicherausnutzung garantiert.
Abbildung 14.5 Best-Fit-Verfahren
Worst-Fit-Verfahren
Das Worst-Fit-Verfahren ist das Gegenteil von Best-Fit. Dabei wird in der Liste nach dem größten verfügbaren freien Bereich gesucht, und dieser wird verwendet.
Abbildung 14.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 dahingehend 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, dass der Speicher schlecht ausgenutzt wird, 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 die Freispeicherverwaltung ist natürlich die Geschwindigkeit. Je schneller wieder auf einen Speicherblock zurückgegriffen werden kann, umso besser ist es. |
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 kehren wir wieder zur Praxis zurück.
Ihre Meinung
Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de.