Paging

Als Paging (vgl. engl. page Speicherseite) oder deutsch Kachelverwaltung^[1] bezeichnet man die Methode der Arbeitsspeicher-Verwaltung per Seitenadressierung durch Betriebssysteme.

Gelegentlich wird der Begriff Paging synonym mit der gesamten virtuellen Speicherverwaltung gebraucht. Dieser Sprachgebrauch ist jedoch unpräzise, da das Paging nur einen – wenn auch zentralen – Aspekt der virtuellen Speicherverwaltung ausmacht.

Funktionsweise

Beim Paging werden logische Adressen und physische Adressen unterschieden. Der logische Adressraum beschreibt die Organisation des Hauptspeichers aus Programmsicht. Der physische Adressraum ist durch den tatsächlich verfügbaren Arbeitsspeicher gegeben.

Auf vielen Rechnerarchitekturen ist zwischen der CPU und dem Arbeitsspeicher noch ein Speichercontroller geschaltet, der weitere Adressumsetzungen vornehmen kann, etwa für die Aufteilung auf die einzelnen Speicherbänke, das Einblenden des Speichers von externen Geräten (Grafikspeicher, Memory-mapped I/O) usw. Diese zusätzlichen Adressumsetzungen sind nicht Bestandteil des Pagings.

Der logische Adressraum wird in gleich große Stücke unterteilt, die man als Seiten (engl. „pages“) bezeichnet. Auch der physische Adressraum ist derart unterteilt. Hier nennt man die einzelnen Stücke Seitenrahmen oder auch Kacheln (engl. “(page) frames”). Eine Seite und der zugehörige Seitenrahmen haben i.d.R die gleiche Größe; alternative Techniken implementieren Paging in der Art, dass die Seitengröße einem ganzzahligen Vielfachen der Größe der Seitenrahmen entspricht - auch hierbei kommt es dadurch nicht zur Fragmentierung des Hauptspeichers. Um Seiten und Seitenrahmen einander zuordnen zu können, wird eine Seitentabelle verwendet. Es existiert für jeden Prozess eine eigene Seitentabelle. Der logische Adressraum ist in der Regel zusammenhängend, während im physischen Adressraum die logisch benachbarten Seiten in weit voneinander entfernt liegenden Seitenrahmen abgelegt werden können. Die Reihenfolge der Seitenrahmen ist beliebig.

Seitenfehler

Auch der logische Adressraum kann "Lücken" haben. Dies sind Seiten, die auf keinen Seitenrahmen abgebildet werden. Meist existiert dafür ein spezielles Flag in der Seitentabelle oder ein bestimmter Seitenrahmen ist für diesen Zweck reserviert. Sobald ein Programm auf eine solche Seite zugreift, wird vom Prozessor automatisch ein "page fault" ausgelöst, dessen Behandlung vom Betriebssystem übernommen wird. Hierbei gibt es zwei generelle Ursachen:

1. Die Seite ist nur vorübergehend nicht vorhanden, etwa weil sie gerade ausgelagert worden ist oder der Prozess das erste Mal auf diese Seite zugreift. Das Betriebssystem lädt die betreffende Seite aus dem Hintergrundspeicher, aktualisiert die Seitentabelle und setzt das Programm an der Stelle, die den Seitenfehler verursacht hat, fort.
2. Die Seite ist dauerhaft nicht existent, der Prozess hat auf eine nicht erlaubte logische Adresse zugegriffen. In diesem Fall wird der Prozess vom Betriebssystem mit einer Fehlermeldung beendet. Die historisch bedingte Bezeichnung für diesen Fehler ist "Segmentation fault" oder "General protection fault".

Adressberechnung beim Paging

In der Terminologie der obigen Grafik entspricht eine logische Speicheradresse der virtuellen Adresse. Der physische Speicher heißt hier reale Adresse. Man entnimmt der Grafik, dass sich die physische Speicheradresse sehr einfach aus zwei Teilen berechnet: Der erste Teil wird der Seitentabelle entnommen, der zweite Teil der virtuellen Adresse. Dabei handelt es sich um zwei Binärzahlen. Werden diese konkateniert, so ergibt sich eine neue Binärzahl, die genau die physische Speicheradresse ist. Derartige Berechnungen werden von der Memory Management Unit ausgeführt.

Ein Puffer kann hier einen Teil der Adressabbildung bereithalten, so dass die Zugriffszeiten optimiert werden können. Dieser Puffer heißt Translation Lookaside Buffer.

Einfaches fiktives Beispiel

Die Adresslänge in diesem Beispiel sei 16 Bit, wobei die unteren 8 Bit der Offset und die oberen 8 Bit die Seitennummern sind.

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

Aufbau der Seitentabellen

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

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

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
• PAT — …
• G — global. Kennzeichnet eine globale Speicherseite

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.

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.

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 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. ^[2] 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. Erfreulicherweise treten die Speicherzugriffe jedoch 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.

CLIMB

Wird eine Seite, die bereits im Speicher steht, referenziert, so steigt sie um eine Position in einer Ordnung auf. Ersetzt wird immer die unterste Seite in dieser Ordnung.

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

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 ausgewählt. Diese Strategie ist die theoretisch optimale Strategie; sie kann allerdings ohne genaue Kenntnis über den Programmablauf nicht implementiert werden.

Siehe auch

• Memory Management Unit
• Seitenfehler
• Segmentierung (Speicherverwaltung)
• Buddy-Speicherverwaltung
• Speicherseite
• Swapping
• Adressraum
• Cache

Einzelnachweise

1. ↑ RabbitMQ 2.0.0 unterstützt aktuellen AMQP-Standard – Artikel bei Heise Developer, vom 26. August 2010
2. ↑ Die Ausführungen in diesem Abschnitt beruhen auf: Per Brinch Hansen: Operating System Principles. Englewood Cliifs, NJ, 1973: Prentice Hall. S. 185–191