Paging

Als Paging (vgl. engl. page „Speicherseite“) bezeichnet man die Methode der Speicherverwaltung per Seitenadressierung durch Betriebssysteme. Nur selten wird die deutsche Bezeichnung Kachelverwaltung verwendet.

Das Paging ermöglicht eine virtuelle Speicherverwaltung. Der virtuelle Speicher bezeichnet den vom tatsächlich vorhandenen physischen Arbeitsspeicher unabhängigen Adressraum, der einem Prozess vom Betriebssystem zur Verfügung gestellt wird. Da meist mehr virtuelle Adressen existieren als im physischen Arbeitsspeicher umsetzbar sind, werden einige Speicherbereiche vorübergehend auf die Festplatte ausgelagert.

Beim Paging wird der virtuelle Adressraum in gleich große Stücke unterteilt, die man als Seiten (engl. pages) bezeichnet. Auch der physische Adressraum ist derart unterteilt. Die entsprechenden Einheiten im physischen Speicher nennt man Seitenrahmen oder auch Kacheln (engl. page frames). Die Seiten werden in der sogenannten Seitentabelle (engl. page table) verwaltet, die Informationen darüber enthält, wo für eine Seite der entsprechende Seitenrahmen im Arbeitsspeicher tatsächlich zu finden ist.

Wenn ein Prozess eine virtuelle Adresse anspricht, die keiner physischen Adresse zugeordnet ist, wird ein Systemaufruf ausgelöst. Dieser Aufruf wird Seitenfehler (engl. page fault) genannt. Als unmittelbare Folge des Seitenfehlers kommt es zu einer synchronen Prozessunterbrechung (Trap). Das Betriebssystem wählt dann einen wenig benutzten Seitenrahmen aus, schreibt dessen Inhalt zurück auf die Festplatte, lädt die angeforderte Seite in den frei gewordenen Seitenrahmen, ändert die Zuordnungstabelle und führt den unterbrochenen Befehl noch einmal aus.

Funktionsweise

Virtueller Adressraum

Virtueller und physischer Speicher, wobei ein Teil des virtuellen Adressraums auf die Festplatte ausgelagert wird.

Der physische Adressraum ist durch den tatsächlich verfügbaren Arbeitsspeicher (Hauptspeicher) gegeben. Eine physische Adresse ist eine reale Adresse einer Speicherzelle im Arbeitsspeicher. Meistens verwenden Prozesse jedoch nicht mehr physische, sondern nur noch virtuelle (logische) Adressen. Das Prinzip der virtuellen Speicherverwaltung ermöglicht es, dass alle aktiven Prozesse mehr Speicherplatz belegen dürfen, als tatsächlich im physischen Adressraum zur Verfügung steht. Die virtuellen Adressen bilden den virtuellen Adressraum. Diese gehen nun nicht direkt an den Speicherbus, sondern an die Memory Management Unit (MMU, dt. Speicherverwaltungseinheit), welche die virtuellen Adressen auf die physischen Adressen abbildet.

Aus der Sicht des Programmierers, der mit virtuellen Adressen arbeitet, erscheint der Adressraum (fast) unbegrenzt. Er braucht keine Rücksicht darauf zu nehmen, ob diese Adressen im real vorhandenen physischen Arbeitsspeicher wirklich existieren. Das Betriebssystem löst diese Aufgabe mit der vorübergehenden Auslagerung von Speicherbereichen auf einen Massenspeicher, meistens die Festplatte. Bei der Speicherverwaltung werden also Daten vom Arbeitsspeicher auf die Festplatte ein- und ausgelagert.

Häufig verfügt ein System über sehr viel mehr virtuellen als physischen Speicher. Konkret legt das installierte RAM fest, wie groß der physische Speicher ist, während der virtuelle Adressraum von der Architektur des Befehlssatzes abhängt. Mit einem 32-Bit-Prozessor kann man maximal $2^{32}$ Byte (also 4 GB) Speicher adressieren, mit einem 64-Bit-System $2^{64}$ Byte (16 ExaBytes), auch wenn beispielsweise nur 512 MB RAM tatsächlich installiert sind.

Das Konzept der virtuellen Speicherverwaltung funktioniert besonders gut bei Systemen mit Multiprogramming, wenn dabei einzelne Teile von mehreren Programmen gleichzeitig im Speicher sind: Während ein Programm darauf wartet, dass Teile von ihm von der Festplatte eingelesen werden, kann die CPU einem anderen Prozess zugeteilt werden.

Zur Organisation des virtuellen Speichers gibt es einerseits den segmentorientierten Ansatz (siehe Segmentierung), bei dem der Speicher in Einheiten unterschiedlicher Größen aufgeteilt ist, und andererseits den seitenorientierten Ansatz (Paging), bei dem alle Speichereinheiten gleich lang sind.

Seitenauslagerung

Paging mit Seiten im virtuellen (logischen) Speicher, Seitentabelle und Seitenrahmen im physischen Speicher

Beim Paging wird der virtuelle Adressraum in gleich große Stücke unterteilt, die man als Seiten (engl. pages) bezeichnet. Auch der physische Adressraum ist derart unterteilt. Die entsprechenden Einheiten im physischen Speicher nennt man Seitenrahmen oder auch Kacheln (engl. page frames). Seiten und Seitenrahmen sind in der Regel gleich groß, beispielsweise 4 KByte.

Beispiel: Die physische Größe des Arbeitsspeichers sei 64 KByte. Ein Programm benötigt insgesamt 200 KByte Speicher. Um das größere Programm trotzdem auf dem kleineren Arbeitsspeicher ausführen zu können, kann man den Adressraum in Seiten (Pages) aufteilen, beispielsweise vier Seiten zu 64 KByte, wobei dann die letzte Seite nur teilweise gefüllt ist. Es befindet sich dann jeweils eine der vier Seiten im physischen Arbeitsspeicher, die anderen drei sind auf die Festplatte ausgelagert.

Der Teil der Festplatte, der für die ausgelagerten Seiten verwendet wird, wird Paging-Area oder Schattenspeicher genannt. Zum Ein- und Auslagern der Seiten existieren viele verschiedene Strategien. Grundsätzlich wird immer versucht, die Seiten im Arbeitsspeicher zu halten, die auch in naher Zukunft verwendet werden, um möglichst selten ein Paging durchzuführen.

Solange die Speicherzugriffe Seiten betreffen, die im Arbeitsspeicher liegen, arbeitet das System ganz normal. Wird aber eine Seite im ausgelagerten Speicher angesprochen, muss die angeforderte Seite eingelagert werden (und unter Umständen eine andere Seite ausgelagert werden). Ausserdem muss eine Adressabbildung aktiviert werden. Das ganze Verfahren heisst Seitenauslagerung oder Paging.

Seitentabellen

Adressabbildung

Im Multiprogramming-Betrieb stellt der Memory-Manager jedem Prozess einen eigenen virtuellen Adressraum zur Verfügung, d.h. eine Menge von Adressen, die ein Prozess zur Adressierung des Speichers benutzen kann. Der virtuelle Adressraum eines Prozesses wird nun beim Paging in Einheiten aufgebrochen, die sogenannten Seiten. Diese werden in der sogenannten Seitentabelle (page table) verwaltet, die Informationen darüber enthält, wo für eine Seite die entsprechenden Seitenrahmen im Arbeitsspeicher tatsächlich zu finden sind. Mathematisch kann die Tabelle als eine Funktion aufgefasst werden, die die virtuelle Seitennummer als Argument nimmt und die Seitenrahmennummer (Page-Frame-Nummer) als Ergebnis liefert. Dadurch kann eine virtuelle Adresse auf eine physische Adresse abgebildet werden.

Eine virtuelle Adresse wird in zwei Teile zerlegt: Eine virtuelle Seitennummer (höherwertige Bits) und einen Offset (niederwertige Bits). Die virtuelle Seitennummer wird als Index für den Eintrag in der Seitentabelle benutzt. Der Offset stellt den relativen Abstand einer Adresse zu einer Basisadresse dar. Er ist also die Distanz, die die genaue Byteadresse innerhalb einer Seite angibt. Mit Hilfe der virtuellen Seitennummer als Index wird in der Seitentabelle der zugehörige Eintrag ausfindig gemacht. Dieser enthält einen Verweis auf den Seitenrahmen (Page-Frame). Die Seitenrahmennummer wird zur phyischen Adresse ergänzt und zusammen mit der Distanz (Offset) erhält man die physische Adresse. Die Größe des Offsets sollte also so gewählt werden, dass damit jede Adresse innerhalb einer Seite angesprochen werden kann.

Die folgende Grafik veranschaulicht, wie aus einer virtuellen Adresse eine physische Adresse (hier: Reale Adresse) berechnet wird:

Die virtuelle Adresse besteht aus zwei Binärzahlen, die n-bit-lange Seitennummer und der m-bit-lange Offset. Der höherwertige Teil der phyischen Adresse (hier: Basisadresse der realen Seite) wird der Seitentabelle entnommen, mit der Seitennummer als Index. Wird dieser mit dem Offset konkateniert, so ergibt sich eine neue Zahl, die genau die phyische Speicheradresse ist. Derartige Berechnungen werden von der Memory Management Unit durchgeführt.

Die Adressen auf der Festplatte, an denen die ausgelagerten Seiten liegen, werden nicht in der Seitentabelle gespeichert. Diese enthält nur Informationen, die die Hardware zur Umrechnung einer virtuellen Adresse in eine physische benötigt. Bei der Behandlung von Seitenfehlern wird auf eigene Tabellen im Betriebssystem zurückgegriffen.

Aufbau eines Seitentabelleneintrages

Über die Seitennummer als Index kann ein Eintrag in der Seitentabelle adressiert werden. Der genaue Aufbau eines solchen Eintrages ist stark maschinenabhängig. Die darin enthaltene Information ist jedoch von Maschine zu Maschine etwa gleich. Nach Andrew S. Tanenbaum (2009) sieht ein typischer Seitentabelleneintrag folgendermassen aus:

Die einzelnen Einträge haben dabei die folgenden Bedeutungen:

• Seitenrahmennummer: Eine physische Adresse im Arbeitsspeicher, auf den der Eintrag verweist (siehe Abschnitt oben).
• Present-/Absent-Bit: Dieses zeigt an, ob die Seite momentan im Arbeitsspeicher liegt (Bit auf 1 gesetzt) oder nicht (Bit auf 0 gesetzt). Letzteres erzeugt einen Seitenfehler.
• Protection-Bits (auch Schutzbits): Diese regeln den Zugriff auf die Seite. Im einfachsten Fall enthält das Feld nur 1 Bit, mit 0 für Lese- und Schreibzugriff und 1 für Schreibzugriff. Eine ausgefeiltere Methode benutzt drei Bits, jeweils eines für das Leserecht, eines für das Schreibrecht und eines für das Recht, die Seite auszuführen.
• M-Bit (Modified-Bit, auch Dirty-Bit): Das M-Bit wird gesetzt, wenn ein Programm eine Seite schreibt. Dies verwendet das Betriebssystem beim Auslagern einer Seite: Wenn die Seite verändert wurde, muss der Seitenrahmen zurück auf die Festplatte geschrieben werden, wenn nicht, kann er einfach überschrieben werden, weil die Kopie der Seite auf der Festplatte noch aktuell ist.
• R-Bit (Referenced-Bit): Das R-Bit wird bei jedem Zugriff auf die Seite gesetzt, egal ob Lese- oder Schreibzugriff. Es hilft dem Betriebssystem bei der Entscheidung, welche Seite bei einem Seitenfehler ausgelagert werden soll. Seiten, die nicht benutzt werden, sind bessere Kandidaten als solche, auf die ständig zugegriffen wird.
• Bit zum Abschalten von Caching: Mit diesem Bit kann das Caching abgeschaltet werden. Dies ist insbesondere für Seiten relevant, die auf Geräteregister statt auf Speicher abgebildet werden. Rechner, die einen getrennten E/A-Adressraum haben und keine Memory-Mapped-Ein-/Ausgabe benutzen, brauchen dieses Bit nicht.

Seitenfehler

Wenn ein Prozess eine Adresse anspricht, die nicht im Arbeitsspeicher geladen ist, erzeugt die MMU einen sogenannten Seitenfehler (engl. page fault), dessen Behandlung vom Betriebssystem übernommen wird. Für einen Seitenfehler gibt es zwei generelle Ursachen:

• Der eigentlich zugehörige Seitenrahmen ist nur vorübergehend nicht im Arbeitsspeicher vorhanden, etwa weil er gerade ausgelagert ist oder der Prozess das erste Mal auf diese Seite zugreift.
• Die Seite ist ungültig bzw. der Prozess hat auf eine ihm nicht erlaubte virtuelle Adresse zugegriffen. Dabei wird eine „Segmentation fault“ oder „General protection fault“ ausgelöst.

Als unmittelbare Folge eines Seitenfehlers kommt es zu einer synchronen Prozessunterbrechung (Trap): Es wird ein sogenannter Pagefault-Interrupt ausgelöst. Das Betriebssystem springt im Kernelmodus auf eine spezielle Unterbrechungsroutine zur Bearbeitung des Seitenfehlers und versucht unter Beachtung der Seitenersetzungsstrategie und der Vergabestrategie die Seite in einen Seitenrahmen zu laden. Anschliessend erhält der unterbrochene Prozess nach Möglichkeit entweder sofort oder später wieder den Prozessor (siehe dazu Prozesszustände). Insbesondere werden die folgenden Schritte durch das Betriebssystem ausgeführt:

• Es wird überprüft, ob die Anforderung erlaubt ist.
• Es wird ein freier Seitenrahmen im Arbeitsspeicher gesucht. Falls kein freier Seitenrahmen gefunden werden kann, muss zuerst durch Auslagerung des Inhalts eines Seitenrahmens auf die Festplatte Platz geschafft werden.
• Es werden die benötigten Informationen auf der Festplatte gesucht und in den gefundenen Seitenrahmen kopiert.
• Der zugehörige Eintrag in der Seitentabelle wird angepasst, d.h. die Adresse der Seite wird eingetragen und das entsprechende Present-/Absent-Bit wird gesetzt.

Um einen freien Seitenrahmen zu finden, kann beispielsweise eine Freelist verwaltet werden. Dafür eignet sich ein Bitvektor, der für jeden Seitenrahmen ein Bit enthält. Ist das Bit gesetzt, so wird dieser benutzt, andernfalls ist er frei und kann belegt werden. Sobald ein Seitenrahmen belegt oder freigegeben wird, muss natürlich die Freelist entsprechend angepasst werden.

Translation Lookaside Buffer

Schematischer Ablauf der Umrechnung einer virtuellen in eine physische Adresse mit Hilfe von MMU und TLB

Translation Lookaside Buffer (Adressumsetzpuffer, kurz: TLB) werden eingesetzt, um die Übersetzung der virtuellen in die physischen Adressen zu beschleunigen.

Würde ausschliesslich die Seitentabelle im Arbeitsspeicher gehalten, würde die Ausführungsgeschwindigkeit deutlich verringert. Beispielsweise ist für einen 1-Byte-Befehl, der ein Register in ein anderes kopiert, ohne Paging nur ein Speicherzugriff nötig, um den Befehl aus dem Speicher zu holen. Mit Paging ist mindestens ein zusätzlicher Speicherzugriff auf die Seitentabelle erforderlich. Wenn also nun zwei Speicherzugriffe pro Befehl erforderlich werden, würde die Leistung der CPU in etwa halbiert.

Deshalb werden die zuletzt ermittelten $n$ Werte für die Adresse der physischen Speicherseite im Translation Lookaside Buffer (TLB) gecacht, wodurch erneute Zugriffe auf Adressen in dieser Seite nicht aufwändig neu ermittelt werden müssen, sondern aus dieser Liste entnommen werden können. Der TLB kann eine begrenzte Menge dieser Referenzen halten und kann dadurch die Ausführung von Speicherzugriffen deutlich beschleunigen. Dies wird über assoziative Ordnungsregister realisiert, die parallele Zugriffe erlauben. Der TLB ist normalerweise ein Teil der MMU. Die Felder des TLB sind normalerweise eins zu eins aus der Seitentabelle entnommen, mit Ausnahme der virtuellen Seitennummer, die in der Seitentabelle nicht benötigt wird. Ein weiteres Feld gibt zudem an, ob der Eintrag momentan benutzt wird.

Die Anzahl der Felder eines TLB hängt von der Rechnerarchitektur ab und liegt häufig zwischen 8 und 256. IA-64-Architekturen verfügen beispielsweise über 128 Einträge im TLB. Aufgrund der hohen Lokalität vieler Programme, kann bereits bei acht Einträgen eine beachtliche Leistungssteigerung erzielt werden.

Wenn eine virtuelle Adresse zur Übersetzung an die MMU geschickt wird, überprüft also diese zuerst, ob ein entsprechender Eintrag im TLB vorhanden ist, indem sie die virtuelle Seitennummer mit allen Einträgen gleichzeitig (parallel) vergleicht. Wird ein passender Eintrag gefunden, kann die Seitennummer aus dem TLB verwendet werden. Andernfalls tritt ein TLB-Fehler auf. Die MMU holt entsprechend den Eintrag aus der Seitentabelle und schreibt ihn zudem in den TLB.

Weitere Eigenschaften

Seitengröße

Die Größe der Seitenrahmen (Page-Frames) hat einen erheblichen Einfluss auf die Speicherausnutzung. Für große Seiten erhält man mehr Treffer pro Seitenaufruf, d.h. es sind weniger Einlagerungen nötig. Zudem reicht dann eine kleinere Seitentabelle aus. Allerdings können sich dann auch weniger Seiten gleichzeitig im Arbeitsspeicher befinden und es gibt eine größere interne Fragmentierung, die dadurch entsteht, dass einem Prozess insgesamt ein größerer Speicherbereich zugewiesen ist, als er eigentlich benötigt. Konkret besteht die interne Fragmentierung aus einem Teil der letzten Seite eines Prozesses. Sind die Seitenrahmen dagegen zu klein, benötigt man sehr lange Seitentabellen. Die optimale Seitengröße stellt einen Ausgleich zwischen diesen Effekten dar.

Eine standardmäßige Seitengrösse wird normalerweise durch die Hardware vorgegeben. Die Seitengröße neigt dazu, mit dem Speicher zu wachsen, aber nicht linear. Wenn sich der Speicher vervierfacht, wird die Seitengröße meistens nicht einmal verdoppelt.

Der Pentium 4 und alle anderen IA-32-Prozessoren stellen ein Paging mit einer Seitengröße von 4 KB zur Verfügung. Ab dem Pentium Pro kann die Seitengröße wahlweise auf 4 MB eingestellt werden. Bei der AMD64-Architektur werden physische Seitengrößen von 4 KB, 2 MB, 4 MB und 1 GB unterstützt. Einige Prozessoren unterstützen auch mehrere Seitengrößen, die man teils gleichzeitig nutzen kann. So kann man beispielsweise für das Betriebssystem und den Grafikspeicher eine große Seitengröße (Large Pages) vorsehen, z.B. 8 MB.

Auch wenn die Hardware gewisse Seitengrößen vorgibt, kann das Betriebssystem diese beeinflussen. Wenn die Hardware beispielsweise für 4-KB-Seiten entworfen wurde, kann das Betriebssytem die Seitenrahmen 0 und 1, 2 und 3, 4 und 5, usw. als 8-KB-Seiten behandeln, indem es einer Seite immer zwei aufeinander folgende Seitenrahmen zuordnet.

Die folgende Tabelle zeigt Seitengrössen unter Windows in Abhängigkeit der Prozessorarchitektur:

Prozessorarchitektur	Größe der Small Page	Größe der Large Page
x86	4 KB	4 MB
AMD64	4 KB	2 MB
Intel 64	8 KB	16 MB

Seitentabellen für große Speicherbereiche

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. Bei einem 64-Bit-Computer mit einem Adressraum von $2^{64}$ Byte und 64 KByte großen Seiten hätte die Seitentabelle $2^{52}$ Einträge. Bei 8 Byte pro Eintrag wäre die Seite dann 30 Millionen GByte (30 PB) groß. Für virtuelle 64-Bit-Adressräume mit Paging sind also andere Lösungen nötig. Deshalb wurden die Konzepte der mehrstufigen Seitentabelle und der invertierten Seitentabelle entwickelt.

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.

Der Vorteil bei diesem Ansatz gegenüber der einstufigen Seitentabelle ist der, dass nicht immer alle Seitentabellen im Speicher gehalten werden müssen. Besonders die nicht benötigten Tabellen sollten nicht nutzlos im Speicher gehalten werden. Die Seitentabellen selbst können also auch ausgelagert werden, sie unterliegen ebenfalls dem Paging.

Für die IA-32-Prozessoren entschied man sich beispielsweise für eine zweistufige Seitenverwaltung, bei der ein zentrales Seitenverzeichnis (page directory) auf bis zu 1024 Seitentabellen (page tables) verweist. Die virtuelle Adresse wurde für die Umsetzung in drei Teile aufgeteilt:

• Die höchstwertigen 10 Bit werden bentutzt, um eine der max. 1024 Einträge im Seitenverzeichnis auszuwählen, der einen Verweis auf die Seitentabelle enthält.
• Die Bits 12-21 bilden die Seitennummer in der entsprechenden Tabelle.
• Die niederwertigsten 12 Bit bilden den Offset.

Bei bei x64-Windows ist die Seitentabelle sogar vierstufig. Es wird eine 48 Bit breite virtuelle Adresse in 4 Indices zu je 9 Bit und einen Offset zu 12 Bit eingeteilt.

Invertierte Seitentabelle

Invertierte Seitentabelle

Bei der Methode der invertierten Seitentabelle wird in der Seitentabelle nicht mehr ein Eintrag pro virtueller Seite angelegt, sondern nur noch ein Eintrag für jeden physischen Seitenrahmen. Wenn der virtuelle Adressraum wesentlich größer als der physische Speicher ist, wird dadurch sehr viel Speicherplatz der Tabelle eingespart.

Jeder Eintrag in der Tabelle speichert das zugehörige Paar (Prozessnummer, Seitennummer). Der Zugriff auf die Seitentabelle erfordert nun jedoch einen Suchvorgang: Wenn ein Prozess mit der Prozessnummer n auf die virtuelle Seite p zugreifen will, muss die Hardware die gesamte Tabelle nach dem Eintrag (n,p) durchsuchen. Dies macht einen Speicherzugriff wesentlich aufwändiger. Abhilfe schafft das Vorschalten einer Hashtabelle mit den virtuellen Adressen als Hashwerten. Alle Seiten, die denselben Hashwert haben, werden verkettet.

Zusätzlich wird der Speicherzugriff durch einen TLB beschleunigt. Wenn alle häufig benutzten Seiten in den TLB passen, ist die Adressumrechnung gleich schnell wie mit herkömmlichen Methoden. Bei einem TLB-Fehler muss jedoch die invertierte Seitentabelle von der Software durchsucht werden.

Demand Paging und Prepaging

Bei der heute üblichen Abrufstrategie des Paging spricht man auch von Demand Paging, da hier eine Einlagerung nur auf Anforderung erfolgt, also wenn die Daten tatsächlich benötigt werden. Beim sog. Prepaging können dagegen auch Seiten in den Hauptspeicher geholt werden, die noch nicht angefordert wurden, beispielsweise wenn man die Lokalität von Programmen gut einschätzen kann (siehe Lokalitätseigenschaft). Auch Kombinationen von Demand Paging und Prepaging werden in der Praxis eingesetzt: Man kann zum Beispiel beim Holen einer angeforderten Seite gleich die benachbarten Seiten oder sonstige Seiten nach einem bestimmten Algorithmus mit in den Hauptspeicher laden.

Beispiele

Einfaches fiktives Beispiel

Die Adresslänge in diesem Beispiel sei 16 Bit, wobei die oberen 8 Bit die Seitennummer und die unteren 8 Bit der Offset sind. (Die Adresse eines Bytes ergibt sich also = Seitenrahmen * 256 + Offset.)

Seitentabelle

Eintrag	Gültig	Seitenrahmen
0	Nein	–
1	Ja	0x17
2	Ja	0x20
3	Ja	0x08
4	Nein	–
5	Ja	0x10

Zu übersetzende Adressen:

virtuelle Adresse	physische Adresse	Bemerkung
0x083A	ungültig	da die Seitentabelle nur Einträge bis Seite 5 enthält.
0x01FF	0x17FF	Seite 0x01 befindet sich in Seitenrahmen 0x17, also werden die oberen 8 bit der virtuellen Adresse durch 0x17 ersetzt
0x0505	0x1005	Seite 0x05 befindet sich in Seitenrahmen 0x10, also werden die oberen 8 bit der virtuellen Adresse durch 0x10 ersetzt
0x043A	ungültig	da die Seite 0x04 als ungültig markiert wurde.

Reales Beispiel: IA32-Architektur

32-Bit-Paging

Die meisten Architekturen verwenden ein mehrstufiges Paging, um die Seitentabellen kleinzuhalten. Die IA32-Architektur verwendete ursprünglich ein zweistufiges Paging. Die 32 Bit der linearen Adresse werden hierbei wie folgt aufgeteilt:

x86 Paging – 4KiByte Seiten

Bits	Zuordnung
31 ... 22	Index im Seitenverzeichnis (engl. page directory, kurz: PD)
21 ... 12	Index in der Seitentabelle (engl. page table, kurz: PT)
11 ... 0	Offset in der Speicherseite

Das Seitenverzeichnis und jede Seitentabelle bestehen aus 1024 Einträgen zu je 4 Byte und belegen somit jeweils genau eine Speicherseite. Jeder Eintrag hat folgenden Aufbau:

32-Bit-Eintrag im Seitenverzeichnis (Page directory entry)

Bits:	31 ... 12																				11 ... 9			8	7	6	5	4	3	2	1	0
Inhalt:	Bit 31...12 der Basisadresse																				ign.			G	PS	D	A	PCD	PWT	U/S	R/W	P

Bedeutungen

• P – present. Seite ist im RAM vorhanden, wenn Bit auf 1
• R/W – read/write. Schreibzugriffe nur erlaubt, wenn Bit auf 1
• U/S – user/supervisor. Ring-3-Code darf nur auf die Seite zugreifen, wenn Bit auf 1
• PWT und PCD – wird zur Cache-Steuerung benutzt
• A – accessed. Wird von der CPU automatisch gesetzt, sobald auf die Seite zugegriffen wird
• D – dirty. Wird von der CPU automatisch gesetzt, sobald in die Seite geschrieben wurde
• PS – page size. Ist dieses Bit gesetzt, verweist dieser Verzeichniseintrag direkt auf eine 4-MiB-Seite statt auf eine Seitentabelle (siehe #Page Size Extension)
• G – global. Kennzeichnet eine globale Speicherseite

Page-Size Extension

Zur Optimierung großer, zusammenhängender Speicherbereiche (z.B. Framebuffer für Grafikkarten usw.) und um den Verwaltungsaufwand im Speichermanagement des Betriebssystems zu verringern, unterstützen CPUs ab dem Pentium (offiziell dokumentiert ab Pentium Pro) außerdem 4 MiB große Seiten. Dieses Feature wird Page-Size Extension (PSE) genannt. Hierbei markiert ein spezielles Bit im zugehörigen Seitenverzeichnis-Eintrag, dass die zweite Stufe im Paging für diesen Adressbereich umgangen werden soll. Damit geben die Bits 21 bis 0 der logischen Adresse direkt den Offset in der 4 MiB großen Speicherseite an.

Um die Page-size Extension zu aktivieren, muss das Betriebssystem das Bit 4 im Steuerregister CR4 setzen.

Da die 4-MiB-Seiten nur auf „glatten“ Adressen beginnen dürfen, müssen die Bits 12 bis 20 im Seitenverzeichniseintrag stets 0 sein. Dies wurde mit der PSE-36-Erweiterung abgeschafft, indem diese Bits eine neue Bedeutung bekamen:

32-Bit-Eintrag im Seitenverzeichnis mit Page Size Extension

Bits:	31 … 22										21	20 … 17				16 … 13				12	11 … 9			8	7	6	5	4	3	2	1	0
PSE (ab Pentium):	Bit 31…22 der Basisadresse										0									PAT	ign.			G	PS	D	A	PCD	PWT	U/S	R/W	P
PSE-36 (ab Pentium II Xeon)	Bit 31…22 der Basisadresse										0					Bit 35…32				PAT	ign.			G	PS	D	A	PCD	PWT	U/S	R/W	P
PSE-36 (ab AMD K8)	Bit 31…22 der Basisadresse										0	Bit 39…32								PAT	ign.			G	PS	D	A	PCD	PWT	U/S	R/W	P

Die PSE-36-Erweiterung ermöglichte es, ohne großen Änderungsaufwand am Betriebssystemkern, auf mehr als 4 GiB physischen Hauptspeicher zugreifen zu können. Allerdings ist Hauptspeicher jenseits der 4-GiB-Grenze nur über 4-MiB-Seiten ansprechbar.

PSE-36 wurde nur von Windows NT 4.0 verwendet, neue Windows-Versionen und Linux setzen ausschließlich auf PAE.

Physical-Address Extension

Ab dem Pentium Pro ist es möglich, bis zu 2³⁶ Bytes (= 64 GiB) physischen Speicher zu adressieren. Diese Technik wird Physical-Address Extension genannt. Dafür wird das Paging um eine dritte Stufe erweitert. Die obersten beiden Bits der linearen Adresse wählen nun einen aus 4 Einträgen der so genannten page directory pointer table (kurz: PDPT) aus.

Die Einträge in den Tabellen wurden auf 8 Bytes erweitert, jede der Tabellen enthält allerdings nur noch 512 Einträge, so dass die Gesamtgröße der Tabelle wieder bei 4 KiB liegt:

64-Bit-Eintrag in Seitentabelle (Page table entry)

Bits:	63	62 … 52											51 … 32
Inhalt:	NX	reserved											Bit 51…32 der Basisadresse
Bits:	31 … 12																				11 … 9			8	7	6	5	4	3	2	1	0
Inhalt:	Bit 31…12 der Basisadresse																				ign.			G	PAT	D	A	PCD	PWT	U/S	R/W	P

Auch mit PAE ist es möglich, die letzte Adress­übersetzungs­stufe des Pagings zu deaktivieren. Die Bits 20 bis 0 der logischen Adresse bilden dann direkt den Offset einer 2 MiB großen Speicherseite.

x86 Paging, mit PAE

Bits	Zuordnung
	4 KiB Page	2 MiB Page
31 ... 30	Index in der PDPT
29 ... 21	Index im Seitenverzeichnis (engl. page directory, kurz: PD)
20 ... 12	Index in der Seitentabelle (engl. page table, kurz: PT)	Offset in der Speicherseite
11 ... 0	Offset in der Speicherseite

64-Bit-Modus

Mit der Einführung des 64-Bit-Modus beim AMD Athlon 64 wurde dieses Prinzip noch einmal angewendet. Das Paging wurde um eine vierte Stufe erweitert (Page Map Level 4, kurz PML4) und die PDPT wurde von 4 auf 512 Einträge vergrößert, so dass sie genauso groß wie die nachfolgenden Seitentabellen ist.

Neben den bereits im 32-Bit-Modus verfügbaren 4 KiB und 2 MiB großen Seiten sind im 64-Bit-Modus auch 1 GiB große Seiten möglich. Hierbei verweisen die unteren 22 Bits eines Eintrags in der Page-Directory-Pointer Table direkt auf die Startadresse einer 1-GiB-Seite:

x86_64 Paging

Bits	Zuordnung
	4 KiB Page	2 MiB Page	1 GiB Page
63 ... 48	Kopie von Bit 47, als Vorzeichenerweiterung
47 ... 39	Index in der PML4 table (engl. page mapping layer 4)
38 ... 30	Index in der PDPT
29 ... 21	Index im Seitenverzeichnis (engl. page directory, kurz: PD)		30-Bit-Offset
20 ... 12	Seitentabelle (engl. page table, kurz: PT)	21-Bit-Offset
11 ... 0	12-Bit-Offset in der Speicherseite

Nachladen von Seiten in den Arbeitsspeicher (Demand Paging)

Wie oben schon erwähnt, wird der Paging-Mechanismus auch zur virtuellen Speicherverwaltung ausgenutzt, so dass der logische Adressraum größer sein kann als physischer Speicher vorhanden ist. Beim so genannten demand paging müssen nicht alle Teile eines Programms gleich beim Programmstart geladen werden. Sobald der Prozess auf eine nicht geladene Seite zugreift, wird der fehlende Teil der Datei vom Betriebssystem nachgeladen.

Ebenso ist es auf vielen Betriebssystemen möglich, eine beliebige Datei in den logischen Adressraum einblenden zu lassen. Beim Anlegen eines solchen Mappings werden vom Betriebssystem nur die Dateizugriffsrechte geprüft und der nötige Bereich im logischen Adressraum des Prozesses reserviert. Erst wenn der Prozess auf diesen Speicherbereich zugreift (=on demand), werden die betreffenden Teile der Datei geladen und im logischen Adressraum eingeblendet.

Thrashing und Working Set

Diese Technik des Pagings hat jedoch ihre Grenzen. Wenn in einem Rechnersystem zu viele Seitenfehler auftreten, etwa weil ein Programm zu oft wahllos auf verschiedene Speicherbereiche zugreift, dann ist das System überwiegend mit dem Nachladen und Auslagern von Seiten beschäftigt. Der Prozessor verharrt die meiste Zeit im Wartezustand, die verfügbare Rechenleistung ist deutlich herabgesetzt. Dieser Zustand wird auch als Thrashing (engl. wörtlich: Dreschen) bezeichnet.

Um Thrashing zu vermeiden, darf der Arbeitsspeicher im Verhältnis zum Auslagerungsspeicher nicht zu klein sein. Zu jedem gegebenen Zeitpunkt sollte mindestens einer der Prozesse, die das System zu verarbeiten hat, vom Prozessor bearbeitet werden können, das heißt: Seine Daten oder Programmbefehle, die aktuell bearbeitet werden, befinden sich im Arbeitsspeicher. In diesem Betriebszustand wartet der Prozessor nicht auf das Nachladen von Seiten, sondern arbeitet an einem Prozess, während parallel für andere Prozesse Seiten nachgeladen werden. Außerdem sollten Programme auf ihre Daten möglichst lokal zugreifen und wahlfreie Zugriffe auf ständig wechselnde Speicherseiten vermeiden.

Entscheidend sind dabei folgende Größen:

• t: Die Zeit, die der Prozessor braucht, um auf eine Speicherstelle zuzugreifen
• T: Die Zeit, die benötigt wird, um eine Seite nachzuladen
• s: Der Anteil an Seiten, der sich im Arbeitsspeicher befindet, im Verhältnis zur Gesamtzahl aller für die Programmausführung benötigten Seiten (0 < s ≤ 1)
• p(s): Die Wahrscheinlichkeit eines Seitenfehlers, abhängig von s

Damit Thrashing vermieden wird, muss p(s) ≤ t/T sein. Der minimale Anteil w an Seiten, der sich im Arbeitsspeicher befinden muss, wird bestimmt durch die Gleichung

• p(w) = t/T.

Er wird als Working Set (Arbeitsmenge) bezeichnet.

Wären die Zugriffe auf den Speicher gleich verteilt, so wäre p(s) = 1 - s. Jedoch treten Speicherzugriffe meist lokal gehäuft auf: In den meisten Fällen folgt ein Programmschritt dem nächsten. Auch die Daten werden meist in Reihen bearbeitet, beispielsweise wenn Rechenoperationen auf ganze Tabellen angewendet werden. Deshalb ist die Wahrscheinlichkeit sehr hoch, dass der nächste Programmschritt und das nächste benötigte Datenelement sich auf derselben Seite befinden wie der gerade verarbeitete Schritt und das gerade verarbeitete Element.

Auf der anderen Seite ist das Verhältnis T/t typischerweise sehr groß: RAM ist mehr als 100-mal so schnell wie Plattenspeicher.

Experimentelle Messungen und Berechnungen, die bereits in den 1960er Jahren durchgeführt wurden, ergeben unter diesen Bedingungen für w einen Wert von nicht wesentlich weniger als 0,5. Das bedeutet, dass der Auslagerungsspeicher kaum größer als der Arbeitsspeicher sein darf.

In der Praxis wird z. B. unter UNIX-Betriebssystemen für die meisten Anwendungsfälle eine Größe des Auslagerungsspeichers vom Zwei- bis Dreifachen des Arbeitsspeichers empfohlen (abhängig davon, ob das jeweilige System den Auslagerungsspeicher zusätzlich zum Arbeitsspeicher oder den Arbeitsspeicher als echte Teilmenge des Auslagerungsspeichers verwaltet).

Seitenersetzungsstrategien

Die Leistung eines Pagingsystems ist davon abhängig, welche Seiten im Hauptspeicher man beim Nachladen neuer Seiten verdrängt. Wenn man Seiten verdrängt, die wenig später erneut gebraucht werden, dann erzeugt man Aufwand für zusätzliche Nachladevorgänge.

Folgende Verfahren sind bekannt und untersucht:

First In – First Out (FIFO)

Die älteste Seite wird ersetzt. Diese Strategie ist ineffizient, da die älteste Seite durchaus eine Seite mit sehr häufigen Zugriffen sein kann.

Least recently used (LRU)

Die am längsten nicht genutzte Seite wird ausgelagert.

Least frequently used (LFU)

Ein Zähler pro Seite zählt mit, wie häufig auf diese Seite zugegriffen wurde. Es wird diejenige Seite entfernt, auf die am wenigsten zugegriffen wurde.

Unversehrtheit der Speicherseite

Wird eine Speicherseite ausgelagert, deren Inhalt sich gegenüber dem Inhalt auf der Festplatte geändert hat, muss die Änderung zurück auf die Festplatte geschrieben werden. Ansonsten entfällt das Zurückschreiben und man spart sich einen teuren I/O-Zugriff.

Not recently used (NRU)

Seiten, die innerhalb eines Zeitintervalls nicht benutzt und nicht modifiziert wurden, werden bevorzugt ausgelagert; danach Seiten, die entweder nicht benutzt oder nicht modifiziert wurden und als letzte Gruppe erst Speicherseiten, die benutzt und modifiziert wurden.

Nächster Zugriff (nach László Bélády)

Für jede Seite wird ermittelt, wie viele Instruktionen ausgeführt werden, bis auf die Seite zugegriffen wird. Es wird die Seite mit der größten Anzahl ersetzt. Diese Strategie ist die theoretisch optimale Strategie; sie kann allerdings ohne genaue Kenntnis über den Programmablauf nicht implementiert werden.

Literatur

• Albert Achilles: Betriebssysteme. Eine kompakte Einführung mit Linux. Springer: Berlin, Heidelberg, 2006.
• Uwe Baumgarten, Hans-Jürgen Siegert: Betriebssysteme. Eine Einführung. 6., überarbeitete, aktualisierte und erweiterte Auflage, Oldenbourg Verlag: München, Wien, 2007.
• Peter Mandl: Grundkurs Betriebssysteme. Architekturen, Betriebsmittelverwaltung, Synchronisation, Prozesskommunikation, Virtualisierung. 4. Auflage, Springer Vieweg: Wiesbaden, 2014.
• Andrew S. Tanenbaum: Moderne Betriebssysteme. 3., aktualisierte Auflage. Pearson Studium, München u.a., 2009, ISBN 978-3-8273-7342-7.
• Klaus Wüst: Mikroprozessortechnik. Grundlagen, Architekturen, Schaltungstechnik und Betrieb von Mikroprozessoren und Mikrocontrollern. 4. Auflage, Vieweg+Teubner: Wiesbaden, 2011.