Virtueller Speicher

Beim virtuellen oder logischen Speicher handelt es sich um eine Abbildung des begrenzten Adressraums des Arbeitsspeichers auf einen linearen, nahezu unbegrenzten Adressraum. Als Adressraum bezeichnet man die Anzahl der verschiedenen Adressen, die ein Prozessor oder ein Programm maximal verwalten kann. Jedem Programm steht ein eigener virtueller Adressraum zur Verfügung. Das hat zwei Vorteile:

• Es kann mehr Arbeitsspeicher genutzt werden, als tatsächlich vorhanden ist.
• Beim Zugriff auf eine virtuelle Speicheradresse muss nicht darauf geachtet werden, ob diese bereits von einem anderen Programm verwendet wird oder überhaupt im physischen Speicher existiert.

Logische Adresse

Jede Seite im virtuellen Speicher hat eine logische Adresse, die sich aus der Seitennummer und einem Offset zusammensetzt. Über das Offset lässt sich jedes einzelne Byte innerhalb einer Seite auswählen. Je größer eine Seite ist, desto mehr Bits der Adresse müssen für das Offset reserviert werden.

Physische Adresse

Um das zugehörige Byte auch im Arbeitsspeicher finden zu können, wird die physische Adresse benötigt. Die physische Adresse ergibt sich aus der Addition der Rahmennummer (Startadresse des Seitenrahmens) mit dem Offset.

Speicherverwaltungseinheit (MMU)

Moderne CPUs besitzen eine eigene Speicherverwaltungseinheit oder MMU (Memory Management Unit).
Die wichtigsten Aufgaben:

• Umrechnung logischer Adressen auf physische Speicheradressen, mittlerweile wird diese Aufgabe von speziellen ALUs, den sogenannten Address Generation Units (AGUs) übernommen.

• Zuteilung von Arbeitsspeicher an die einzelnen Prozesse

• Segmentierung und Paging: Die Einteilung des Speichers in voneinander unabhängige Speicherbereiche ist Voraussetzung für die gleichzeitige Ausführung mehrerer Prozesse*, wobei die dem Paging vorgelagerte Segmentierung heutzutage nicht mehr eingesetzt wird.

• Swapping: Wenn im Arbeitsspeicher kein Platz mehr ist, führt die MMU die Auslagerung einzelner Prozesse auf Festplatte durch. Swapping ist ebenfalls veraltet.

• Paging: Anders als beim Swapping werden nicht komplette Prozesse ausgelagert, sondern nur einzelne, gleich große Seiten. Diese sind zwar einem bestimmten Prozess zugeordnet, müssen aber nicht hintereinander im Speicher abgelegt werden.

• Speicherschutz: Speicherbereiche, die einem bestimmten Prozess zugeordnet sind, können vor dem Zugriff durch andere Prozesse geschützt werden. Meistens werden Daten und Befehle in unterschiedlichen Seiten gespeichert, wobei Seiten mit Programmbefehlen mit „Nur Lesen“ (Read-Only) gekennzeichnet werden. So können Befehle von mehreren Prozessen ohne das Risiko einer Manipulation gemeinsam verwendet werden.

*Als Prozess bezeichnet man ein im Arbeitsspeicher abgelegtes Programm.

Adresse umrechnen

Um eine virtuelle Adresse in eine physische Adresse umrechnen zu können, werden zusätzlich folgende Informationen benötigt:

• Seitengröße n in Byte, z.B. 4.096 Byte (entspricht 4 KiB)
• Adressbreite der CPU, z.B. 16 Bit

Zuerst muss ermittelt werden, wie viele höherwertige Bits den Seitenindex bilden:

1. Länge des Offset berechnen: Log2(n) = Log2(4.096) = 12
2. Länge des Seitenindex berechnen:  Adressbreite – Offset = 16 – 12 = 4, d.h. einem Prozess stehen 2^4 = 16 Seiten zur Verfügung

Bei einem Prozessor mit 32 Adressleitungen (32 Bit) und einer Seitengröße von 4 KiB besteht die logische Adresse aus einer 20 Bit Seitennummer. Es können also 2^20 = 1.048.576 Seiten verwaltet werden.
Danach muss der Seitenindex zum Nachschlagen in der Seitentabelle ermittelt werden. Beispiel anhand der virtuellen Adresse EF92h:

1. Zur leichteren Berechnung sollte man den Hexadezimal- in einen Binärwert umwandeln (s. Hexadezimalsystem):
   1110 1111 1001 0010
2. Die 4 höherwertigen Bits sind der Seitenindex: 1110 = 14

Seitentabelle (Beispiel)

Um die physische Adresse zu erhalten, werden nachgeschlagene Rahmenadresse und Offset wieder zusammengesetzt:

1. Der entsprechende Eintrag verweist auf Seitenrahmen 7, das entspricht dem Binärwert 0111.
2. Binärwert wieder in Hex-Wert umwandeln: 0111 1111 1001 0011 = 7F92h

Seitentabelle

In der Seitentabelle gibt es zu jeder Seite einen eigenen Eintrag (PTE = Page Table Entry), der den Seitenindex, die Nummer des zugehörigen Seitenrahmens und Informationen über den Status der Seite enthält. Die wichtigsten Statusbits:

• Das Valid-Bit (V-Bit) gibt an, ob die Seite überhaupt noch im Speicher vorhanden ist. Wenn der Eintrag ungültig ist (Valid = 0), wird ein Seitenfehler (engl. page fault) ausgelöst.
• Das Modified-Bit (M-Bit) ist nützlich bei ausgelagerten Seiten. Es gibt an, ob der Inhalt der Seite durch einen Prozess verändert wurde. Wenn das M-Bit auf 1 (geändert) steht, ist die Seite im Speicher nicht mehr mit der Kopie auf der Festplatte identisch. Dann muss die entsprechende Seite erst auf die Festplatte zurückgeschrieben werden.
• Das Referenced-Bit (R-Bit) gibt an, ob innerhalb eines bestimmten Zeitraums ein Zugriff auf die Seite erfolgte und ist damit ein wichtiges Auslagerungskriterium.
• Das Schutzbit gibt an, ob die Seite gelesen und beschrieben oder nur gelesen werden darf.

Für jedes im Speicher befindliche Programm (Prozess) wird eine eigene Seitentabelle erzeugt. Die Startadresse der gerade aktiven Seitentabelle im Arbeitsspeicher wird in einem speziellen Register, dem PTBR (Page Table Base Register) abgelegt. Das Betriebssystem kann auf diese Weise schnell zwischen verschiedenen Seitentabellen wechseln, indem es die Adresse der gewünschten Tabelle in das PTBR lädt.

Probleme: Extremer Speicherbedarf und hohe Zugriffszeiten

 Je mehr Seiten eine CPU ansprechen kann, desto größer ist die Seitentabelle. Mit zunehmender Größe steigen sowohl Zugriffszeiten als auch Speicherbedarf. Bei einer 32-Bit-CPU (s. Bespiel oben) ist eine entsprechende Seitentabelle 4 MiB groß (1.048.576 Seiten x 4 Byte pro Eintrag). In diesem Fall ist der Speicherbedarf noch uberschaubar. Aktuelle 64-Bit-CPUs können allerdings bis zu 2^52 (64 Bit – 12 Bit Offset) Seiten adressieren, das entspräche etwa 4,5 Billiarden Einträgen. Der Speicherbedarf für nur eine Seitentabelle wäre mit etwa 18.000 Terabytes gigantisch! Selbst wenn man einen solch gewaltigen Speicher hätte, den richtigen Eintrag zu finden würde ewig dauern. Welche Möglichkeiten gibt es, den Speicherbedarf für Seitentabellen zu verringern?

 Die naheliegendste Lösung wäre es, die Anzahl der Seiten bzw. der zu durchsuchenden Einträge zu verringern und dafür die Größe der einzelnen Seiten zu erhöhen. Bei einer Seitengröße von 1.024 MiB müssten „nur“ noch 2^34 (64 Bit – 30 Bit Offset), also 17,1 Milliarden Einträge verwaltet werden. Der Speicherbedarf wäre dann mit 68,4 GB allerdings immer noch zu hoch. Außerdem wird sehr viel Speicherplatz verschenkt, da die Seiten für viele Prozesse zu groß wären. Beispiel. Wenn ein Prozess nur etwa 1 MiB insgesamt benötigt, dann wäre eine Seitengröße ideal, die kleiner als 1.024 KiB ist und sich durch ein Vielfaches von 2 teilen lässt, z.B. 1024/4 = 256 KiB, 1024/8 = 128 KiB). Bei 128 KiB würde es im RAM genau 8 Seiten belegen, es würde kaum Speicher verschwendet. Würde man die Seitengröße auf 4.096 KiB erhöhen, würde das Programm eine ganze Seite belegen und 75% des zugewiesenen Speichers ungenutzt lassen.
Eine wesentlich effektivere Lösung zur Verringerung des Speicherplatzbedarfs ist der Einsatz einer mehrstufigen Seitentabelle.

Mehrstufige Seitentabelle

Eine mehrstufige Seitentabelle besteht aus mehreren hierarchisch angeordneten Seitentabellen. Der Einträge der übergeordneten Tabelle verweisen dabei jeweils auf die Tabelle der nächsten Stufe. Meistens wird die Tabelle der ersten Stufe als Seitenverzeichnis (page directory) benutzt, in dem Verweise auf die Seitentabellen der zweiten Stufe gespeichert werden. Erst die Tabelle der letzten Stufe enthält den Eintrag mit der Nummer des entsprechenden Seitenrahmens. Über die logische Adresse kann der entsprechende Eintrag aus einer Tabelle ausgewählt werden. Dazu wird der Seitenindex in n Segmente unterteilt, wobei n für die Anzahl der Stufen steht.
Beispiel: Bei 32-Bit-CPUs mit x86-Architektur wird eine zweistufige Seitentabelle eingesetzt. Die logische Adresse ist wie folgt aufgebaut:

• Verzeichnisindex: Verweist auf eine der 1.024 (2^10 = 1.024) Seitentabellen
• Seitenindex: Wählt einen Eintrag in der entsprechenden Tabelle aus. Eine Seitentabelle hat 1.024 je 4 Byte große Einträge.

Dieses Beispiel zeigt bereits die Vorteile einer mehrstufigen Seitentabelle gegenüber einer einstufigen Seitentabelle:

• Der Speicherbedarf ist um ein Vielfaches geringer: Statt 4 MiB (1.048.576 x 4 Byte) benötigt eine Seitentabelle nur 4 KiB (1.024 x 4 Byte). Dadurch wird es möglich, nicht benötigte Seitentabellen auf Festplatte auszulagern.
• Die Zugriffszeit ist kürzer, da nicht so viele Einträge durchsucht werden müssen. Allerdings steigt sie mit jeder weiteren Stufe wieder an, da für jede Tabelle ein Speicherzugriff nötig ist.

Physical Address Extension (PAE)

Die physische Adresserweiterung wurde mit dem Pentium-Pro- (Intel) bzw. dem Athlon-Prozessor (AMD) eingeführt, vor allem um die Beschränkung des physischen Adressraums auf 4 GiB aufzuheben. Dazu wurde die Anzahl der Adressleitungen von 32 auf 36 erhöht. Mit 36 Bit langen physischen Adressen lassen sich theoretisch bis zu 64 GiB Speicher (2^36) ansprechen. Die logische Adresse ist weiterhin 32 Bit breit, da PAE aber eine dreistufige Seitentabelle nutzt, ist die logische Adresse in drei Segmente + Offset aufgeteilt:

• Verzeichniszeiger: Die Tabelle der ersten Ebene (PDPT Page Directory Pointer Page) enthält im Grunde nur Verweise auf die 4 Seitenverzeichnisse
• Verzeichnisindex: Verweist auf eine der 512 (2^9) Seitentabellen
• Seitenindex: Wählt einen Eintrag in der entsprechenden Tabelle aus. Eine Seitentabelle hat 512 je 8 Byte große Einträge.

Die Größe der Einträge wurde verdoppelt, um mehr Bits für die Adresse unterbringen zu können. Da die Seitentabellen aber trotzdem nicht größer sein sollten als 4 KiB, musste die Anzahl der Einträge entsprechend halbiert werden. Dafür stehen nun 40 statt 20 Bit allein für den Seitenindex zur Verfügung, zusammen mit dem 12 Bit Offset ergibt das einen (theoretischen) Adressraum von 2^52 = 4,5 Petabytes. PAE unterstützt auch einen 64-Bit-Modus („Long Mode“) mit vierstufiger Seitentabelle. Die Adresse ist hier 64 Bit breit, davon werden 48 Bit zur Adressierung der Seiten verwendet.

TLB (Translation Lookaside Buffer)

Bei mehrstufigen Seitentabellen müssen mehrere Seitentabellen aus dem Arbeitsspeicher geladen werden, um den Eintrag mit dem entsprechenden Seitenrahmen zu erhalten. Da dieses Verfahren sehr zeitaufwändig ist, werden die zuletzt am häufigsten abgerufenen Einträge in einem speziellen Cache abgelegt, der als TLB (Translation Lookaside Buffer) bezeichnet wird.

Paging

Als Paging bezeichnet man auch das zeitweilige Auslagern von Seiten auf Festplatte. Es wird beim Auftreten eines sogenannten Seitenfehlers (page fault) ausgelöst, also wenn sich die von der logischen Adresse angesprochene Seite nicht mehr im Speicher befindet (Valid-Bit ist auf 0 gesetzt). In diesem Fall wird zuerst der entsprechende Prozess angehalten. Dann wird überprüft, ob noch eine freier Seitenrahmen für die Seite vorhanden ist. Wenn kein Platz mehr ist, wird ein bereits belegter Seitenrahmen ausgewählt und dessen Inhalt auf die Festplatte verschoben. Welche Seite als Erstes ausgelagert und ersetzt wird, entscheidet die Seitenersetzungsstrategie. Im Anschluss daran werden die adressierten Daten auf der Festplatte gesucht und in den Seitenrahmen übertragen. Zuletzt wird der entsprechende Eintrag in der Seitentabelle aktualisiert und der Prozess fortgesetzt.

Seitenersetzungsstrategien

In der Zeitspanne, die ein Schreib-/Lesezugriff auf die Festplatte benötigt, können etwa 100.000 Zugriffe auf den Arbeitsspeicher bewältigt werden. Deshalb sollte ein optimaler Algorithmus die Anzahl der Ein-/Auslagerungsvorgänge minieren, indem er immer die Seite als Kandidat für eine Auslagerung auswählt, auf die am längsten kein Zugriff mehr erfolgte. Gleichzeitig sollte der Algorithmus aber auch schnell und nicht zu komplex sein. In der Praxis ist es deshalb schwierig, den optimalen Algorithmus zu finden. Das einfachste Verfahren beruht auf einer vom Betriebssystem verwalteten Liste, in der alle in den Speicher geladenen Seiten nach dem FIFO-Prinzip vermerkt werden: Die älteren, zuerst geladenen Seiten stehen weiter oben, die neueren, zuletzt geladenen Seite befinden sich weiter unten. Es wird immer die Seite ausgelagert, die ganz oben in der Liste steht. Der Algorithmus verdrängt allerdings auch ältere Seiten, die häufig benutzt werden. In dieser Hinsicht kommt der LRU-Algorithmus dem optimalen Algorithmus am nächsten.

LRU (Least Recently Used)

• Prinzip: Es wird die Seite ausgelagert, auf die in letzter Zeit am wenigsten zugegriffen wurde.
• Umsetzung: Zu jedem Eintrag in der Liste wird ein Zähler gespeichert, der bei einem Zugriff auf die Seite um 1 erhöht wird. Die Liste wird bei jeder Änderung neu sortiert, so dass Seiten mit niedrigem Zählerstand immer weiter oben und Seiten mit hohem Zählerstand weiter unten stehen. Es wird die Seite mit dem niedrigsten Zählerstand als „Opfer“ ausgewählt.
• Nachteil: Die Liste muss ständig aktualisiert werden.

Second Chance („Zweite Chance“)

• Prinzip: Es wird die Seite ausgelagert, die zuerst geladen wurde und auf die am längsten kein Zugriff erfolgte.
• Umsetzung: In der FIFO-Liste wird noch zusätzlich das R-Bit gespeichert, das angibt, ob die Seite zuletzt verwendet wurde. Wenn das R-Bit gesetzt ist (R = 1) ist, wandert der Eintrag in der Liste ganz ans Ende und das R-Bit wird gelöscht. Dadurch bleiben auch ältere, häufig genutzte Seiten länger im Speicher.
• Nachteil: Die Listeneinträge müssen oft verschoben werden.

Clock (Uhr)

• Prinzip: s. „Second Chance“
• Umsetzung: Statt eines Stapels wird eine ringförmige Liste von Seitenrahmen verwendet. Die Einträge sind wie beim Zifferblatt einer Uhr um einen Zeiger herum angeordnet. Der Zeiger startet auf dem ältesten Eintrag. Stößt der Zeiger auf einen Eintrag, bei dem das R-Bit nicht gesetzt ist (R = 0), wird die entsprechende Seite ausgelagert und in der Liste durch eine neue Seite ersetzt, ansonsten wird dieses einfach gelöscht und der Zeiger wandert weiter zum nächsten Eintrag.

Ein Problem tritt bei diesen Algorithmen auf, wenn im Arbeitsspeicher kein Platz mehr ist und sich bereits sehr viele Prozesse darin befinden. Dadurch sinkt bei jeder weiteren Anforderung die Anzahl an Seitenrahmen, die pro Prozess zur Verfügung stehen. Es kommt dann häufiger vor, dass sich mehrere Prozesse einen Seitenrahmen streitig machen, wodurch die betroffenen Seiten oft ein- und ausgelagert werden. Man bezeichnet dieses Verhalten auch als Thrashing oder Seitenflattern.

Working-Set-Algorithmus

Beim WS-Algorithmus wird für jeden Prozess ein sogenannter Arbeitsbereich bestimmt, um Seitenflattern zu minimieren. Als Arbeitsbereich oder Working-Set (WS) bezeichnet man die Seiten, auf die ein Prozess innerhalb eines vom Betriebssystem festgelegten Zeitraums (Δ) zugreift. Diese dürfen nicht ausgelagert werden, weshalb der Prozess erst gestartet wird, wenn der „Arbeitsbereich“ geladen wurde.

Prinzip: Es wird die Seite ausgewählt, die nicht zum aktuellen Prozess gehört.

Umsetzung: In der Seitentabelle wird nicht nur der Zeitpunkt des letzten Zugriffs gespeichert, sondern auch, ob innerhalb des Zeitfensters ein Zugriff erfolgte (R-Bit gesetzt). Anhand des letzten Zugriffs wird zusätzlich das Alter der Seite ermittelt (Alter = Laufzeit – Letzter Zugriff). Ob eine Seite im Arbeitsbereich liegt, lässt sich nun durch einen Vergleich des Alters der Seite mit dem Zeitfenster Δ feststellen. Wenn das Alter größer als Δ ist, liegt die Seite außerhalb des Arbeitsbereichs. Der Algorithmus arbeitet die Einträge der Seitentabelle nach folgenden Regeln ab:

• Wenn R gesetzt ist (R = 1), dann überschreibe „Letzter Zugriff“ mit der aktuellen Systemzeit.
• Wenn R nicht gesetzt ist…
  • …und die Seite außerhalb des Arbeitsbereichs liegt, dann lagere die Seite aus.
  • …und alle Seiten im WS liegen, dann lagere die älteste Seite aus.

Nachteil: Da bei jedem Seitenfehler die komplette Seitentabelle durchsucht werden muss, ist der Algorithmus sehr langsam.

WSClock-Algorithmus

Der WSClock-Algorithmus stellt eine vereinfachte und schnellere Version des WS-Verfahrens dar. Statt der Seitentabelle wird wie beim Clock-Algorithmus eine ringförmige Liste mit Zeiger verwendet, der beim ältesten Eintrag startet. Wenn das R-Bit gesetzt ist, wird es gelöscht und die Zeit aktualisiert, bevor der Zeiger zum nächsten Eintrag weiterwandert. Wenn R nicht gesetzt ist und die Seite nicht im Arbeitsbereich liegt, dann hängt das weitere Vorgehen vom M-Bit ab: Falls die Seite nicht geändert wurde (M-Bit = 0), wird sie sofort ausgelagert und in der Liste durch eine neue Seite ersetzt. Anderenfalls wird die Seite vorgemerkt und beim nächsten Mal ausgelagert. Wenn keine Seite vorgemerkt wurde, entscheidet ein Zufallsgenerator.