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.

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.

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.