Betriebssystemtheorie/ Speicherverwaltung

Adressräume

Ein Adressraum ist eine Menge von Elementen, wobei jedem Element ein Name ein-eindeutig zugeordnet ist.

Um dieser reichlich abstrakten Definition etwas Leben einzuhauchen, betrachten wir den im Computer eingebauten Arbeitsspeicher. Das grundlegende Element des Arbeitsspeichers ist das Byte, der Arbeitsspeicher ist eine Menge von Bytes. Jedem Byte wird eine Nummer als Name zugeordnet durch welche es von der CPU, oder einem anderen Gerät, benannt werden. Man sagt, es wird adressiert. Das erste Byte erhält die Adresse 0, das n-te Byte die Adresse n-1. Da der Speicher dieses Adressraums physisch im Rechner vorhanden ist, spricht man vom physischem Adressraum.

Die physischen Speicheradressräume in heutigen Rechnern sind linear. Es gibt in jedem Gerät einen physischen Adressraum, welcher bei 0 beginnt, bis n-1¹ läuft und keine Löcher oder undefinierten Stellen enthält.

1: n bezeichnet hier die Gesamtgröße des physischen Speichers

Virtueller Speicher

Der Ausdruck virtueller Speicher beschreibt ein Konzept, bei dem für jeden Prozess ein eigener Speicheradressraum konstruiert wird. Dieser virtuelle Adressraum wird auf den physischen Adressraum abgebildet.

Ohne virtuelle Adressräume könnte man immer nur einen Prozess zu einem Zeitpunkt starten. Beim Ausführen eines zweiten Prozesses würden beide Prozesse sich mit hoher Wahrscheinlichkeit gegenseitig stören und abstürzen.

Deshalb wird jeder Prozess in einem virtuellen Adressraum ausgeführt. Dieser hat die selben Eigenschaften wie der physische Adressraum. Er ist linear, beginnt bei 0 und reicht bis N-1².

Zusätzlich benötigt man für jeden Prozess noch eine Funktion y = f(x) welche für jede Adresse im virtuellen Speicher die zugehörige Adresse im physischen Speicher zurückliefert. Die Abbildung f(x) ist keine mathematische Funktion, sondern wird von einem Hardwaregerät bereitgestellt.

Ein exemplarischer Speicherzugriff läuft folgendermaßen ab:

Prozess P möchte einen Speicherwert in das CPU-Register R1 laden
P legt die virtuelle Adresse x des Wertes auf den Adressbus
Am Adressbus befindet sich ein Gerät, welches die virtuelle Adresse in eine physische Adresse übersetzt
Das Gerät erkennt x an seinem Eingang und führt die y = f(x) aus
Die physische Adresse y wird an den Ausgang des Geräts geschrieben
Der Speicherkontroller erkennt y an seinem Eingang und schreibt den gewünschten Wert des physischen Speichers auf den Speicherbus
P empfängt den Wert und schreibt ihn in das Register R1

2: N bezeichnet hier die Gesamtgröße des virtuellen Speichers

Paging

Da es unpraktisch oder unmöglich ist, die Funktion f(x) für jede Speicheradresse zu definieren, wird der gesamte virtuelle Adressraum eines Prozesses in sogenannte Seitenrahmen unterteilt, man sagt, er wird partitioniert. Jeder Seitenrahmen bezeichnet einen zusammenhängenden Bereich des Arbeitsspeichers.

Alle Seitenrahmen haben die gleiche Größe, welche von der zugrunde liegenden Hardware vorgegeben ist und eine Potenz von 2 ist. Beispielsweise ist auf der IA32-Architektur eine Speicherseite 2¹² = 4096 Byte oder 2²² = 4194304 Byte groß. Die erste Speicherseite eines Adressraumes liegt an der Adresse 0. Jede weitere folgt nach jeweils 2ⁿ Byte.

Eine Adresse eines partitionierten Adressraums läßt sich in zwei Teile unterteilen. Die n niederwertigsten Bits (0 bis n-1) dienen zur Lokalisierung eines Byte innerhalb einer Speicherseite. Die restlichen höherwertigen Bits geben die Nummer des Seitenrahmens und ihre Position im virtuellen Adressraum an.

Diese Partitionierung wird für den physischen Speicheradressraum und für jeden virtuellen Speicheradressraum durchgeführt. Zur besseren Übersicht welcher Adressraum gemeint ist, gelten für den Rest des Buches die folgenden Regeln:

Seitenrahmen: Bezeichnet eine Partition im virtuellen Adressraum

Kachel: Bezeichnet eine Partition im physischen Adressraum

Speicherseite: Bezeichnet den Inhalt einer Kachel oder eines Seitenrahmens

Diese Definitionen werden dem einen oder anderen Leser jetzt überkorrekt oder sogar unnütz vorkommen. Für das Verständnis der folgenden Kapitel sind sie aber unerlässlich.

Hardwareunterstützung

Die Implementierung von virtuellen Adressräumen benötigt Unterstützung durch die Hardware. Die 3 verbreitetsten Konzepte werden im folgenden vorgestellt.

Segmentierung

Eine sehr einfache Methode zur Speicheraufteilung ist die Segmentierung. Der physische Arbeitsspeicher wird dazu in kleinere Teile zerlegt, sogenannte Segmente. Die CPU enthält 2 Register, welche ein Segment definieren.

OFFSET: Der Wert im OFFSET-Register zeigt den Beginn eines Segments und wird zu jeder virtuellen Speicheradresse hinzuaddiert. Enthält OFFSET beispielsweise den Wert 0x1000 (Byte 4096), wird die virtuelle Adresse 0 auf 4096+0 abgebildet, die virtuelle Adresse 1 auf 4096+1, usw.

SIZE: Der Wert im SIZE-Register gibt die Gesamtgröße des Segmentes an. Durch die Begrenzung der Segmente nach oben, wird es möglich, mehrere Segmente hintereinander im physischen Adressraum anzulegen, ohne dass diese sich überlappen. Ruft ein Prozess eine virtuelle Adresse auf, deren Wert größer als der Wert in SIZE ist, erzeugt die CPU eine Ausnahme vom Typ SEGFAULT (Segmentation fault), welche vom Betriebssystemkern behandelt werden muss.

Befindet sich die CPU im Kernmodus, d.h. der Betriebssystemkern wird ausgeführt, wird keine Segmentierung durchgeführt. Der Kern kann den gesamten Arbeitsspeicher sehen und nutzen. Beim Anlegen eines neuen Prozesse sucht der Kern einen Bereich des Speichers, welcher noch von keinem Segment genutzt wird. Die niedrigste Adresse und die Größe des Bereiches definieren ein neues Segment. Beide Werte werden für den zu erzeugenden Prozess gespeichert. Wird ein Thread des Prozesses ausgeführt, lädt der Kern die Segment-Werte in ihre entsprechenden Register. Beim Umschalten in den Benutzermodus wird die Segmentierung aktiviert.

Segmentierung ist sehr einfach zu bauen, hat aber leider einige Probleme:

Durch die Abgrenzung der Segmente ist es fast unmöglich, dass zwei Prozesse auf die gleiche physische Adresse zugreifen. Dies geht nur, falls die Segmente der beiden Prozesse im Speicher direkt nebeneinander liegen und das untere Segment in das obere hineinreicht. Diese Einschränkung macht die IPC zwischen beliebigen Prozessen sehr langsam, da alle Daten durch den Kern vom Quellsegment zum Zielsegment kopiert werden müssen.
Es kann sehr aufwendig sein, den virtuellen Adressraum eines Prozessen bei Bedarf zu vergrößern. Wird ein Segment nach oben hin durch ein anderes begrenzt, kann der Wert im Register SIZE nicht einfach erhöht werden, da die Segmente sonst überlappen würden. Der Kern muss zuerst Segmente umsortieren, bis sich genügend freier Speicher an das zu vergrößernde Segment anschließt.

Bei vielen x86-Architekturen ist Segmentierung heute aus Gründen der Kompatibilität noch vorhanden. Auf Grund der genannten Probleme wird sie aber nicht genutzt und hat keinerlei Bedeutung mehr.

Memory Management Units

Ein flexibleres Konzept als Segmentierung ist die Verwendung einer Memory Management Unit (MMU). Die MMU ist ein Hardwaregerät, das sich am Adressbus zwischen CPU und Speicher befindet und virtuelle Adressen in physische Adressen übersetzt.

Jedem Prozess im System ist eine Übersetzungstabelle zugeordnet, die sogenannte Seitentabelle. Diese bildet die Speicherrahmen des virtuellen Adressraums auf die Kacheln des physischen Adressraums ab. Der Vorteil gegenüber der Segmentierung ist hierbei, dass die Zuordnung völlig wahlfrei ist. Im folgenden einige Beispiele:

Der Seitenrahmen kann die Speicherseite in einer beliebigen Kachel enthalten.
Zwei Seitenrahmen können die selbe Kachel referenzieren.
Ein Seitenrahmen kann leer sein.

Die Seitentabelle enthält für jeden Seitenrahmen eines virtuellen Adressraums die zugeordnete Kachel. Hat eine Architektur einen Adressbus der Breite M und Seitengröße von 2^N Byte, gelten folgende Regeln:

Es gibt M-N Seitenrahmen und maximal M-N Kacheln
Eine vollständige Seitentabelle enthält 2^M-N Einträge

Die Seitennummer eines Seitenrahmens gibt den Index seines Eintrages in der Seitentabelle. Ein Eintrag besteht aus folgenden Teilen:

Die obersten M-N Bits geben den Index der Kachel an, die von diesem Seitenrahmen referenziert wird.
Die unteren N Bits enthalten zusätzliche Zustandsbits:
- Read-only (RO) löst eine Exception aus, beim Versuch, auf die Speicherseite zu schreiben.
- No-Execute (NX) löst eine Exception aus, falls der Inhalt der Speicherseite ausgeführt werden soll.
- Copy-On-Write (COW) signalisiert dem Betriebssystem, die Seite zu duplizieren, falls sie geschrieben werden soll. Meist wird es mit dem RO-Bit verwendet, welches die benönigte Exception auslöst.

Translation Lookaside Buffers

Genau wie eine MMU ist ein Translation Lookaside Buffer (TLB) ein Hardwaregerät, das virtuelle Adressen in physische Adressen übersetzt. Es befindet sich am Adressbus der CPU und wird vom Kern während der Prozessumschaltung programmiert.

Im Gegensatz zur MMU enthält ein TLB allerdings keine vollständige Seitentabelle, sondern nur ausgewählte Einträge. Welche das sind wird vom Betriebssystem festgelegt.

Die Übersetzung zwischen den Adressräumen funktioniert genau wie in einer MMU. Wird ein Speicherzugriff ausgeführt und der benötigte Eintrag befindet sich im TLB, funktioniert die Translation unbemerkt. Ist der benötigte Eintrag nicht vorhanden, generiert der TLB eine Ausnahme vom Typ SEGFAULT. Das Betriebssystem bekommt nun die Möglichkeit, den entsprechenden Eintrag nachzuladen.

TLB sind vor allem in x86-64 und älteren 64 bit Architekturen verbreitet. Während für die klassischen 32 bit x86-Prozessoren eine MMU verwendet werden konnte, ist der heute übliche 64 bit Adressraum einfach zu groß, um durch vollständige Seitentabellen übersetzt zu werden. Wirklich neu ist das Konzept allerdings nicht. Bereits zu 32-bit-Zeiten benutzten viele MMUs intern einen TLB, um häufig benutzte Einträge zu cachen.

Behandlung von Pagefaults

Pagefaults sind Fehlermeldungen bei der Umrechnung zwischen Adressräumen. Sie werden von einem Hardware-Gerät generiert und dem Betriebssystem zugestellt.

Pagefaults können verschiedene Gründe haben.

Die virtuelle Adresse konnte nicht umgerechnet werden, da sich der benötigt Eintrag nicht in der MMU oder dem TLB befindet.
Es wurde versucht, auf eine Seite mit dem RO-Bit zu schreiben.
Es wurde versucht, Instruktionen von einer Seite mit dem NX-Bit zu laden.