Paging

Im Gegensatz zum Swapping, bei dem Prozesse komplett mit ihrem belegten Speicher aus dem Hauptspeicher aus- und eingelagert werden, werden beim Paging Seiten von z.B. 4kB Grösse ein- bzw. ausgelagert. Wenn der Hauptspeicher nicht ausreicht, um eine von einem Prozess zusätzlich benötigte Seite aufzunehmen, tritt ein Seitenfehler auf. Dann muss eine andere Seite ausgewählt und ausgelagert werden, um den belegten Seitenrahmen für die neue Seite frei zu machen. Für die Auswahl existieren mehrere Seitenaustausch-Algorithmen.

Der optimale Algorithmus wählt als auszulagernde Seite jene, auf die der nächste Zugriff am weitesten in der Zukunft liegt. Der Algorithmus ist nicht praktisch realisierbar, kann jedoch zum Performance-Vergleich mit anderen Seitenaustausch-Algorithmen herangezogen werden.

Der Not-Recently-Used-Algorithmus (NRU) verwendet für jede Seite zwei Flag-Bits: referenziert (R) und verändert (M), die bei lesendem oder schreibendem Zugriff auf die Seite gesetzt werden. Bei jedem Timer-Interrupt werden die M-Bits zurückgesetzt. Anhand der R- und M-Bits werden die Seiten in vier Klassen eingeteilt: 0 (R=0, M=0), 1 (R=0, M=1), 2 (R=1, M=0), 3 (R=1, M=1). Es wird eine Seite aus der niedrigsten, nicht-leeren Klasse ausgewählt.

Der FIFO-Algorithmus wählt die sich am längsten im Speicher befindende Seite aus. Da er keine Informationen über den letzten Zugriff oder die Häufigkeit der Zugriffe verwendet, ist er oft nicht besonders effizient.

Der Clock-Algorithmus verwaltet alle Seiten in einer zirkulären Liste. Man denkt sich die Seiten dann als Ziffern auf einer Uhr. Wenn eine Seite ausgelagert werden muss, betrachtet man zunächst die Seite, auf die der Uhrzeiger zeigt. Ist das R-Bit der Seite nicht gesetzt, wird die Seite ausgewählt und der Zeiger eine Position vorgestellt. Ist das R-Bit gesetzt, so wird es gelöscht, dann wird der Uhrzeiger vorgestellt und der Vorgang mit der nun betrachteten Seite wiederholt.

Der Least-Recently-Used-Algorithmus (LRU) wählt die Seite, die am längsten unbenutzt war.