Virtuelle Speicherverwaltung

Die virtuelle Speicherverwaltung ist eine spezielle Speicherverwaltung in einem Computer. Der virtuelle Speicher bezeichnet den vom tatsächlich vorhandenen Arbeitsspeicher unabhängigen Adressraum, der einem Prozess für Daten und das Programm vom Betriebssystem zur Verfügung gestellt wird. Eine virtuelle Adresse beschreibt einen Ort im Speicher eines Computersystems, dessen Betriebssystem eine virtuelle Speicherverwaltung zur Adressierung verwendet. Die Gesamtheit aller virtuellen Adressen wird auch als virtueller Adressraum bezeichnet.

Die Virtuelle Speicherverwaltung sorgt für die effiziente Nutzung vorhandenen Speichers, stellt große, linear zusammenhängende logische Speicherbereiche zur Verfügung und ermöglicht die Implementierung von Speicherschutzmechanismen. Nur die Betriebssysteme, die eine virtuelle Speicherverwaltung verwenden, können einen virtuellen Adressraum generieren und dadurch Speicherseiten, die physikalisch nicht zusammenhängend sind, für den Programmierer bzw. das Programm als logisch zusammenhängenden Speicherbereich abbilden. So stellen viele moderne Betriebssysteme bis zu 4 Gigabyte für Programme und Daten zur Verfügung, auch wenn weniger physikalischer Arbeitsspeicher, z. B. nur 1 Gigabyte, zur Verfügung steht. Die Umsetzung der verwendeten virtuellen Adressen auf die physikalische Adresse wird durch die Memory Management Unit, eine vom Betriebssystem bediente Hardware-Komponente, erreicht. Prozesse können somit Adressen verwenden, die theoretisch auf dem Rechner nicht existieren können.

Der virtuelle Speicher wurde 1956 von Fritz-Rudolf Güntsch erfunden. Er findet heute in beinahe allen modernen Betriebssystemen Verwendung.

Beispiele

AMD64-Architektur: Eine virtuelle Adresse ist 48 Bit lang. Es wird eine vierstufige Seitentabelle verwendet. Die 48 Bit teilen sich auf in je 9 Bit für die vier Seitentabellen plus 12 Bit Offset.
IA32-Architektur: Eine virtuelle Adresse ist 32 Bit lang. Es wird eine zweistufige Seitentabelle verwendet. Die 32 Bit teilen sich auf in je 10 Bit für die zwei Seitentabellen plus 12 Bit Offset.
IA32-Architektur mit PAE: Eine virtuelle Adresse ist 32 Bit lang. Es wird eine dreistufige asymmetrische Seitentabelle verwendet. Die 32 Bit teilen sich auf in 2 Bit für die erste Seitentabelle und je 9 Bit für die zwei weiteren Seitentabellen plus 12 Bit Offset.

Bei der IA-32-Architektur ist der Arbeitsspeicher in Speicherseiten aufgeteilt, deren mögliche Größen und Anfangsadressen durch die Hardware vorgegeben sind. Wird auf eine Adresse zugegriffen, der zur Zeit keine physikalische Speicherseite zugeordnet ist, so muss das Betriebssystem die Memory Management Unit anweisen, an dieser Stelle eine bestimmte freie Speicherseite einzublenden. Steht keine freie Speicherseite mehr zur Verfügung, so muss eine andere Speicherseite frei gemacht werden, wobei der Inhalt vom Betriebssystem z. B. auf die Festplatte ausgelagert wird. Diesen Vorgang bezeichnet man als Paging. Die Größe des virtuellen Adressraums kann aus der Definition der virtuellen Adresse berechnet werden. So ist beispielsweise in einer IA-32-Architektur eine virtuelle Adresse 32 Bit breit, zweimal je 10 Bit für eine zweistufige Seitentabelle und 12 Bit (entspricht den o.g. 4 Kilobyte) für den Offset. Somit lassen sich 2¹⁰ x 2¹⁰ x 2¹² Byte adressieren. Das entspricht 2³² Byte, also 4 Gigabyte.

Funktionsweise

Gemeinsam sind den virtuellen Speicherverwaltungen heutzutage folgende Grundprinzipien:

Alle von Prozessen verwendeten Adressen werden nur noch als virtuelle Adressen behandelt.
Der durch die Gesamtheit aller möglichen virtuellen Adressen definierte virtuelle Adressraum, der den virtuellen Speicher bildet, wird genauso wie der tatsächlich vorhandene physikalische Arbeitsspeicher in gleich große Speicherabschnitte unterteilt. Die für diese Speicherabschnitte verwendeten deutschen Begriffe Kachel, Speicherseite oder Seitenrahmen sind synonym. Im Englischen wird dieser Speicherabschnitt pageframe genannt. Eine Seite (page) des virtuellen Adressraums wird auf eine Kachel (pageframe) des physischen Adressraums abgebildet.
Die Memory Management Unit übersetzt die virtuellen Adressen in reale physikalische Adressen.

Die verschiedenen virtuellen Speicherverwaltungen unterscheiden sich

in der Speichergröße, die eine Speicherseite belegt,
in der Art, wie die Memory Management Unit aus der virtuellen Adresse eine physikalische Adresse berechnet und
in ihrer Seitenersetzungsstrategie, welche die Reaktion auf einen so genannten Seitenfehler, die Adressierung einer nicht im physikalischen Speicher vorhandenen virtuellen Adresse, festlegt.

Aufgrund der Tatsache, dass bei diesem Seitenaustausch immer ganze Speicherseiten (engl.: page) ausgetauscht (engl.: to swap) werden, wird dieser Vorgang der Seitenersetzung auch häufig Paging oder Swapping genannt. Da Swapping aber auch bei der Segmentierung auftritt, sind die Begriffe nicht synonym zu verwenden.

Ein Seitenfehler tritt auf, wenn ein Programm auf einen Speicherbereich zugreift, der sich gerade nicht im Hauptspeicher befindet, sondern beispielsweise auf die Festplatte ausgelagert wurde. Als unmittelbare Folge des Seitenfehlers kommt es zu einer synchronen Programmunterbrechung (engl.: trap). Das Betriebssystem sorgt nun dafür, dass der angeforderte Speicherbereich wieder in den Hauptspeicher geladen wird, damit das Programm darauf zugreifen kann. Ein Seitenfehler ist daher kein Fehler im eigentlichen Sinn. Der Anwender spürt von diesem Vorgang nichts, maximal eine geringe Beeinträchtigung der Geschwindigkeit, da das Laden der Seite einen kurzen Augenblick benötigt.

Eine Seitentabelle ist eine Tabelle, welche der Transformation von virtuellen in physikalische Seitenrahmen dient. Die optimale Seitengröße ist ein Kompromiss zwischen Häufigkeit von Seitenwechsel und Größe der Tabelle.

Platzierungsstrategien

FirstFit: erste ausreichende Lücke
BestFit: kleinste ausreichende Lücke
NextFit: nächster freier Speicher; startet an der Stelle, an der das letzte Programm eingefügt wurde (ringförmiges Durchsuchen)
WorstFit: größte ausreichende Lücke; Restlücke wird zusammengelegt

Seitenersetzungsstrategien

NRU („not recently used“): Teilt Seiten anhand des Use-Bits und Dirty-Bits aus der Seitentabelle in vier Klassen und entfernt zufällig eine aus der untersten, nicht-leeren Klasse.
FIFO („first in, first out“): Jede Seite bekommt Zeitstempel; „älteste raus, hinten rein, vorne raus“
Second-Chance-Algorithmus: Variante von FIFO, die verhindert, dass Seiten ausgelagert werden, die noch häufig benutzt werden.
LFU („least frequently used“): Jede Seite hat ein Feld, das Aufschluss über letzte Nutzung gibt; bei Seitenfehler müssen alle Seiten auf bislang nicht benutzte Zeit durchsucht werden
Working-Set-Algorithmus ersetzt gleich den ganzen Arbeitsbereich (working set) eines Prozesses. Er zählt zu den Prepaging-Strategien, da Seiten geladen werden, noch bevor sie gebraucht werden.
Clock-Algorithmus: Funktionsweise analog zum Second-Chance-Algorithmus. Die Seiten werden in Form einer virtuellen Uhr mit Zeigern abgebildet. Im Verdrängungsfall wird der Uhrzeiger so lange um ein Element weitergeschaltet, bis eine Seite mit einem zurückgesetzten R-Bit gefunden wird. Seiten mit gesetztem R-Bit werden bei der Überquerung des Zeigers zurückgesetzt. Bei großer Anzahl an Hauptspeicherseiten ist dieses Verfahren zu langsam. Daher werden z.B. bei BSD-UNIX zwei Zeiger - mit konstantem Abstand - zur Laufzeitverbesserung verwendet. Der vordere Zeiger setzt das R-Bit im Seitendeskriptor zurück und der hintere prüft das R-Bit und führt bei zurückgesetztem Bit die Verdrängung durch.
Belady-Theorem der optimalen Verdrängung: Hierbei werden die Seiten verdrängt, die in Zukunft am längsten nicht referenziert werden. Nicht umsetzbar, da das Programmverhalten nicht vorhergesagt werden kann.