<< 8.3 Demand-Paging | Index | 8.5 Beispiel Unix >>


8.4 Strategien zur Seitenersetzung

  • Problem: Welche Seite soll ausgelagert werden, um Platz für neue Seiten zu schaffen?
    • Aus der Vergangenheit lernen um Vorhersagen für die Zukunft machen
    • Verwendete Daten als Anhaltspunkte:
      • Zeitpunkt der Einlagerung (Seitenalter, age)
      • Zeitpunkt des letzten Zugriffs
      • Anzahl der Zugriffe
      • Modify/Dirty-Bit der Seiten

Optimale Strategie

  • Verdrängen der Seite, die zukünfigt am längsten nicht gebraucht wird
  • Ist optimal (erzeugt so wenig Seitenfehler wie möglich)
  • Nicht praktikabel in alltäglichen Systemen, kann aber als Vergleich für andere Verfahren herangezogen werden
    • Benötigt einen ersten Durchlauf, der die Seitenzugriffe beobachtet
    • Bei weiteren Durchläufen sind Seitenzugriffe bekannt und können verwendet werden
    • Nur für genau eine Konstellation Programm/Daten gültig

FIFO

  • Die älteste Seite wird verdängt
    • Sehr einfach zu implementieren, z. B. über Warteschlange (kein Zeitstempel erforderlich)
  • Schlechte Leistung
  • FIFO-Anomalie: Erhöhung der zu Verfügung stehenden Frames kann zu einer Erhöhung der Seitenfehler führen

Second Chance

  • Ähnlich FIFO, aber Seiten erhalten zusätzlich ein Zugriffsbit (Reference-Bit, r)
    • Beim Zugriff auf eine Seite wird r-Bit gesetzt
    • Wenn Seite verdängt werden soll, wird r-Bit überprüft
      • r=0: Seite wird verdrängt
      • r=1: Seite wird hinten an die Liste gestellt und r-Bit gelöscht (r=0)
  • Vorteile:
    • Wesentlich bessere Leistung als reines FIFO
  • Nachteile:
    • Aber kein Zähler für die Anzahl der Zugriffe, nur ein Bit
    • Kann zu FIFO degenerieren, wenn alle Seiten referenziert werden

Clock-Algorithmus

  • Effiziente Implementierung von Second Chance
    • Statt lineare Warteschlange mit ältestem Element vorne wird zyklische Liste verwendet
    • Ein Zeiger zeigt auf das älteste Element und geht im Kreis herum

2-Hand-Clock-Algorithmus

  • Erweiterung des Clock-Algorithmus
    • Zwei Zeiger in der zyklischen Liste
      1. Vorderer Zeiger auf älteste Seite (löscht r-Bit)
      2. Hinterer Zeiger zur Überprüfung (r=0: verdrängen, r=1: übergehen)
    • Steuerung des Pagings über Abstand der beiden Zeiger ("Winkel")
      • Zeiger dicht zusammen: Nur Seiten mit sehr häufigem Zugriff werden nicht verdrängt
      • Zeiger maximal weit auseinander: einfacher Clock-Algorithmus
  • Anwendung in Unix, abgewandelt in Linux

LRU

  • Idee: Verdrängen der Seite, die am Längsten nicht genutzt wurde
  • Vorteile:
    • Gute Strategie
  • Nachteile:
    • Aufwendig zu implementieren
      1. Liste sortiert nach letzten Zugriff, muss bei jedem Zugriff aktualisiert werden
      2. Zeitstempel des letzten Zugriffs
    • Nur Zeitpunkt des Zugriffs zählt, nicht die Anzahl

Aging-Verfahren

  • Approximation von LRU
    • Unterscheidet zw. Zeitpunkt der Zugriffe
    • Verwendet r-Bit und Zähler (i. d. R. 8 Bit) zur Protokollierung der letzten Zugriffe
    • Bei jedem Timer-Interrupt:
      1. Zähler wird um 1 Bit nach rechts geshiftet
      2. Das MSB des Zählers wird gleich dem r-Bit gesetzt
      3. r-Bit wird gelöscht
    • Die Seite mit kleinstem Zähler wird zur Ersetzung ausgewählt
  • Findet so ähnlich Anwendung in Windows 2000

Keller-Strategien

  • Forderung:
    • Wenn die Anzahl der Frames erhöht wird, dann ist die Menge der eingelagerten Seiten pro Intervall eine Obermenge der eingelagerten Seiten bei der ursprünglichen Anzahl Frames.
      => Keine FIFO-Anomalie möglich
  • Beispiel: "echtes" LRU

Nach oben

Zuletzt geändert am 12 März 2005 16:40 Uhr von chrschn