Seitenverwaltung und virtueller Speicher

Ein Programm verwendet virtuelle Adressen. Der physische Speicher hält die Bytes in Seitenrahmen. Die Seitenverwaltung unterteilt den virtuellen Adressraum in gleich große Seiten und den physischen Speicher in gleich große Seitenrahmen. Das Betriebssystem kann jede Seite in jedem freien Seitenrahmen ablegen. Seite 0 könnte Seitenrahmen 12 belegen und Seite 1 den Seitenrahmen 3; das Programm sieht weiterhin aufeinanderfolgende virtuelle Adressen.

Das beseitigt externe Fragmentierung bei der Zuweisung einzelner Seiten. Bei Segmenten variabler Größe kann eine Anfrage scheitern, weil der freie Speicher in zu kleine Lücken aufgeteilt ist. Bei der Seitenverwaltung passt eine Seite immer in einen freien Seitenrahmen. Ein dünn besetzter Adressraum kann eine große Lücke zwischen Heap und Stack lassen, ohne dafür physische Seitenrahmen zu reservieren.

Ungenutzten Platz innerhalb von Seiten berechnen

Bei der Seitenverwaltung entsteht weiterhin interne Fragmentierung. Ein Bereich muss ganze Seiten belegen, auch wenn seine letzte Seite teilweise leer ist. Ein Bereich von 9.000 Byte benötigt drei 4 KiB große Seiten: Zwei Seiten nehmen 8.192 Byte auf, sodass 808 Byte für die dritte bleiben. Die Zuweisung belegt 12.288 Byte, wovon 3.288 Byte ungenutzt sind. KiB bedeutet 1.024 Byte, MiB bedeutet 1.048.576 Byte. Manche Bücher verwenden KB und MB für diese binären Größen.

Die Adresse in Felder aufteilen

Eine Adresse bezeichnet sowohl eine Seite als auch ein Byte innerhalb dieser Seite. Bei einer Seitengröße von $2^k$ Byte bilden die niederwertigen $k$ Bit den Offset. Die übrigen höherwertigen Bits bilden die virtuelle Seitennummer, kurz VPN. Eine 32-Bit-Adresse hat bei 4 KiB großen Seiten 12 Offsetbits und 20 VPN-Bits. In diesem Adressraum gibt es $2^{20}$ mögliche virtuelle Seiten.

Bei 0x00403A7C ergeben die letzten drei Hexadezimalstellen den Offset 0xA7C, weil jede Hexadezimalstelle vier Bit darstellt. Die ersten fünf Stellen ergeben die VPN 0x00403. Diese Abkürzung funktioniert hier, weil die Feldgrenze zwischen Hexadezimalstellen liegt. Zähle bei einer anderen Seitengröße die Bits, bevor du den geschriebenen Hexadezimalwert aufteilst.

Die Dezimalrechnung liefert dasselbe Ergebnis:

Dabei ist $P$ die Seitengröße in Byte. Bei Seiten mit 1.024 Byte hat die virtuelle Adresse 5.000 die VPN 4 und den Offset 904. Vier vollständige Seiten umfassen 4.096 Byte; die übrigen 904 Byte bestimmen die Position der Adresse innerhalb von Seite 4. Offsets beginnen bei null, die Offsets dieser Seite reichen also von 0 bis 1.023.

Die Übersetzung ersetzt die VPN durch eine physische Seitenrahmennummer. Den Offset übernimmt sie unverändert: Byte 904 einer virtuellen Seite ist Byte 904 ihres Seitenrahmens. Die Seitennummer allein ist keine Byteadresse. Multipliziere eine Seitenrahmennummer mit der Seitengröße, um die Startadresse des Seitenrahmens zu finden, und addiere dann den Offset.

Eine Seitengröße wählen

Größere Seiten verringern die Anzahl der Abbildungen und ermöglichen, dass jede zwischengespeicherte Übersetzung mehr Bytes abdeckt. Sie verschwenden aber auch mehr Platz in teilweise genutzten Seiten und übertragen beim Laden einer Seite mehr Daten. Eine übliche Basisseitengröße ist 4 KiB; andere Systeme verwenden 16 KiB oder 64 KiB. x86-64 unterstützt auch große Abbildungen wie 2 MiB große Seiten.

Eine Seitentabelle erfasst die Abbildungen eines Prozesses. In einer linearen Seitentabelle indiziert die VPN ein Array: Eintrag 4 beschreibt die virtuelle Seite 4. Jeder Prozess hat eine eigene Tabelle, sodass dieselbe virtuelle Adresse in verschiedenen Prozessen auf unterschiedliche physische Bytes verweisen kann. Bei einem Kontextwechsel wählt das Betriebssystem über ein Seitentabellenbasisregister die Tabelle des neuen Prozesses aus.

Zustand und Berechtigungen eines Eintrags lesen

Ein Seitentabelleneintrag, kurz PTE, enthält eine physische Seitenrahmennummer (PFN) und Steuerinformationen. Im Lehrmodell gibt ein Gültigkeitsbit an, dass die Seite zum Adressraum gehört; ein Präsenzbit gibt an, dass ihr Inhalt im physischen Speicher liegt. Schutzbits steuern das Lesen, Schreiben, Ausführen und den Benutzerzugriff. Ein Änderungsbit erfasst Schreibzugriffe seit seinem letzten Zurücksetzen. Ein Referenzbit erfasst die Nutzung seit seinem letzten Zurücksetzen.

Dies sind begriffliche Rollen, keine Zusage identischer Hardwarestrukturen. Auf x86 gibt es kein separates Gültigkeitsbit in einem PTE. Ist das Präsenzbit nicht gesetzt, unterscheidet das Betriebssystem anhand eigener Aufzeichnungen eine ungenutzte Adresse von einer gültigen, andernorts gespeicherten Seite. Auf x86 setzt die Hardware das Referenz- und das Änderungsbit; das Betriebssystem verwaltet sie und setzt sie zurück.

Den Eintrag und das Byte finden

So übersetzt du eine Adresse mit einer linearen Tabelle:

1. Teile die virtuelle Adresse in VPN und Offset auf.
2. Finde den Eintrag bei $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{e}+\mathrm{V}\mathrm{P}\mathrm{N}\times \mathrm{P}\mathrm{T}\mathrm{E}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}$.
3. Prüfe, ob die Abbildung existiert, präsent ist und diesen Zugriff erlaubt.
4. Bilde die physische Adresse aus $\mathrm{P}\mathrm{F}\mathrm{N}\times \mathrm{p}\mathrm{a}\mathrm{g}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}+\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}\mathrm{t}$.
5. Lies oder schreibe das Byte an dieser physischen Adresse.

Bei Seiten mit 1.024 Byte ergibt die virtuelle Adresse 5.000 die VPN 4 und den Offset 904. PTE 4 sei präsent, erlaube den angeforderten Lesezugriff und enthalte PFN 9. Seitenrahmen 9 beginnt bei 9.216, die physische Byteadresse ist also 10.120. Die Adresse des Tabelleneintrags wird separat berechnet: Belegen Einträge je 4 Byte, liegt PTE 4 um 16 Byte hinter der Tabellenbasis.

Ein Hexadezimalbeispiel: Bei 4 KiB großen Seiten wird 0x00403A7C in VPN 0x403 und Offset 0xA7C aufgeteilt. Enthält die erlaubte Abbildung PFN 0x1F2B5, lautet die physische Adresse 0x1F2B5A7C. Der PTE liegt bei Basis + 0x403 × 4 = Basis + 0x100C. Das Anhängen des Offsets bildet eine Datenadresse; die Multiplikation der VPN mit der Eintragsgröße ermittelt den PTE. Diese beiden Adressen dienen unterschiedlichen Zwecken.

Eine fehlgeschlagene Prüfung löst eine Ausnahme aus. Das Betriebssystem kann eine gültige, nicht im Speicher befindliche Seite einlagern, nullinitialisierten Speicher bereitstellen oder eine andere zulässige Abbildung korrigieren. Eine unzulässige Adresse oder ein verbotener Zugriff verursacht normalerweise eine Speicherzugriffsverletzung. Eine präsente Seite kann einen Schreibzugriff dennoch abweisen, wenn ihr Schutz das Schreiben verbietet.

Tabellenplatz und Speicherlesezugriffe zählen

Lineare Tabellen sind selbst für kleine Prozesse aufwendig. Bei virtuellen 32-Bit-Adressen und 4 KiB großen Seiten benötigt jede Tabelle 1.048.576 Einträge. Bei je 4 Byte sind das 4 MiB pro Prozess, einschließlich der Einträge für ungenutzte virtuelle Seiten. Hundert Prozesse benötigen allein für diese Tabellen 400 MiB.

Außerdem fügen sie jedem Speicherzugriff eine Suche hinzu. In einem einfachen Modell ohne Übersetzungscache liest der Prozessor einen PTE und dann die angeforderten Daten: zwei Speicherzugriffe. Gemeinsame Nutzung ist dennoch möglich: Zwei Prozesse können ihre getrennten virtuellen Seiten gezielt auf dieselbe PFN abbilden, etwa bei schreibgeschütztem Programmcode.

Ein Translation Lookaside Buffer, kurz TLB, ist ein kleiner Hardwarecache für Adressübersetzungen in der Speicherverwaltungseinheit (MMU). Er enthält kürzlich verwendete VPN-zu-PFN-Abbildungen und Zugriffsinformationen. Er speichert Übersetzungen zwischen, während ein Datencache Programmbytes enthält. Ein Programm kann in einem Cache einen Fehlzugriff und im anderen einen Treffer erzielen.

Treffer und Fehlzugriffe verfolgen

Bei einem TLB-Treffer erhält die MMU die PFN aus dem zwischengespeicherten Eintrag, prüft die Zugriffsberechtigungen und kombiniert die PFN mit dem unveränderten Offset. Sie muss die Seitentabelle nicht lesen. Auch bei einem Treffer muss der Speicherschutz durchgesetzt werden. Das Gültigkeitsbit des TLB gibt an, dass ein zwischengespeicherter Eintrag nutzbar ist; es sagt nicht aus, ob eine virtuelle Seite zum Adressraum des Prozesses gehört.

Bei einem TLB-Fehlzugriff muss das System die Übersetzung in der Seitentabelle suchen. Ist die Seite präsent und der Zugriff erlaubt, trägt es die Übersetzung ein und schließt den Zugriff ab oder wiederholt ihn. Ein Lesezugriff auf den Massenspeicher ist nicht nötig. Meldet die Tabelle dagegen eine fehlende Abbildung oder einen verbotenen Zugriff, muss das Betriebssystem einen Seitenfehler behandeln. Ein TLB-Fehlzugriff allein ist kein Seitenfehler.

Wiederverwendung anhand der Lokalität vorhersagen

TLBs können weit weniger Einträge aufnehmen, als es virtuelle Seiten gibt. Dennoch funktionieren sie gut, weil Programme Lokalität aufweisen. Räumliche Lokalität bedeutet, dass benachbarte Adressen zeitlich nah beieinander genutzt werden. Sobald eine Übersetzung zwischengespeichert ist, können viele Adressen innerhalb dieser Seite sie nutzen. Zeitliche Lokalität bedeutet, dass kürzlich genutzte Adressen wahrscheinlich erneut genutzt werden, etwa bei den Befehlen einer Schleife.

Betrachte 16.384 Ganzzahlen zu je vier Byte, die aufeinanderfolgend in einem an einer Seitengrenze ausgerichteten Array gespeichert sind. Bei 4 KiB großen Seiten enthält jede Seite 1.024 Ganzzahlen, das Array umfasst also 16 Seiten. Bei anfänglich leerem TLB und ohne andere störende Übersetzungen verursacht die erste Ganzzahl auf jeder Seite einen Fehlzugriff. Die nächsten 1.023 auf dieser Seite erzielen Treffer. Insgesamt gibt es 16 Fehlzugriffe und 16.368 Treffer, was eine Trefferquote von etwa 99,9 % ergibt.

Die Zugriffsreihenfolge verändert dieses Ergebnis. In C speichert int a[1024][1024] die Zeilen aufeinanderfolgend. Nimm Ganzzahlen zu je vier Byte, eine Ausrichtung an einer Seitengrenze, 4 KiB große Seiten und einen LRU-TLB mit 64 Einträgen an. Jede Zeile belegt eine Seite. Beim zeilenweisen Durchlaufen entsteht ein Fehlzugriff pro Zeile, also 1.024 Fehlzugriffe. Beim spaltenweisen Durchlaufen werden 1.024 verschiedene Seiten besucht, bevor wieder die erste erreicht wird. Deren Übersetzung wurde bereits verdrängt, sodass alle 1.048.576 Arrayzugriffe fehlschlagen. Die Größe des Arrays bleibt gleich; die Anzahl der Zugriffe bis zur Wiederverwendung ändert sich.

Durchschnittlichen Aufwand für Treffer und Fehlzugriffe berechnen

Das Zeitmodell muss angeben, wie viel Zeit ein Treffer und ein Fehlzugriff kosten. Der Speicher benötige 100 ns, die TLB-Abfrage keine zusätzliche Zeit und ein Fehlzugriff bei einer linearen Tabelle einen zusätzlichen Lesezugriff auf den Speicher. Ein Treffer kostet 100 ns und ein erfolgreich behandelter Fehlzugriff 200 ns. Bei einer Trefferquote von 98 %:

Dieser Durchschnitt enthält in beiden Fällen den abschließenden Datenzugriff. Würde nur der zusätzliche Lesezugriff für den PTE als gesamter Aufwand des Fehlzugriffs gezählt, wäre der Gesamtaufwand zu niedrig angesetzt. Bei mehrstufigen Tabellen kann ein Fehlzugriff mehrere Tabellenlesezugriffe erfordern, sodass Lokalität noch wichtiger wird.

Ein TLB-Fehlzugriff erfordert die Suche nach einer Übersetzung, doch Architekturen teilen diese Arbeit unterschiedlich auf. Bei einem hardwareverwalteten TLB, wie auf x86 und ARM, durchläuft die MMU die Seitentabelle ausgehend von der gewählten Tabellenwurzel. Die Hardware legt das Format fest, das sie durchlaufen kann. Ist die Abbildung nutzbar, füllt sie den Übersetzungscache, ohne bei einem gewöhnlichen Fehlzugriff eine Behandlungsroutine des Betriebssystems aufzurufen.

Ein softwareverwalteter TLB, wie er in klassischen MIPS- und SPARC-Entwürfen genutzt wird, löst bei einem Fehlzugriff eine Ausnahme aus. Eine Behandlungsroutine des Betriebssystems findet die Abbildung und trägt sie mit privilegierten Befehlen ein. Das gibt dem Betriebssystem mehr Freiheit beim Aufbau seiner Tabellen. Bei der Rückkehr aus dieser Ausnahme wird der Befehl mit dem Fehlzugriff wiederholt; bei der Rückkehr aus einem Systemaufruf wird normalerweise nach dem Aufruf fortgefahren.

Die Nachfüllroutine erreichbar halten

Die Behandlungsroutine für Fehlzugriffe benötigt zuverlässigen Zugriff auf ihre eigenen Befehle und Daten. Löst die Behandlung eines Fehlzugriffs innerhalb der Routine sofort dieselbe Art eines unbehandelten Fehlzugriffs aus, kann der Fortschritt ausbleiben. Entwürfe vermeiden dies durch nicht übersetzten Speicher oder dauerhaft fest zugewiesene Übersetzungen für den wesentlichen Code und die Daten der Routine.

Den richtigen Adressraum wählen

Kontextwechsel bringen ein weiteres Problem mit sich. Prozess A könnte VPN 7 auf Seitenrahmen 20 abbilden, während Prozess B VPN 7 auf Seitenrahmen 90 abbildet. Bliebe der nicht gekennzeichnete Eintrag von A nach dem Wechsel zu B erhalten, würde er B zum falschen Seitenrahmen führen. Das Laden der Seitentabellenwurzel von B allein macht eine zwischengespeicherte Abbildung ohne Kennung nicht sicher.

Eine Lösung ist, beim Wechsel die betreffenden TLB-Einträge zu invalidieren. Ihre Gültigkeitsbits werden zurückgesetzt, sodass der neue Prozess sie erneut füllen muss. Eine andere Lösung versieht Einträge mit einer Adressraumkennung (ASID). Bei der Suche müssen dann sowohl die virtuelle Seite als auch ihre Adressraumkennung übereinstimmen. Auf x86 heißt diese Kennung Prozesskontextkennung, kurz PCID. Einträge mehrerer Adressräume können im Cache bleiben, während die Hardware nur die zum aktuellen Kontext gehörenden auswählt. Die erneute Vergabe von Kennungen muss weiterhin so verwaltet werden, dass ein alter Eintrag nicht mit einem neuen Adressraum verwechselt werden kann.

Geänderte Abbildungen invalidieren

Auch eine Änderung eines PTE macht eine zwischengespeicherte Übersetzung ungültig. Das Betriebssystem entferne die Schreibberechtigung im Speicher, lasse aber einen beschreibbaren TLB-Eintrag bestehen. Der Prozessor könnte über diesen alten Eintrag weiterhin Schreibzugriffe erlauben. Das Betriebssystem muss betroffene Übersetzungen invalidieren. Auf einem Rechner mit mehreren Kernen muss jeder Kern mitwirken, der die Abbildung zwischengespeichert haben könnte. Diese Koordination heißt TLB-Shootdown.

Die Reichweite der Übersetzungen berechnen

Neben der Korrektheit ist auch die Kapazität entscheidend. Die TLB-Reichweite ist die Speichermenge, die durch die zwischengespeicherten Übersetzungen abgebildet wird:

Ein TLB mit 64 Einträgen erreicht bei 4 KiB großen Seiten 256 KiB und bei 2 MiB großen Seiten 128 MiB. Die Reichweite beschreibt den durch Abbildungen abgedeckten Bereich, nicht die Kapazität des physischen Speichers. Reale Prozessoren können für verschiedene Seitengrößen getrennte TLB-Kapazitäten haben; diese Rechnung vergleicht daher eine feste Anzahl von Einträgen.

Ist ein TLB voll, ersetzt er eine Übersetzung. LRU bevorzugt kürzlich genutzte Einträge; die zufällige Ersetzung wählt ohne Berücksichtigung der letzten Nutzung. Ein wiederholter Durchlauf über eine Seite mehr, als hineinpasst, ist für LRU ungünstig, weil jede Übersetzung unmittelbar vor ihrer erneuten Nutzung verdrängt wird.

Eine lineare Seitentabelle reserviert einen Eintrag für jede mögliche virtuelle Seite. Die meisten Prozesse nutzen nur einen kleinen Teil ihres Adressraums: Code und Heap liegen nahe dem einen Ende, der Stack nahe dem anderen, und eine große Lücke trennt sie. Eine Tabelle mit Millionen ungültiger Einträge verbraucht dennoch Speicher. Um diesen Aufwand zu verringern, muss die Seitengröße, die Tabellenorganisation oder beides geändert werden.

Die Seitenanzahl verringern

Größere Seiten verringern die Anzahl der VPNs. Bei einem 32-Bit-Adressraum und 16 KiB großen Seiten bilden 14 Bit den Offset und 18 Bit die VPN. Eine lineare Tabelle benötigt dann 262.144 Einträge. Bei je 4 Byte belegt sie 1 MiB, gegenüber 4 MiB bei 4 KiB großen Seiten. Das spart Tabellenplatz, obwohl der Prozess weiterhin 4 GiB virtuelle Bytes adressieren kann.

Der Aufwand verlagert sich. Bei einer kleinen Zuweisung kann mehr Platz auf der letzten Seite verschwendet werden, und beim Einlagern einer Seite werden mehr Bytes übertragen. Eine größere Seitengröße unterscheidet nicht zwischen einem dicht genutzten Teil des Adressraums und einer ungenutzten Lücke; sie verringert lediglich für beide die Anzahl der Einträge.

Lücken mit getrennten Segmenttabellen aussparen

Eine Kombination aus Segmentierung und Seitenverwaltung gibt Code, Heap und Stack eigene Seitentabellen. Jedes Segment hat eine Tabellenbasis und eine Schranke für seine Seitennummern. Die Lücke zwischen den Segmenten benötigt keine Einträge. Die Übersetzung wählt zuerst das Segment aus, prüft seine Schranke und sucht dann die Seite innerhalb dieses Segments.

Dieser Ansatz setzt eine brauchbare Aufteilung in Segmente voraus. Seine Tabellen können unterschiedlich lang sein und zusammenhängenden physischen Speicher benötigen, wodurch für die Tabellen selbst erneut externe Fragmentierung entsteht. Die Datenseiten des Prozesses bleiben gleich groß; die fragmentierten Objekte sind nun die Seitentabellen variabler Größe.

Stattdessen physische Seitenrahmen indizieren

Eine invertierte Seitentabelle ändert, was ein Eintrag beschreibt. Sie hat für den gesamten Rechner einen Eintrag pro physischem Seitenrahmen und erfasst den belegenden Prozess und die VPN. Bei 16 GiB physischem Speicher und 4 KiB großen Seitenrahmen benötigt sie 4.194.304 Einträge, unabhängig davon, wie viele Prozesse große virtuelle Adressräume haben. Um aus dieser Anzahl die Gesamtgröße in Byte zu berechnen, wird noch die Eintragsgröße benötigt.

Eine gewöhnliche Tabelle nutzt die VPN direkt als Arrayindex. Eine invertierte Tabelle sucht stattdessen nach dem Paar aus Adressraumidentität und VPN. Eine Hashstruktur kann dies effizient machen, bei Kollisionen können aber zusätzliche Suchschritte nötig sein. Gemeinsam genutzte Seitenrahmen erfordern ebenfalls eine zusätzliche Behandlung, weil ein Seitenrahmen mehrere virtuelle Namen haben kann. Hashbasierte Seitentabellen, wie sie in PowerPC-Systemen verwendet wurden, nutzen verwandte Suchprinzipien; eine hashbasierte Tabelle ist nicht zwangsläufig eine streng invertierte Tabelle mit einem Eintrag pro Seitenrahmen.

Tabellen nach genutztem Bereich zuweisen

Mehrstufige Seitentabellen behalten die indizierte Suche bei und weisen Tabellenseiten niedrigerer Stufen nur dort zu, wo Abbildungen benötigt werden. Ein Eintrag einer höheren Stufe kann einen ganzen ungenutzten Bereich kennzeichnen, ohne dessen Tabelle niedrigerer Stufe zuzuweisen. Dies ist die übliche Lösung auf modernen Systemen. Bei dünn besetzten Adressräumen ist die Ersparnis am größten, während ein TLB-Fehlzugriff mehr Suchschritte erfordert.

Vergleiche die Verfahren anhand der Frage, was ihre Größe bestimmt. Eine lineare Tabelle wächst mit der Anzahl virtueller Seiten pro Prozess. Eine invertierte Tabelle wächst mit der Anzahl physischer Seitenrahmen im System. Eine Hierarchie wächst mit den für die Abbildungen benötigten Tabellenzweigen. Keine dieser Anzahlen entspricht der Anzahl der Bytes von Programmdaten, die gerade im Speicher liegen.

Eine zweistufige Seitentabelle unterteilt eine große lineare Tabelle in seitengroße Stücke. Ein Seitenverzeichnis zeigt auf diese Stücke. Das Verzeichnis wird zugewiesen, eine Seitentabellenseite der unteren Stufe aber nur dann, wenn ihr Bereich Abbildungen benötigt. Ein fehlender Verzeichniseintrag kann einen ganzen ungenutzten Bereich darstellen.

Die 10/10/12-Aufteilung herleiten

Nimm eine virtuelle 32-Bit-Adresse, 4 KiB große Seiten und 4 Byte große Einträge. Jede Seitentabellenseite enthält 1.024 Einträge, sodass ein 10-Bit-Index einen Eintrag auswählt. Die Adresse wird in 10 Verzeichnisbits, 10 Tabellenbits und 12 Offsetbits aufgeteilt. Jede Tabelle der unteren Stufe bildet 1.024 Seiten ab und deckt 4 MiB virtuelle Adressen ab. Auch das Verzeichnis hat 1.024 Einträge und belegt eine 4 KiB große Seite.

Verzeichnis- und Tabelleneinträge verfolgen

Der Durchlauf folgt physischen Zeigern:

1. Addiere $\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ zur physischen Basis des Verzeichnisses. Lies diesen Seitenverzeichniseintrag (PDE).
2. Zeigt er auf eine Tabellenseite, multipliziere seine PFN mit 4.096, um die physische Basis dieser Tabelle zu erhalten.
3. Addiere $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ und lies den PTE.
4. Prüfe die Abbildung auf der untersten Stufe und kombiniere ihre PFN mit dem Offset.

Der PDE zeigt auf eine Tabelle, während der PTE auf die angeforderte Datenseite zeigt. Wer diese Rollen verwechselt, leitet einen Zugriff in den Speicher der Seitentabelle statt zu den Programmdaten.

Für die virtuelle Adresse 0x00803ABC ist der Verzeichnisindex 2, der Tabellenindex 3 und der Offset 0xABC. Verzeichniseintrag 2 zeige auf Seitenrahmen 0xA1. Dessen Tabelle beginnt bei 0xA1000. Eintrag 3 liegt 12 Byte nach Tabellenbeginn bei 0xA100C. Enthält der erlaubte, präsente PTE die PFN 0x2F3C4, lautet die Datenadresse 0x2F3C4ABC.

Beachte die zwei unterschiedlichen Faktoren. Ein Tabellenindex zählt Einträge, multipliziere ihn also mit der Eintragsgröße. Eine PFN zählt Seitenrahmen, multipliziere sie also mit der Seitengröße. Der Offset zählt Bytes innerhalb der letzten Seite und benötigt keinen der beiden Faktoren. Die Verzeichnisbasis und die beim Durchlauf verwendeten Zeiger sind physische Adressen; virtuelle Zeiger würden eine weitere Übersetzung erfordern, um diese Übersetzung durchzuführen.

Tabellen und Lesezugriffe für die Suche zählen

Der Speicherbedarf hängt davon ab, wie die Abbildungen angeordnet sind. Ein Prozess nutze die unteren 8 MiB seines 4 GiB großen Adressraums und die oberen 4 MiB; beide Bereiche seien an Verzeichnisgrenzen ausgerichtet. Der untere Bereich benötigt zwei Tabellenseiten, der obere eine. Mit dem Verzeichnis ergibt das vier Seiten oder 16 KiB statt einer 4 MiB großen linearen Tabelle. Würde dieselbe Anzahl an Datenseiten dünn über viele Verzeichnisbereiche verteilt abgebildet, könnten mehr Tabellenseiten nötig sein.

Im grundlegenden Lehrmodell bedeutet ein ungültiger PDE, dass keine Seite in seinem 4-MiB-Bereich zum Adressraum gehört. Der Durchlauf endet, ohne einen PTE zu lesen. Vollständige Betriebssysteme können fehlende Einträge auch für verzögerte Speicherzuweisung nutzen. Daher entscheiden ihre Softwareaufzeichnungen über die Bedeutung eines aus Sicht der Hardware nicht präsenten Eintrags.

Die Hierarchie spart Platz, indem sie bei einem TLB-Fehlzugriff zusätzliche Arbeit verursacht. Ein zweistufiger Durchlauf ohne zwischengespeicherte Einträge liest vor dem Datenzugriff einen PDE und einen PTE: insgesamt drei Speicherlesezugriffe gegenüber zwei bei einer linearen Tabelle. Ein TLB-Treffer umgeht diese Tabellenlesezugriffe. Das macht eine hohe Trefferquote besonders wertvoll, je tiefer die Hierarchie wird.

Die Anzahl der Tabellenstufen ergibt sich aus drei Größen: der implementierten Breite virtueller Adressen, der Seitengröße und der Eintragsgröße. Berechne zuerst die Breite des Offsets. Berechne dann, wie viele Einträge auf eine Tabellenseite passen und wie viele Bits einen Eintrag auswählen. Teile schließlich die übrigen VPN-Bits in Indexfelder auf und runde die Anzahl der Stufen bei Bedarf auf.

Die vier Stufen herleiten

Bei der vierstufigen Seitenverwaltung auf x86-64 beträgt die implementierte Breite virtueller Adressen 48 Bit. Eine 4 KiB große Seite ergibt 12 Offsetbits. Bei 8 Byte pro Eintrag passen 512 Einträge auf eine Tabellenseite, die durch 9 Bit ausgewählt werden. Die VPN hat 36 Bit, sodass vier 9-Bit-Indizes nötig sind. Ein erfolgreicher Durchlauf ohne zwischengespeicherte Einträge folgt vier Einträgen und greift dann auf die Daten zu.

Die Stufen heißen PML4, Seitenverzeichniszeigertabelle, Seitenverzeichnis und Seitentabelle. Ihre Indizes belegen die Bits 47–39, 38–30, 29–21 und 20–12. CR3 bezeichnet die physische Wurzel. Linux nennt die entsprechenden Stufen PGD, PUD, PMD und PTE; seine allgemeine Hierarchie enthält eine P4D-Stufe, die zusammengefaltet wird, wenn die Architektur nur vier Stufen verwendet.

Adressbreite und RAM unterscheiden

Ein implementierter 48-Bit-Adressraum enthält 256 TiB adressierbare Bytes. Adressen werden weiterhin in 64-Bit-Werten gehalten: In der gewöhnlichen kanonischen Form wiederholen die Bits oberhalb von Bit 47 dessen Wert. Die gültigen unteren und oberen Bereiche sind durch eine nicht kanonische Lücke getrennt. Die Bezeichnung als 48-Bit-Adressraum bedeutet weder, dass jedes 64-Bit-Muster nutzbar ist, noch dass ein Prozess 256 TiB RAM erhält.

Eine lineare Tabelle wäre riesig. Es gibt $2^{36}$ virtuelle Seiten; multipliziert mit 8 Byte pro Eintrag ergibt das $2^{39}$ Byte oder 512 GiB pro Prozess. Eine Hierarchie stellt ungenutzte Bereiche durch fehlende Zweige dar, statt all diese Einträge zu reservieren.

Prozessoren mit Unterstützung für fünfstufige Seitenverwaltung können 57 implementierte virtuelle Adressbits nutzen, wenn dieser Modus aktiviert ist. Oberhalb der PML4 kommt ein weiterer 9-Bit-Index hinzu. Das ergibt 128 PiB adressierbare Bytes und einen weiteren möglichen Tabellenlesezugriff. Die oberen Bits einer kanonischen Adresse wiederholen dann Bit 56. Die Prozessorunterstützung und der aktivierte Seitenverwaltungsmodus bestimmen, welche Breite gilt.

Den Durchlauf bei einer großen Seite beenden

Große Speicherseiten beenden den Durchlauf frühzeitig. Auf x86-64 kann ein Eintrag auf Seitenverzeichnisebene direkt eine 2 MiB große Seite abbilden, wobei 21 Offsetbits bleiben. Ein Seitenverzeichniszeigereintrag kann eine 1 GiB große Seite abbilden, wobei 30 Offsetbits bleiben. Niederwertige Bits, die sonst Einträge niedrigerer Stufen auswählen würden, wählen nun Bytes innerhalb dieser großen Seite aus.

Das verringert sowohl die Länge des Durchlaufs als auch die Anzahl der für einen bestimmten Bereich benötigten Übersetzungen. Es erhöht die TLB-Reichweite, was Datenbanken und anderen großen Arbeitslasten helfen kann. Die physische Abbildung benötigt einen passend ausgerichteten zusammenhängenden Bereich von Seitenrahmen, und eine teilweise genutzte große Seite kann erheblich mehr Speicher verschwenden. Linux unterstützt die ausdrückliche Zuweisung großer Speicherseiten und transparente große Speicherseiten; die unterstützten Größen hängen von der Architektur ab.

Die einfache Aufwandsrechnung setzt voraus, dass keine Tabelleneinträge zwischengespeichert sind. Reale Prozessoren speichern Seitenverwaltungsstrukturen zwischen und Tabellenlesezugriffe können in gewöhnlichen Caches Treffer erzielen. Vier Stufen bedeuten daher nicht, dass bei jedem TLB-Fehlzugriff vier Verzögerungen durch Hauptspeicherzugriffe auftreten. Sie beschreiben die Abhängigkeitskette und deren Aufwand ohne zwischengespeicherte Einträge.

Virtuelle Adressräume können zusammen größer sein als der physische Speicher, weil nicht jede Seite ständig im Speicher liegen muss. Der Auslagerungsbereich speichert verdrängte Seiteninhalte auf einer Festplatte oder SSD. Linux kann eine Auslagerungspartition oder -datei nutzen; Windows verwendet eine Auslagerungsdatei. Der physische Speicher hält die aktuell eingelagerten Seiten.

Die Seitenverwaltung verschiebt einzelne Seiten. Beim Auslagern wird eine Seite auf einen Hintergrundspeicher geschrieben, bevor ihr Seitenrahmen erneut verwendet wird; beim Einlagern wird sie zurückgelesen. Historisch bezeichnete Auslagerung auch das Verschieben eines ganzen Prozesses. Heute ist damit häufig das Verschieben von Seiten gemeint. Achte daher darauf, was verschoben wird.

Die fehlende Abbildung deuten

Das Präsenzbit eines PTE teilt der Hardware mit, ob eine Abbildung auf einen Seitenrahmen im physischen Speicher verfügbar ist. Wurde eine gültige Seite ausgelagert, hält das Betriebssystem fest, wo ihr Inhalt zu finden ist, entweder in von der Software verwendeten Bits des Eintrags oder in separaten Metadaten. Ein Präsenzbit mit dem Wert null verweist nicht von sich aus auf den Auslagerungsbereich: Es kann auch nicht zugewiesenen oder verzögert zugewiesenen Speicher bezeichnen.

Ein Seitenfehler ist eine Ausnahme, die ein Zugriff auslöst, der mit der aktuellen Abbildung nicht abgeschlossen werden kann. Er kann eine fehlende Abbildung oder eine Schutzverletzung melden. Die Behandlungsroutine entscheidet, ob der Zugriff zulässig ist und wie er behandelt wird. Sie kann gespeicherte Bytes laden, nullinitialisierten Speicher bereitstellen, einen bereits eingelagerten Seitenrahmen abbilden oder eine private Kopie erstellen. Ein tatsächlich ungültiger Zugriff führt normalerweise zu einer Speicherzugriffsverletzung.

Eine gespeicherte Seite wiederherstellen

Verfolge einen Lesezugriff auf eine ausgelagerte Seite bei Seiten mit 1.024 Byte:

1. Die virtuelle Adresse 5.000 ergibt VPN 4 und Offset 904.
2. Der TLB hat keine nutzbare Übersetzung. Der Seitentabellendurchlauf findet die gültige Seite als nicht präsent; Softwareaufzeichnungen verweisen auf Auslagerungsblock 37.
3. Die Behandlungsroutine beschafft Seitenrahmen 9. Ist kein Seitenrahmen frei, muss zunächst Speicher zurückgewonnen werden.
4. Das Betriebssystem liest Block 37 in Seitenrahmen 9. Der Prozess, der den Seitenfehler ausgelöst hat, wartet; ein anderer ausführbarer Prozess kann die CPU nutzen.
5. Nach Abschluss trägt das Betriebssystem PFN 9 ein, markiert die Abbildung als präsent und macht den Prozess ausführbar.
6. Der Befehl wird wiederholt. Die Übersetzung führt nun zur physischen Adresse 10.120.

Sobald die Bytes verfügbar sind, setzt der Befehl seine vorgesehene Operation fort. Würde die Ausführung nach dem fehlgeschlagenen Befehl fortgesetzt, ginge ein Lese- oder Schreibzugriff verloren. Der Prozess kann eine Verzögerung bemerken, seine virtuelle Adresse hat sich aber nicht geändert.

Den Seitenfehler einordnen und Bedarf vorhersagen

Ein schwerer Seitenfehler benötigt einen Lesezugriff auf den Massenspeicher. Ein leichter Seitenfehler wird ohne diese Ein-/Ausgabe behoben, etwa durch Bereitstellen eines mit Nullen gefüllten Seitenrahmens oder durch Abbilden eines bereits eingelagerten Seitenrahmens. Viele leichte Seitenfehler bedeuten daher nicht dieselben Gerätezugriffe wie ebenso viele schwere Seitenfehler. Unter Linux meldet /usr/bin/time -v für einen Befehl beide Anzahlen.

Bei der Seitenanforderung bei Bedarf wird eine Seite erst beim Zugriff bereitgestellt. So kann ein Programm beginnen, ohne seinen gesamten Inhalt zu laden. Beim Vorabladen werden Seiten eingelagert, die voraussichtlich bald benötigt werden. Gute Vorhersagen vermeiden spätere Wartezeiten; schlechte verbrauchen Bandbreite und Speicher für Seiten, die nie genutzt werden.

Halte die Ereignisse auseinander: Ein TLB-Fehlzugriff erfordert die Suche nach einer Übersetzung. Bei einem Seitenfehler muss das Betriebssystem ein Abbildungsproblem behandeln. Eine Speicherzugriffsverletzung ist eine übliche Folge eines verbotenen Zugriffs. Bei einer eingelagerten Seite, auf die der Zugriff erlaubt ist, kann ein TLB-Fehlzugriff auftreten, ohne dass eines der beiden anderen Ereignisse eintritt.

Ein seltener Lesezugriff auf den Massenspeicher kann die durchschnittliche Speicherzugriffszeit dominieren. Dabei sei $p$ die Wahrscheinlichkeit, dass ein Zugriff einen schweren Seitenfehler auslöst, $M$ die gewöhnliche Zugriffszeit und $F$ die gesamte Behandlungszeit für einen Zugriff mit Seitenfehler. Ein einfaches Modell mit zwei Fällen ergibt:

Dabei umfasst $F$ den Lesezugriff auf den Massenspeicher, die Arbeit des Betriebssystems und das gegebenenfalls nötige Zurückschreiben einer veränderten Opferseite. Es ist die Gesamtzeit für den Seitenfehlerfall, nicht nur ein kleiner Zusatzaufwand für die PTE-Suche.

Die Wirkung seltener Seitenfehler berechnen

Ein gewöhnlicher Zugriff dauere 100 ns und ein schwerer Seitenfehler insgesamt 8 ms. Rechne 8 ms vor der Mittelwertbildung in 8.000.000 ns um. Bei einem Seitenfehler pro 1.000 Zugriffe:

Das ist etwa das 81-Fache der gewöhnlichen Zugriffszeit. Eine Seitenfehlerrate von 0,1 % klingt gering, aber ein Seitenfehler kostet so viel Zeit wie viele Tausend Speicherzugriffe.

Für eine Verlangsamung unter 10 % muss der Durchschnitt unter 110 ns liegen. Umstellen ergibt:

Das ist weniger als ungefähr ein schwerer Seitenfehler pro 800.000 Zugriffe. Die zulässige Wahrscheinlichkeit hängt von der angenommenen Behandlungszeit ab. Bei einer beispielhaften SSD-Behandlungszeit von 0,1 ms ist die Wartezeit kürzer, beträgt aber immer noch 100.000 ns: tausend Zugriffe zu je 100 ns.

Seitenrahmen bereithalten

Das Betriebssystem versucht, Seitenrahmen bereitzuhalten, bevor ein Seitenfehler einen benötigt. Ein Seitendämon im Hintergrund, etwa kswapd unter Linux, gewinnt Speicher zurück, wenn die Anzahl freier Seitenrahmen unter eine niedrige Wasserstandsmarke fällt. Im grundlegenden Wasserstandsmarkenmodell arbeitet er weiter, bis eine hohe Wasserstandsmarke erreicht ist. So muss nicht bei jedem Seitenfehler erst eine Opferseite ausgewählt und vorbereitet werden.

Änderungen vor der erneuten Nutzung sichern

Eine veränderte Seite enthält Änderungen seit dem letzten Zurücksetzen des Änderungszustands. Bevor ihr Seitenrahmen erneut genutzt wird, müssen diese Änderungen gesichert werden, sofern die Seite Teil des Speichers eines Prozesses bleibt. Das Zurückschreiben kann im Hintergrund erfolgen. Nach erfolgreichem Zurückschreiben kann die eingelagerte Seite als unverändert markiert werden; ein späterer Schreibzugriff verändert sie erneut.

Eine unveränderte Seite darf nur dann ohne erneuten Schreibvorgang verworfen werden, wenn ihr Inhalt wiederhergestellt oder neu erzeugt werden kann. Unveränderter Programmcode kann erneut aus der ausführbaren Datei gelesen werden. Eine Seite mit einer aktuellen Kopie im Auslagerungsbereich kann von dort gelesen werden. Eine unveränderte anonyme Seite ohne wiederherstellbare Kopie darf nicht einfach vergessen werden. Das Änderungsbit allein belegt nicht, dass eine Kopie auf einem Hintergrundspeicher existiert.

Muss bei einem Seitenfehler synchron eine veränderte Seite verdrängt werden, kann ein Schreibvorgang für die Opferseite und anschließend der angeforderte Lesevorgang nötig sein. Wird eine unveränderte, wiederherstellbare Opferseite bevorzugt, entfällt dieser Schreibvorgang im kritischen Ablauf der Seitenfehlerbehandlung. Die Bündelung von Seitentransfers fasst mehrere Schreibvorgänge zu größeren Übertragungen zusammen, was besonders bei Festplatten nützlich ist.

Seitenfehler sind nützliche Stellen, an denen Arbeit aufgeschoben werden kann. Eine Abbildung kann zu einem Prozess gehören, bevor das Betriebssystem ihr einen privaten Seitenrahmen zuweist. Bei der Nullinitialisierung bei Bedarf erhält der Prozess beim ersten Zugriff mit Nullen gefüllten Speicher. Dadurch müssen nicht alle reservierten Seiten im Voraus zugewiesen und mit Nullen gefüllt werden. Die Nullinitialisierung verhindert außerdem, dass ein Prozess Datenreste eines anderen Prozesses sieht.

Der Seitenfehler benötigt keinen Lesezugriff auf die Festplatte, weil der benötigte Inhalt aus Nullen und nicht aus gespeicherten Bytes besteht. Es ist ein leichter Seitenfehler. Ein System kann die Implementierung optimieren, aber das sichtbare Ergebnis bleibt: Neu bereitgestellter Speicher enthält die erforderlichen Nullen.

Schreibgeschützten Code gemeinsam nutzen

Getrennte Seitentabellen erfordern keine getrennten Kopien jeder Seite. Zwei PTEs können dieselbe PFN enthalten, auch bei unterschiedlichen virtuellen Adressen. Prozesse, die dasselbe Programm ausführen, können schreibgeschützten Code gemeinsam nutzen. Fünfzig Prozesse, die einen Editor nutzen, können auf eine eingelagerte Kopie jeder gemeinsam genutzten Codeseite verweisen. Der Schreibschutz verhindert, dass ein Prozess diese Befehle für alle verändert.

Beim Schreiben private Inhalte erzeugen

Copy-on-Write (COW) ermöglicht die anfängliche gemeinsame Nutzung von Seiten, die später möglicherweise private Inhalte benötigen. Nach fork() haben Eltern- und Kindprozess getrennte Adressräume, können sich aber ihre gewöhnlichen privaten Datenseitenrahmen teilen. Das Betriebssystem markiert ihre beschreibbaren privaten Abbildungen als schreibgeschützt und hält fest, dass es sich um COW-Abbildungen handelt. Lesezugriffe gelingen ohne Kopieren.

Wenn einer der Prozesse erstmals eine gemeinsam genutzte COW-Seite beschreibt, verstößt der Schreibzugriff gegen deren aktuellen Schutz und löst einen Seitenfehler aus. Die Behandlungsroutine erkennt den zulässigen COW-Fall, weist einen privaten Seitenrahmen zu, kopiert die Seite, richtet für den schreibenden Prozess eine beschreibbare Abbildung ein und wiederholt den Befehl. Der andere Prozess behält den ursprünglichen Inhalt. Das Betriebssystem muss außerdem dafür sorgen, dass zwischengespeicherte Übersetzungen mit den geänderten Abbildungen übereinstimmen.

Ein Prozess habe 400 MiB eingelagerte private Daten. Sein Kindprozess beschreibe drei verschiedene 4 KiB große Seiten, bevor er exec() aufruft. Die durch diese Schreibzugriffe kopierten Daten umfassen insgesamt 12.288 Byte. Wiederholte Schreibzugriffe auf eine bereits private Seite verursachen nicht jedes Mal eine neue Kopie der ganzen Seite. Die Erstellung der Seitentabellen und die übrige Prozessverwaltung verursachen weiterhin Aufwand; COW vermeidet das sofortige Kopieren aller 400 MiB Daten.

Das ist besonders nützlich, wenn auf fork() bald exec() folgt, das den Adressraum des Kindprozesses ersetzt. Würden alle alten Daten sofort kopiert, entstünde Arbeit, deren Ergebnis der Kindprozess möglicherweise nie nutzt. Absichtlich gemeinsam genutzte beschreibbare Abbildungen haben eine andere Semantik: COW beschreibt private Abbildungen, die sich bei einem Schreibzugriff unterscheiden müssen.

Ein schreibgeschützter PTE allein bedeutet nicht, dass COW vorliegt. Ein Schreibzugriff auf tatsächlich schreibgeschützten Programmcode ist ein Fehler; ein Schreibzugriff auf eine durch COW geschützte Datenseite kann ermöglicht werden. Softwareaufzeichnungen unterscheiden die Fälle, sodass dieselbe Schutzausnahme der Hardware entweder zu einer erfolgreichen Wiederholung oder zu einer Speicherzugriffsverletzung führen kann.

Kernelabbildungen schützen

Auch Kernelabbildungen nutzen Schutzmechanismen. Ein herkömmlicher Entwurf bildet Kernelspeicher mit ausschließlichem Kernelzugriff in den Adressraum jedes Prozesses ab. So kann der Kernel betreten werden, ohne eine vollständig andere Abbildung auszuwählen. Code im Benutzermodus kann nicht auf diese Seiten zugreifen, nur weil sie Adressen haben. Die Kernel-Seitentabellenisolation, die auf betroffenen Systemen eingeführt wurde, nachdem Meltdown 2018 öffentlich bekannt wurde, entfernt die meisten Kernelabbildungen, während Benutzercode läuft, und wechselt beim Eintritt in den Kernel die Abbildungen.

Eine Seitenersetzungsstrategie wählt eine eingelagerte Seite zur Verdrängung, wenn für eine benötigte Seite kein Seitenrahmen frei ist. Der physische Speicher dient als Cache für Seiteninhalte. Die Strategie versucht, Seiten zu behalten, deren zukünftige Nutzung teure Seitenfehler vermeidet. Ein Fehlzugriff bei der Seitenersetzung ist ein abstraktes Ereignis, bei dem eine Seite nicht im Speicher liegt; ob Ein-/Ausgabe nötig ist, hängt von der Herkunft des fehlenden Inhalts ab.

Treffer und Fehlzugriffe erfassen

Vergleiche Strategien mit derselben Referenzfolge, derselben Anzahl an Seitenrahmen und demselben Ausgangszustand. Eine Referenzfolge führt Seitennummern in der Reihenfolge der Zugriffe auf. Frage bei jedem Zugriff zuerst, ob die Seite eingelagert ist. Falls ja, notiere einen Treffer. Andernfalls notiere einen Fehlzugriff, lade die Seite und verdränge nur dann eine Opferseite, wenn der Speicher bereits voll ist.

Erste Zugriffe sind Fehlzugriffe, auch wenn noch Seitenrahmen frei sind. Diese Erstzugriffsfehler lassen sich durch die Wahl einer anderen Opferseite nicht vermeiden. Spätere Fehlzugriffe aufgrund unzureichender Kapazität sind Kapazitätsfehler. Bei der Seitenersetzung gibt es keine Platzierungskonflikte: Eine Seite kann jeden Seitenrahmen belegen. Konfliktfehler gehören zu Caches mit eingeschränkter Platzierung, nicht zu diesem vollständig flexiblen Seitenrahmenmodell.

Die am weitesten entfernte zukünftige Nutzung wählen

Die optimale Strategie, OPT oder MIN, wählt die Seite, deren nächste Nutzung am weitesten in der Zukunft liegt. Eine Seite, die nie wieder genutzt wird, ist eine ideale Opferseite. Dies ergibt für eine bekannte Referenzfolge die wenigsten Fehlzugriffe, doch ein laufendes Betriebssystem kann beliebige zukünftige Zugriffe nicht kennen. OPT dient als Maßstab für praktische Strategien.

Verwende drei zunächst leere Seitenrahmen und die Folge 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. Die ersten drei Zugriffe füllen den Speicher und sind Fehlzugriffe. Der nächste Zugriff auf 1 ist ein Treffer. Bei Zugriff 5 kommt Seite 4: Die eingelagerten Seiten 1, 2 und 3 werden als Nächstes an den Positionen 6, 8 und 11 genutzt. Verdränge 3, deren nächste Nutzung am weitesten entfernt ist.

Nach dem Treffer auf 1 kommt Seite 5 an Position 7. Die eingelagerten Seiten 1, 2 und 4 werden als Nächstes an den Positionen 9, 8 und 10 genutzt, daher verdrängt OPT 4. Die nächsten Zugriffe auf 2 und 1 sind Treffer. Der Zugriff auf Seite 4 an Position 10 ist ein Fehlzugriff; entweder 2 oder 5 kann verdrängt werden, weil keine der beiden Seiten erneut genutzt wird. Anschließend ist der Zugriff auf Seite 3 ein Fehlzugriff und entfernt eine weitere Seite ohne zukünftige Nutzung. Der letzte Zugriff auf 1 ist ein Treffer.

Gesamtergebnisse und Arbeitslasten vergleichen

Der Ablauf hat 7 Fehlzugriffe und 5 Treffer. Zählt man alle 12 Zugriffe, beträgt die Trefferquote 5/12 oder etwa 41,7 %. Es gibt fünf verschiedene Seiten und damit fünf Erstzugriffsfehler. Werden diese Fehlzugriffe aus der angegebenen Quote ausgeschlossen, beträgt sie 5/7 oder etwa 71,4 %. Beide Quoten können denselben Ablauf beschreiben, gib daher immer den Nenner an.

Um nicht den Überblick zu verlieren, halte den aktuellen Zugriff vom nachfolgenden Teil der Folge getrennt. OPT vergleicht die nächste Nutzung jeder eingelagerten Seite nach der aktuellen Position; es wählt nicht die Seite mit der größten Nummer oder die zuerst geladene Seite. Werden zwei Seiten nie wieder genutzt, bleibt jede der beiden Entscheidungen optimal.

Die Arbeitslast beeinflusst, wie stark sich die Strategie auswirkt. Sind Zugriffe auf alle Seiten gleich wahrscheinlich, bietet die bisherige Nutzung wenig Orientierung. Bei Lokalität erhält eine kleine, häufig genutzte Seitenmenge viele Zugriffe, und sie zu erhalten verbessert die Trefferquote. Der Abstand zwischen der Anzahl der Fehlzugriffe einer praktischen Strategie und der von OPT misst die mögliche Verbesserung bei dieser Arbeitslast.

FIFO verdrängt unter den aktuell eingelagerten Seiten diejenige, die zuerst geladen wurde. Eine Warteschlange erfasst die Ankunftsreihenfolge. Ein Treffer verschiebt die Seite nicht ans Ende dieser Warteschlange. Dadurch ist FIFO einfach zu verwalten, kann aber eine weiterhin häufig genutzte Seite verdrängen, nur weil sie vor langer Zeit ankam.

Statt der Ankunft die letzte Nutzung verfolgen

LRU erfasst die letzte Nutzung jeder eingelagerten Seite. Bei einem Treffer wird diese Seite zur zuletzt genutzten; bei einem Fehlzugriff und vollem Speicher wird die Seite verdrängt, deren letzte Nutzung am längsten zurückliegt. Das folgt der zeitlichen Lokalität: Kürzliche Nutzung sagt häufig eine Nutzung in naher Zukunft voraus. Ankunftszeit und Zeitpunkt der letzten Nutzung beschreiben unterschiedliche Abläufe.

Die zufällige Seitenersetzung wählt eine eingelagerte Opferseite zufällig aus, ohne eine Reihenfolge nach letzter Nutzung zu führen. Ihr Ergebnis variiert zwischen den Läufen. Sie kann das deterministische Fehlermuster von LRU bei einer zyklischen Arbeitslast vermeiden, aber dennoch unglückliche Entscheidungen treffen. LFU erfasst statt der letzten Nutzung die Anzahl der Zugriffe. Ohne Alterung kann LFU eine Seite behalten, die in einer früheren Programmphase häufig genutzt wurde, jetzt aber ungenutzt ist.

Strategien anhand derselben Folge verfolgen

Vergleiche drei leere Seitenrahmen bei 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. Die Seiten 1, 2 und 3 füllen zunächst den Speicher. Der Treffer auf 1 lässt die FIFO-Reihenfolge unverändert, sodass die eintreffende Seite 4 die Seite 1 verdrängt. LRU behandelt 1 dagegen als kürzlich genutzt und verdrängt 2. Der folgende Zugriff auf 1 ist daher bei FIFO ein Fehlzugriff und bei LRU ein Treffer.

Bei LRU verdrängen die späteren Fehlzugriffe 3 für Seite 5, 4 für Seite 2, 5 für Seite 4 und 2 für Seite 3. Am Ende stehen 8 Fehlzugriffe und 4 Treffer. FIFO verursacht 10 Fehlzugriffe und 2 Treffer. OPT verursacht bei derselben Folge 7 Fehlzugriffe. LRU verbessert hier das Ergebnis von FIFO, erreicht aber nicht das Optimum mit Kenntnis der Zukunft.

Die Belady-Anomalie erklären

Mehr Seitenrahmen verbessern nicht jede Strategie bei jeder Folge. Die Belady-Anomalie ist eine Zunahme der Fehlzugriffe, wenn FIFO mehr Seitenrahmen erhält. Bei 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 hat FIFO mit drei Seitenrahmen 9 Fehlzugriffe und mit vier 10. Die zusätzliche Kapazität verändert die späteren Opferseiten der Warteschlange, sodass ihre Mengen eingelagerter Seiten nicht zwangsläufig ineinander enthalten sind.

LRU und OPT sind Stack-Algorithmen: Werden Gleichstände einheitlich behandelt, ist die Menge eingelagerter Seiten bei einer kleineren Anzahl von Seitenrahmen in der Menge bei einer größeren Anzahl enthalten. Eine größere Kapazität kann daher einen Treffer bei kleinerem Speicher nicht in einen Fehlzugriff bei größerem Speicher verwandeln. LRU ergibt bei der Anomaliefolge 10 Fehlzugriffe mit drei Seitenrahmen und 8 mit vier.

Für die letzte Nutzung ungünstige Arbeitslasten erkennen

LRU hat dennoch ungünstige Arbeitslasten. Durchlaufe die Seiten 1, 2, 3, 4 dreimal mit drei Seitenrahmen. Jede neue Seite verdrängt die als Nächstes benötigte, was 12 Fehlzugriffe ergibt. OPT benötigt 6. Die zufällige Seitenersetzung kann nützliche Seiten über einen Zyklus hinweg behalten und schneidet hier im Durchschnitt besser ab. Ebenso kann ein einmaliger Durchlauf eine nützliche, häufig genutzte Seitenmenge aus einem LRU-Cache verdrängen.

Ein Strategievergleich muss die Arbeitslast und die Anzahl der Seitenrahmen berücksichtigen. Bei vielen Programmen macht Lokalität die letzte Nutzung zu einem nützlichen Anhaltspunkt. Das ist der Grund für LRU-Annäherungen in realen Systemen. Eine regelmäßige Schleife knapp oberhalb der Kapazität begünstigt eine andere Wahl; ein beobachteter Vorteil bei einer kurzen Folge begründet keine allgemeingültige Rangfolge.

Exaktes LRU verursacht bei jedem Speicherzugriff Arbeit. Bei Zeitstempeln aktualisiert jeder Zugriff einen Zeitstempel und die Auswahl der Opferseite sucht nach dem ältesten. Bei einer geordneten Liste steht die Opferseite am Ende bereit, aber jeder Zugriff muss seine Seite an den Anfang verschieben. Diese Struktur bei jedem Lese- und Schreibzugriff per Software zu aktualisieren wäre zu aufwendig.

Das Referenzbit lesen

Die Hardware bietet ein weniger aufwendiges Signal: das Referenzbit. Die Hardware setzt es, wenn eine Seite gelesen oder beschrieben wird. Das Betriebssystem setzt es zurück, um ein weiteres Beobachtungsintervall zu beginnen. Ein gesetztes Bit bedeutet mindestens eine Nutzung seit dem letzten Zurücksetzen; es zählt nicht die Häufigkeit und zeigt nicht die genaue Reihenfolge der letzten Nutzung an.

Eine Opferseite suchen

Der Clock-Algorithmus ordnet Seitenrahmen in einem Kreis an und hält einen Zeiger auf den nächsten Kandidaten. Bei einer Ersetzung prüft er das Referenzbit des Kandidaten. Ist das Bit 1, setzt der Zeiger es zurück und bewegt sich weiter. Ist das Bit 0, wird dieser Seitenrahmen zum Opfer. Die neue Seite kommt mit gesetztem Referenzbit hinein und der Zeiger bewegt sich darüber hinaus. Ein Treffer setzt das Bit der referenzierten Seite, ohne den Zeiger zu bewegen.

Der Kreis enthalte A mit Bit 1, B mit Bit 0 und C mit Bit 1; der Zeiger stehe bei A. Ein Seitenfehler bei D setzt das Bit von A zurück und bewegt den Zeiger zu B. B hat bereits Bit 0, sodass D die Seite B mit Bit 1 ersetzt und der Zeiger bei C endet. Ist der nächste Zugriff ein Seitenfehler bei E, setzt der Zeiger das Bit von C zurück, findet dann A mit 0 und ersetzt A. Wäre zwischen diesen Seitenfehlern auf A zugegriffen worden, wäre das Bit von A 1 und A erhielte eine weitere Chance.

Sind alle Bits 1 und erfolgen dazwischen keine neuen Zugriffe, setzt ein Durchlauf sie alle zurück. Bei seiner Rückkehr verdrängt der Zeiger dann die Seite, bei der er begonnen hat. Diese einzelne Auswahl ähnelt der nächsten Opferseite nach FIFO-Ankunftsreihenfolge, doch Clock richtet sich allgemein nach der Nutzung und der Zeigerposition; es ist nicht immer gleichbedeutend mit FIFO.

Ein vollständiger Clock-Ablauf benötigt eine Festlegung des Ausgangszustands. Hier werden leere Seitenrahmen der Reihe nach mit Bit 1 gefüllt; der Zeiger bleibt bis zur ersten Ersetzung bei Seitenrahmen 0. Treffer setzen Bits. Jede Ersetzung bewegt den Zeiger weiter. Nach dieser Festlegung ergeben drei Seitenrahmen bei 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1 10 Fehlzugriffe. Eine kurze Folge kann den Nutzen einer Annäherung an die letzte Nutzung verdecken; über längere Läufe bildet Clock Lokalität oft gut ab.

Schreibaufwand und reale Varianten berücksichtigen

Ein veränderter Zustand erhöht den Aufwand, weil die Opferseite gesichert werden muss. Eine bevorzugte Reihenfolge beim erweiterten Clock-Algorithmus ordnet Paare aus (Referenzbit, Änderungsbit) als (0, 0), (0, 1), (1, 0), dann (1, 1). Das bevorzugt eine Seite, die weder kürzlich genutzt wurde noch ungesicherte Änderungen enthält. Implementierungen unterscheiden sich darin, wie Durchläufe Bits zurücksetzen und Schreibvorgänge planen. Das Zurückschreiben im Hintergrund kann einen veränderten Kandidaten vor der Ersetzung unverändert machen.

Reale Systeme nutzen umfangreichere Varianten. VAX/VMS legte entfernte Seiten auf Listen unveränderter oder veränderter Seiten ab, sodass ein Prozess eine Seite zurückholen konnte, bevor ihr Seitenrahmen erneut genutzt wurde. Linux hat aktive und inaktive Listen verwendet und bietet Multi-Gen LRU an, das Seiten nach beobachteter letzter Nutzung gruppiert. Diese Systeme nutzen Hinweise der Hardware für Entscheidungen des Betriebssystems; das Referenzbit der Hardware wählt selbst keine Opferseite.

Seitenflattern tritt auf, wenn Prozesse die meiste Zeit damit verbringen, Seiten nach Seitenfehlern einzulagern und Seiten zu verdrängen, die bald wieder benötigt werden. Das Speichergerät bleibt beschäftigt, während die CPU-Auslastung sinkt, obwohl Programme noch Arbeit haben. Eine niedrige CPU-Auslastung allein weist nicht auf Seitenflattern hin; der Hinweis ist die Kombination aus umfangreichen Seitentransfers und geringem Fortschritt.

Die Ursache ist ein Speicherbedarf, der die verfügbaren Seitenrahmen übersteigt. Ein Prozess benötigt eine brauchbare Zusammenstellung eingelagerter Seiten, um seine aktuelle Phase abzuschließen. Passen die aktiven Seitenmengen mehrerer Prozesse zusammen nicht in den Speicher, verdrängen ihre Seitenfehler wiederholt nützliche Seiten. Noch mehr Prozesse zu starten kann diesen Druck verstärken, obwohl die CPU nicht ausgelastet erscheint.

Den aktuellen Seitenbedarf schätzen

Die Arbeitsmenge, geschrieben $W(t,\mathrm{\Delta })$, schätzt den aktuellen Bedarf eines Prozesses. Im Modell mit einem Zugriffsfenster ist sie die Menge der verschiedenen Seiten in den letzten $\mathrm{\Delta }$ Zugriffen bis zum Zeitpunkt $t$. Zähle jede Seite einmal, auch wenn sie im Fenster mehrfach vorkommt. Die Größe der Arbeitsmenge ist eine Anzahl von Seiten, nicht die Anzahl der Zugriffe.

Betrachte bei Fenstergröße 5 und der Folge 1, 2, 1, 3, 2, 1, 4, 5, 4, 5, 4, 6, 5, 4 den Zustand nach Zugriff 6. Die letzten fünf Zugriffe sind 2, 1, 3, 2, 1, das ergibt {1, 2, 3} mit Größe 3. Nach Zugriff 8 ist das Fenster 3, 2, 1, 4, 5, was Größe 5 ergibt. Nach Zugriff 11 ist es 4, 5, 4, 5, 4, was Größe 2 ergibt. Der Bedarf erreicht vorübergehend einen Höchstwert, während sich alte und neue Phase überlappen.

Aktiven Bedarf und Zuweisung steuern

Ein kurzes Fenster kann noch benötigte Seiten auslassen; ein zu langes kann Seiten aus einer abgeschlossenen Phase enthalten. Peter Dennings Arbeitsmengenmodell verbindet diesen wechselnden Bedarf mit der Zuweisung. Eine Arbeitsmengenstrategie führt Prozesse nur aus, wenn ihre Arbeitsmengen zusammen in den Speicher passen. Ist das nicht der Fall, suspendiert sie einen oder mehrere Prozesse und gibt deren Seitenrahmen frei. Das ist Zulassungskontrolle.

Die Seitenfehlerhäufigkeitssteuerung (PFF) nutzt gemessene Seitenfehlerraten. Oberhalb eines oberen Schwellenwerts benötigt ein Prozess mehr Seitenrahmen. Unterhalb eines unteren Schwellenwerts können einige Seitenrahmen neu zugewiesen werden. Benötigt ein Prozess Seitenrahmen und sind keine verfügbar, kann es nötig sein, einen Prozess zu suspendieren. Zwei Schwellenwerte verringern ständige Anpassungen um einen einzelnen Grenzwert herum.

Bei globaler Seitenersetzung kann ein Seitenfehler eine Seite eines anderen Prozesses verdrängen. Das passt sich flexibel an wechselnden Bedarf an, erlaubt aber einem Prozess, die Seitenfehler eines anderen zu erhöhen. Bei lokaler Seitenersetzung stammen Opferseiten nur aus den dem Prozess mit dem Seitenfehler zugewiesenen Seitenrahmen. Das begrenzt gegenseitige Störungen, hilft aber einem Prozess mit zu wenigen zugewiesenen Seitenrahmen nur, wenn die Zuweisung geändert wird.

Gegenmaßnahmen bei Speicherdruck wählen

Nützliche Gegenmaßnahmen verringern den Bedarf oder erhöhen die Kapazität: weniger Programme ausführen, physischen Speicher hinzufügen oder die Lokalität verbessern, etwa indem Arrays in Speicherreihenfolge durchlaufen werden. Ein schnellerer Auslagerungsbereich verringert den Aufwand jedes schweren Seitenfehlers; er sorgt nicht dafür, dass eine zu große aktive Seitenmenge hineinpasst. Der Ersatz einer Festplatte durch eine SSD kann den Fortschritt verbessern, ohne die Ursache zu beseitigen.

Bei extremem Druck kann der OOM-Killer von Linux einen ausgewählten Prozess beenden, wenn das Zurückgewinnen und Auslagern nicht genügend Speicher freigeben können. Die Auswahl beruht auf einer speicherbezogenen Bewertung und strategischen Anpassungen, nicht einfach darauf, welcher Prozess der größte ist. Der Speicher kann beim Prozessende zurückgewonnen werden, und die Arbeit des Prozesses geht verloren. Dies ist eine letzte Maßnahme zur Freigabe von Ressourcen und unterscheidet sich vom Suspendieren eines Prozesses, der später fortgesetzt werden kann.