Paging-Algorithmen
Paging-Algorithmen
Auf einen Blick
Page-Replacement-Algorithmen (PRA) entscheiden, welche Page verdrängt wird, wenn bei einem Page Fault kein Frame frei ist. Ziel: möglichst wenige zukünftige Page Faults. Wichtige Verfahren: OPT, FIFO, LRU, Second Chance, LFU.
Interaktiver Simulator
Wähle Algorithmus und Frame-Anzahl und vergleiche die Page-Fault-Zahlen:
Die Algorithmen
| Algorithmus | Verdrängt … | Bewertung |
|---|---|---|
| OPT (optimal) | die Page, deren Zugriff am weitesten in der Zukunft liegt | beste mögliche Fault-Zahl — aber nur theoretisch (Zukunft unbekannt); Vergleichsmaßstab |
| FIFO | die zuerst eingelagerte Page | kennt keine „Wichtigkeit", schlechtes Verhalten (Belady-Anomalie) |
| LRU (Least Recently Used) | die am längsten nicht verwendete Page | prinzipiell gut, aber teuer (Zeitstempel pro Page) |
| Second Chance | FIFO, aber überspringt Pages mit gesetztem Accessed Bit | billige LRU-Annäherung („lange nicht = gerade nicht") |
| LFU (Least Frequently Used) | die Page mit dem niedrigsten Zugriffszähler | „wichtig = häufig"; alte Zugriffe verzerren → Aging nötig |
Schlüsselideen
- LRU nutzt die zeitliche Lokalität: bald gebraucht wird, was gerade gebraucht wurde.
- Second Chance verwendet nur das Accessed Bit aus dem PTE — daher billig.
- LFU mit Aging: alte Zugriffe werden geringer gewichtet, damit der Zähler die aktuelle Situation abbildet.
Belady-Anomalie
Bei FIFO kann mehr Speicher zu mehr Page Faults führen — ein Grund, FIFO zu meiden. Probiere im Simulator verschiedene Frame-Zahlen bei FIFO!
Verwandte Notes
Page Faults · Thrashing · Page Table & MMU · TLB · Segmente & Pages
