Einführung in die Seitentabelle (mit 4 verschiedenen Typen)

Übersicht über die Seitentabelle

Was ist eine Seitentabelle? Eine Seitentabelle ist eine Datenstruktur, die vom virtuellen Speichersystem im Betriebssystem eines Computers verwendet wird, um die Zuordnung zwischen virtuellen Adressen und physischen Adressen zu speichern. Das vom zugreifenden Prozess ausgeführte Programm verwendet virtuelle Adressen, während die Hardware, genauer gesagt das RAM-Subsystem, physische Adressen verwendet. Die Seitentabelle ist eine Schlüsselkomponente der virtuellen Adressumsetzung und wird für den Zugriff auf Daten im Speicher benötigt.

In einem Betriebssystem, das virtuellen Speicher verwendet, wird jedem Prozess der Eindruck vermittelt, dass er einen großen und zusammenhängenden Speicherbereich verwendet. Physisch gesehen kann der Speicher jedes Prozesses in verschiedenen Bereichen des physischen Speichers verstreut sein oder in einen anderen Speicher, normalerweise ein Festplattenlaufwerk oder ein Solid-State-Laufwerk, ausgelagert worden sein.

Wenn ein Prozess Zugriff auf Daten in seinem Speicher anfordert, ist das Betriebssystem dafür verantwortlich, die vom Prozess angegebene virtuelle Adresse der physischen Adresse des tatsächlichen Speichers zuzuordnen, in dem die Daten gespeichert sind. In der Seitentabelle speichert das Betriebssystem die Zuordnung von virtueller Adresse zu physischer Adresse, und jede Zuordnung wird auch als Seitentabelleneintrag (PTE) bezeichnet.

Übersetzungsprozess der Seitentabelle

Die Speicherverwaltungseinheit (MMU) der CPU speichert die zuletzt verwendete Abbildung aus der Seitentabelle des Betriebssystems im Cache. Dieser wird Übersetzungspuffer oder Translation Lookaside Buffer (TLB) genannt und ist ein zugehöriger Cache.

Wenn eine virtuelle Adresse in eine physikalische Adresse umgewandelt werden muss, wird zuerst der TLB, der Übersetzungspuffer, durchsucht. Wird eine Übereinstimmung gefunden (TLB-Treffer), wird die physikalische Adresse zurückgegeben und der Speicherzugriff kann fortgesetzt werden. Gibt es jedoch keine Übereinstimmung (TLB-Fehlschlag), wird die Speicherverwaltungseinheit oder der TLB-Fehlschlag-Handler des Betriebssystems normalerweise die Adresszuordnung in der Seitentabelle nachschlagen, um zu sehen, ob es eine Zuordnung gibt (ein Page Walk).

Wenn es eine Zuordnung gibt, wird sie in die TLB zurückgeschrieben (dies muss geschehen, weil die Hardware über die TLB im virtuellen Speichersystem auf den Speicher zugreift), und der fehlerhafte Befehl wird neu gestartet (dies kann auch parallel geschehen). Nachfolgende Übersetzungen werden TLB-Treffer finden, und der Speicherzugriff wird fortgesetzt.

Typen von Seitentabellen

Invertierte Seitentabellen

Die invertierte Seitentabelle (Inverted Page Table, IPT) kann man sich am besten als eine chipexterne Erweiterung der TLB vorstellen, die den normalen Systemspeicher (RAM) verwendet. Im Gegensatz zur echten Seitentabelle ist sie nicht in der Lage, alle aktuellen Zuordnungen zu speichern. Das Betriebssystem muss darauf vorbereitet sein, mit Fehlschlägen umzugehen, genau wie bei der Verwendung der softwaregefüllten TLB im MIPS-Stil.

IPT kombiniert eine Seitentabelle und eine Frametabelle in einer Datenstruktur. Der Kern einer Tabelle mit fester Größe ist, dass die Anzahl der Zeilen der Anzahl der Frames im Speicher entspricht. Wenn es 4.000 Frames gibt, hat die invertierte Seitentabelle 4.000 Zeilen. Jede Zeile enthält einen Eintrag für die virtuelle Seitennummer (VPN), die physische Seitennummer (nicht die physische Adresse), einige andere Daten und die Methode zur Erstellung der Kollisionskette.

Mehrstufige Seitentabellen

Mehrstufige Seitentabellen werden auch als „hierarchische Seitentabellen“ bezeichnet. Obwohl die invertierte Seitentabelle eine Liste der von allen Frames im physischen Speicher installierten Mappings enthält, kann dies sehr verschwenderisch sein. Um dies zu vermeiden, können wir eine Seitentabellenstruktur erstellen, die virtuelle Seitenabbildungen enthält. Dazu werden mehrere Seitentabellen angelegt, die einen bestimmten Block des virtuellen Speichers abdecken. Zum Beispiel können wir kleinere 4K-Seiten mit 1024 Einträgen erstellen, die 4M virtuellen Speicher abdecken.

Dies ist nützlich, weil die oberste und unterste Schicht des virtuellen Speichers normalerweise verwendet wird, wenn der Prozess läuft – die oberste Schicht wird normalerweise für Text- und Datensegmente verwendet, und die unterste Schicht wird normalerweise für den Stack verwendet, mit freiem Speicher dazwischen. Mehrstufige Seitentabellen können einige kleinere Seitentabellen reservieren, um nur den oberen und unteren Teil des Speichers abzudecken, und nur bei Bedarf neue Seitentabellen erstellen.

Jede dieser kleineren Seitentabellen ist nun durch die Hauptseitentabelle miteinander verbunden, wodurch eine Baumstruktur entsteht. Es sind nicht nur zwei Ebenen erforderlich, sondern es können mehrere Ebenen erforderlich sein.

Die virtuelle Adresse kann in diesem Modus in drei Teile aufgeteilt werden: den Index in der Stammseitentabelle, den Index in der Unterseitentabelle und den Offset in der Seite.

Virtualisierte Seitentabellen

Die Erstellung einer Seitentabellenstruktur, welche die Abbildung jeder virtuellen Seite im virtuellen Adressraum enthält, kann sich als Verschwendung erweisen. Das Problem des übermäßigen Platzbedarfs kann jedoch gelöst werden, indem die Seitentabelle im virtuellen Speicher untergebracht und der Speicher der Seitentabelle vom virtuellen Speichersystem verwaltet wird.

Ein Teil dieser linearen Seitentabellenstruktur muss sich jedoch immer im physischen Speicher befinden, um zirkuläre Seitenfehler zu verhindern und wichtige Teile der Seitentabelle zu finden, die in der Seitentabelle nicht vorhanden sind.

Verschachtelte Seitentabellen

Sie können verschachtelte Seitentabellen implementieren, um die Leistung der Hardwarevirtualisierung zu verbessern. Durch die Bereitstellung von Hardwareunterstützung für die Seitentabellenvirtualisierung werden die Simulationsanforderungen erheblich reduziert. Für die x86-Virtualisierung stehen derzeit die Funktion Extended Page Table von Intel und die Funktion Rapid Virtualization Indexing von AMD zur Auswahl.