Quelltext der Seite Seitentabelle

Eine '''Seitentabelle''' ({{enS|''page table''}}) ist die Datenstruktur, die für das Umrechnen von virtuellen zu physischen Adressen verwendet wird. Virtuelle Adressen werden von Prozessen verwendet und sind eine Abstraktion vom physischen Speicher. Der Prozess kann nur auf seinen eigenen virtuellen Speicher schreiben und lesen. Das Umrechnen der virtuellen Adresse eines Prozesses wird heute üblicherweise von der [[Memory Management Unit|MMU]]  übernommen und ist für den Prozess gar nicht einsehbar. Die Seitentabellen beinhalten dabei das Mapping zwischen der virtuellen und der physischen Adresse.

== Einstufige Seitentabelle ==
[[Datei:EinstufigeSeitentabelle.png|mini|400px|Schematische Darstellung der einstufigen Adressumsetzung]]

Die Adressumsetzung mit Hilfe einer einstufigen Seitentabelle geschieht durch Interpretation der ''n'' höherwertigen Bits einer [[Virtuelle Adresse|virtuellen Adresse]] als Seitennummer der angeforderten [[Speicherseite]] und der Verwendung der ''m'' niederwertigen Bits als [[Speicheradresse#Segmentierte Adressen|Offset]]. Die Seitennummer bestimmt dabei ausgehend von der Basisadresse der Seitentabelle, welche in einem [[Register (Computer)|Register]] der [[Memory Management Unit]] gehalten wird, denjenigen Eintrag in der Seitentabelle, aus dem die Basisadresse der nötigen realen Speicherseite abzulesen ist. Des Weiteren beinhaltet die Seitentabelle auf den höherwertigen Bits Statusinformationen über die Speicherseite, die beispielsweise Auskunft geben, ob sich die Speicherseite im [[Random-Access Memory|RAM]] befindet oder ob sie seit dem letzten Zugriff verändert wurde. Die aus der Seitentabelle ausgelesene Basisadresse der realen Speicherseite zusammen mit dem unveränderten Offset ergeben die reale Adresse.

Da die Anzahl der Einträge einer einstufigen Seitentabelle von der Größe des virtuellen Adressraums und der gewählten Seitengröße abhängt, ergibt sich ein Problem, wenn der virtuelle Adressraum zu groß und/oder die gewählte Seitengröße zu klein wird. Wählt man beispielsweise eine Seitengröße von 4&nbsp;kiB, dann hat die zugehörige Seitentabelle bei einem 16-Bit-Adressraum, also einem virtuellen Speicher von 64&nbsp;kiB, lediglich 16 Einträge. Für einen 32-Bit-Adressraum, also einem virtuellen Speicher von 4&nbsp;GiB Größe, und gleicher Seitengröße benötigt eine zugehörige Seitentabelle bereits über eine Million Einträge, die alle im Speicher gehalten werden müssten.
Um den Speicherbedarf der Seitentabellen also auch für große Adressräume akzeptabel zu halten, wurden die Konzepte der ''mehrstufigen Seitentabelle'' und der ''invertierten Seitentabelle'' entwickelt.<ref name="Tanenbaum Moderne Betriebssysteme">Andrew S. Tanenbaum ''Moderne Betriebssysteme''. Übersetzt von Uwe Baumgarten. 2., überarbeitete Auflage. Pearson Studium / Prentice Hall, München 2003, ISBN 3-8273-7019-1.</ref>

== Mehrstufige Seitentabelle ==
[[Datei:MehrstufigeSeitentabelle.png|mini|400px|Schematische Darstellung der mehrstufigen Adressumsetzung]]

Die Adressumsetzung mit Hilfe einer ''k''-stufigen Seitentabelle geschieht durch Aufteilung einer [[Virtuelle Adresse|virtuellen Adresse]] in ''k*n'' höherwertige Bits als Seitentabellenverweise und ''m'' niederwertige Bits als [[Speicheradresse#Segmentierte Adressen|Offset]]. Mit dem ''k''-ten Verweis in der virtuellen Adresse wird aus der ''k''-ten Seitentabelle die Basisadresse der Seitentabelle der Stufe ''k+1'' ausgelesen. Die letzte Stufe enthält dann den tatsächlichen Verweis auf die reale Basisadresse. Die aus der letzten Stufe der Seitentabellen ausgelesene Basisadresse der realen Speicherseite zusammen mit dem unveränderten Offset ergeben die reale Adresse.

Der Vorteil bei diesem Ansatz gegenüber der einstufigen Seitentabelle ist der, dass nicht immer alle Teile der Seitentabelle im Speicher gehalten werden müssen.<ref name="Tanenbaum Moderne Betriebssysteme" />

== Invertierte Seitentabelle ==
[[Datei:Invertierte Seitentabellen de.svg|mini|500px|links|Invertierte Seitentabelle]]

Insbesondere einstufige, aber auch mehrstufige Seitentabellen benötigen sehr viel Speicherplatz, nur um die Seitentabelle im Speicher abzulegen. Mit dem Ansatz der invertierten Seitentabelle beseitigt man dieses Problem. Es wird in der Seitentabelle nicht mehr ein Eintrag pro virtueller Seite angelegt, sondern nur noch je ein Eintrag pro realer Speicherseite. Der Zugriff auf diese Tabelle benötigt nun jedoch einen Suchvorgang, um die virtuelle Adresse in der gesamten Seitentabelle zu finden und die zugehörige reale Adresse auszulesen. Häufig wird das Suchen in der invertierten Seitentabelle durch das Vorschalten einer [[Hashtabelle]] beschleunigt.

Da sich keine Informationen über ausgelagerte Seiten in der invertierten Seitentabelle finden, ist bei einem Seitenfehler der Rückgriff auf eine „normale“ Seitentabelle notwendig.

== Seitenfehler (Page Fault) ==
Bei jedem Verfahren kann es natürlich passieren, dass die angeforderte virtuelle Adresse sich in einer nicht im [[Arbeitsspeicher]] befindlichen [[Speicherseite]] befindet, sondern erst durch [[Paging]] vom Hintergrundspeicher in den Arbeitsspeicher geladen werden muss (engl.: [[Paging#Demand Paging|Demand Paging]]).
Die Memory Management Unit signalisiert dies, sobald sie in den Statusbits bei dem sogenannten Valid Bit einer Seitentabelle einen ''Ungültig'' Eintrag (i.&nbsp;d.&nbsp;R. eine 0)  vorfindet, indem sie einen so genannten [[Seitenfehler]] (Page Fault) auslöst.

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4620646-2}}

[[Kategorie:Speicherverwaltung]]
[[Kategorie:Rechnerarchitektur]]