Page table

Seitentabellen sind Teile von Prozessen, welche der Transformation von virtuellen in physische Seitenrahmen dienen. Die optimale Seitengröße ist ein Kompromiss zwischen Häufigkeit von Seitenwechseln und Größe der Tabelle. In der Praxis ist eine Größe zwischen 2 und 32 kByte üblich.

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.

Mehrstufige Seitentabelle

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.

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

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 einer Seitentabelle einen Ungültig Eintrag vorfindet, indem sie einen so genannten Seitenfehler (Page Fault) auslöst.

Weblinks

• Linux Kernel 2.4.x Prozessadressräume und Swapping - enthält sehr übersichtliche Abbildungen der Seitentabellen