Beim Seitenersatz (engl. page replacement, auch Seitenverdrängung) entscheidet das Betriebssystem, welche Speicherseite aus dem Arbeitsspeicher verdrängt wird, wenn ein Seitenfehler auftritt und kein freier Seitenrahmen mehr verfügbar ist. Ziel ist es, die Zahl der Seitenfehler möglichst klein zu halten – denn jeder verdrängte und später erneut benötigte Inhalt kostet einen teuren Zugriff auf Festplatte oder Swap.
Die klassischen Verfahren
- FIFO (First In, First Out): Die am längsten im Speicher liegende Seite wird verdrängt. Einfach umzusetzen, aber anfällig für die Belady-Anomalie: Mehr Speicher kann paradoxerweise zu mehr Seitenfehlern führen.
- LRU (Least Recently Used): Die am längsten nicht benutzte Seite fliegt raus. Basiert auf dem Lokalitätsprinzip (zuletzt benutzte Seiten werden wohl bald wieder gebraucht) und ist gegen die Belady-Anomalie immun – Details siehe LRU-Cache.
- Optimal (OPT, Belady): Verdrängt die Seite, die am längsten nicht mehr gebraucht wird. Nur mit Blick in die Zukunft möglich, dient als theoretische Untergrenze für Vergleiche.
Praxis: LRU-Approximationen
Exaktes LRU ist in Hardware zu aufwendig. Reale Betriebssysteme nutzen Näherungen wie den Clock-Algorithmus (Second-Chance): Ein Referenzbit pro Seitenrahmen, ein Zeiger wandert im Kreis und gibt jeder Seite mit gesetztem Bit eine zweite Chance. Auch LFU (Least Frequently Used, nach Nutzungshäufigkeit) und NRU (Not Recently Used) sind Varianten.
Belady-Anomalie
Bei FIFO kann mehr Speicher die Seitenfehlerzahl erhöhen: Eine bestimmte Referenzfolge (z. B. 1 2 3 4 1 2 5 1 2 3 4 5) erzeugt mit 3 Rahmen 9 Fehler, mit 4 Rahmen 10 Fehler. LRU und OPT sind von diesem Phänomen nicht betroffen.
Verwandte Grundlagen: LRU-Cache, Page Cache, Demand Paging, Thrashing, Working Set.