Formale Verdrängungsalgorithmen
Verdrängungsalgorithmen versuchen, das zukünftige Zugriffsverhalten von Prozessen über das Lokalitätsprinzip (zeitliche und räumliche Nähe von Operationen; 90/10-Regel) zu approximieren, um die Anzahl der Page Faults zu minimieren:
- Optimale Auswahlstrategie (OPT): Verdrängt diejenige Seite, die in der Zukunft für den mathematisch längsten Zeitraum nicht mehr referenziert wird. Sie erfordert absolute Kenntnis der Zukunft und ist in der Praxis nicht realisierbar. Sie dient als rein theoretische Messlatte (Untere Schranke).
- First In – First Out (FIFO): Verdrängt die Seite, die am längsten ununterbrochen im physischen Speicher verweilt.
- FIFO-Anomalie (Belady-Anomalie): Das mathematische Phänomen, bei dem eine Erhöhung der physischen Kachelressourcen bei einer FIFO-Ersetzung paradoxerweise zu einer höheren Anzahl an Seitenfehlern führt.
- Least Recently Used (LRU): Verdrängt die Seite, deren letzter Zugriff zeitlich am längsten zurückliegt. Mathematisch realisiert über einen virtuellen Stack: Bei jedem Zugriff wandert die getroffene Seite an die Spitze des Stacks; bei einem Seitenfehler wird die unterste Seite verdrängt. In Reinform im Hauptspeicher hardwareseitig zu teuer, da jeder CPU-Speicherzugriff komplexe Stack-Operationen auslösen müsste.
- Least Frequently Used (LFU): Verdrängt die Seite, die statistisch die geringste Zugriffshäufigkeit aufweist. Ein Softwarezähler pro Seite wird bei jedem Zugriff inkrementiert.
- Recently Not Used (RNU): Verdrängt gezielt Seiten, auf die innerhalb eines fest definierten Zeitfensters (die letzten
Zugriffe) kein Zugriff mehr stattgefunden hat.