Seitentabelle

Eine Seitentabelle (englisch 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 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

Schematische Darstellung der einstufigen Adressumsetzung

Die Adressumsetzung mit Hilfe einer einstufigen Seitentabelle geschieht durch Interpretation der n höherwertigen Bits einer virtuellen Adresse als Seitennummer der angeforderten Speicherseite und der Verwendung der m niederwertigen Bits als Offset. Die Seitennummer bestimmt dabei ausgehend von der Basisadresse der Seitentabelle, welche in einem 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 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 kiB, dann hat die zugehörige Seitentabelle bei einem 16-Bit-Adressraum, also einem virtuellen Speicher von 64 kiB, lediglich 16 Einträge. Für einen 32-Bit-Adressraum, also einem virtuellen Speicher von 4 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.^[1]

Mehrstufige Seitentabelle

(c) Frank Jacobsen, CC BY-SA 3.0

Schematische Darstellung der mehrstufigen Adressumsetzung

Die Adressumsetzung mit Hilfe einer k-stufigen Seitentabelle geschieht durch Aufteilung einer virtuellen Adresse in k*n höherwertige Bits als Seitentabellenverweise und m niederwertige Bits als 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.^[1]

Invertierte Seitentabelle

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.: 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. d. R. eine 0) vorfindet, indem sie einen so genannten Seitenfehler (Page Fault) auslöst.

Einzelnachweise

1. ↑ ^{a b} Andrew S. Tanenbaum Moderne Betriebssysteme. Übersetzt von Uwe Baumgarten. 2., überarbeitete Auflage. Pearson Studium / Prentice Hall, München 2003, ISBN 3-8273-7019-1.