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.[1]
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. Die Übersetzung von logischen in physische Adressen wird von der Speicherverwaltungseinheit (MMU) erledigt, die außerdem für den – vom Paging unabhängigen – Speicherschutz zuständig ist. Ebenfalls nicht Bestandteil des Pagings ist eine weitere Adressumsetzung, die im Speichercontroller stattfindet und für die Aufteilung der Speicherbänke und das Einblenden des Speichers von externen Geräten (Grafikspeicher, Memory-mapped I/O usw.) verantwortlich ist.
Beim Paging wird der logische Adressraum 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 zu externer Fragmentierung des Hauptspeichers. Um (logische) Seiten und (reale) Seitenrahmen einander zuordnen zu können, wird eine Tabelle 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 also beliebig.
Seitenfehler
Seiten des logischen Adressraums können auch auf keinem realen Seitenrahmen abgebildet sein. Meist existiert dafür ein spezielles Flag in der Seitentabelle oder eine bestimmte Seitenrahmennummer ist für diesen Zweck reserviert. Sobald ein Programm auf eine nicht verfügbare Seite zugreift, wird vom Prozessor automatisch ein „page fault“ ausgelöst, dessen Behandlung vom Betriebssystem übernommen wird. Hierbei 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. Das Betriebssystem lädt den betreffenden Seitenrahmen aus dem Hintergrundspeicher, aktualisiert die Seitentabelle und setzt das Programm an der Stelle fort, an welcher der Seitenfehler aufgetreten ist.
- Die Seite ist ungültig, der Prozess hat auf eine ihm nicht erlaubte logische Adresse zugegriffen. Auch im virtuellen Adressraum muss bei den meisten Betriebssystemen ein Prozess Arbeitsspeicher vom Betriebssystem anfordern, bevor er ihn verwenden darf. Bei Zugriff auf nicht freigegebene Adressen 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 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:
| 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.[2]
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:
| 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 236 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übersetzungsstufe des Pagings zu deaktivieren. Die Bits 20 bis 0 der logischen Adresse bilden dann direkt den Offset einer 2 MiB großen Speicherseite.
| 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:
| 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. [3] 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.
Einzelnachweise
- ↑ Verwendung Begriff "Kachelverwaltung":
- Karlsruher Institut für Technologie, Prüfung, abgerufen am 1. September 2014
- Uni Ulm, Netzwerktreiber-Projekt, abgerufen am 1. September 2014
- RabbitMQ 2.0.0 unterstützt aktuellen AMQP-Standard – Artikel bei Heise Developer, vom 26. August 2010
- ↑ [1] (PDF)
- ↑ Die Ausführungen in diesem Abschnitt beruhen auf: Per Brinch Hansen: Operating System Principles. Englewood Cliifs, NJ 1973: Prentice Hall. S. 185–191.