2 Seitenersetzungsstrategien

Strategieren

Optimaler Algorithmus (OA)

• Seite, die am Längsten nicht referenzierte Seite wird, wird ersetzt.
• AO gibt es nicht, ist aber als Metrik wichtig (zum Vergleichen)

FIFO

• Seite, die sich am Längsten im Puffer befindet, wird ersetzt.
• Größerer Puffer führt zu mehr Page Faults

LIFO

• Seite, die sich am Kürzesten im Puffer befindet, wird ersetzt.

LRU

• Seite, die am Längsten nicht referenziert wurde, wird ersetzt.

• Kleinere Framennummer ⇐⇒ Länger nicht referenziert.

  	Referenced-Bit	Dirty-Bit
  Klasse 1	0	0
  Klasse 2	0	1
  Klasse 3	1	0
  Klasse 4	1	1

NRU

• Jede Seite hat Referenced-Bit und Dirty-Bit
• Referenced-Bit wird bei Zugriff gesetzt, in bestimmten Zeitabständen zurückgesetzt.
• Dirty-Bit wird beim Schreibzugriff gesetzt.
• Ersetzungsreihenfolge

Clock-Algorithmus

• Seiten im Puffer als Ringpuffer mit Zeiger
• Jede Seite ist ein Referenzbit
• Wenn eine Seite in Puffer, dann
  • Setze Referenzbit auf 1
  • Zeiger bleibt stehen
• Wenn eine Seite nicht in Puffer, dann
  • Zeiger geht weiter
  • Ist Referenzbit = 1 → Setze auf 0, gehe weiter
  • Ist Referenzbit = 0 → Eersetze Seite

Zählerbasierte Varfahren (LFU/MFU)

• Für jede Seite: Zähler mit Anzahl der Referenzierungen
• Zwei Ausprägungen:

LFU (Least Frequently Used)

• Ersetze Seite mit kleinstem Zähler
• Problem: Häufig hintereinander zugegriffene Seite bleibt sehr lange im Puffer
• Abhilfe: Periodisches Herabsetzen des Referenzzählers

MFU (Most Frequetly Used)

• Ersetze Seite mit größtem Zähler

Zwischenfazit

• LRU ist im Schnitt am Besten
• Es ist populär im Betriebssystemen
• Warum nicht unmittelbar auf Datenbanken übertragbar?
  • DBMS kann manchmal Zugriffsmuster vorhersagen (Referenzmuster)
    • Daher werden die Ersetzungsstrategien angepasst und Pre-Fetching für tpyische DB-Operationen realisiert.
  • DBMS muss manchmal Seite explizit auf Platte schreiben (Nötig zur Realisierung Write-Ahead Log Protocol)

Beispiel:

1. Puffer hat 10 Rahmen, zu scannende Datei hat 11 Seiten → Jeder Scan der Datei führt zum Lesen aller Seiten
2. Tabelle T mit 10 000 Seiten und B+-Baum Index. Es kommen regelmäßig Anfragen, dabei sollte der Index dauerhaft im Puffer bleiben, um effizient zu arbeiten, doch er wird immer wieder von den Seiten mit den Daten verdrängt.
3. Es sind z.B. alle Seiten, die bei 95% der Anfragen benötigt werden, im Puffer. Nun wird bei einem Aufruf jede Seite der Datenbank in den Puffer geladen → Seiten sind weg