Swapping und Paging

• Kombination von NRU- und FIFO Algorithmus
• Die älteste Seite wird untersucht
• R-Flag = 0: nicht benutzt – auslagern
• R-Flag = 1: kürzlich benutzt – noch nicht auslagern
  • R-Flag löschen
  • ans Ende der Liste (als "jüngste" Seite) setzen
  •  Suche fortsetzen

+Besser als FIFO

-das ständige umsetzen von Listenelementen macht den Algorithmus kompliziert

• Das Element, auf das der Zeiger weist, wird untersucht
• R = 0 (unbenutzt) – auslagern/ersetzen
• R = 1 (benutzt)
  • R-Flag löschen
  • Zeiger weiterdrehen
  • Weitersuchen

+ Gleicher Effekt wie Second Chance, aber ohne Umsortieren der Liste

•  Zugriffe auf benachbarte Seiten sind weit häufiger als  solche auf "entfernte”: Lokalität ("locality of reference")
•  Die letzten k Seiten, auf die zugegriffen wurde bilden den Arbeitssatz  ("working set") des Prozesses (k: "Fenstergröße")
• Bei Seitenfehler wird eine Seite ausgelagert,  die nicht zum Arbeitssatz gehört

•  Der Arbeitssatz besteht aus den Seiten, auf die in den letzten z.B. 100 ms zugegriffen wurde
• Dazu muss die Zeit des letzten Zugriffs (im Verhältnis zur insgesamt vom Prozess genutzten CPU-Zeit) gespeichert werden ("current virtual time")
•  In regelmäßigen Abständen (Periodendauer T) werden alle R-Flags gelöscht
•  Bei Seitenfehler:
  • R = 1 (benutzt): Schreibe aktuelle Prozesszeit in den Seitenlisten-Eintrag
  • R = 0 (unbenutzt): wie groß ist die Differenz Δt von aktueller und eingetragener Prozesszeit?
    • Δt < T: Seite bleibt im Arbeitssatz
    • Δt > T: Seite gehört nicht mehr zum Arbeitssatz und kann entfernt werden

•  Seite "sauber": einfach überschreiben
• Seite verändert: Zum Schreiben auf Platte einplanen
• Zeiger weiterdrehen
• Zeiger einmal rundrum:
  • Entweder: >= 1 Seite zum Schreiben eingeplant – weitersuchen
  • Oder: keine Seite zum Schreiben eingeplant – irgendeine "saubere" Seite auslagern

• Der Page Daemon verwendet eine Spielart des WSClock-Algorithmus
• Anstelle einer Zeitmarke wird jeder Seite ein Alter (Anzahl der Überprüfungen) zugeordnet
• Beim Systemstart wird der Page Daemon gestartet
  • Prüft regelmäßig, ob genügend Speicher frei ist
  • Wenn der freie Speicher knapp wird, beginnt der Page  Daemon damit, Seiten zu markieren, die ausgelagert  werden können

 Der Flush Daemon schreibt auslagerungsfähige Seiten,  die verändert wurden, auf Platte

Wenn das Paging zu häufig wird ("thrashing"), werden  Prozesse aus dem Speicher entfernt (Swapping)

??

• Ein lauffähiger Prozess in den Speicher geladen werden soll
• Die Frequenz der Seitenfehler so groß ist, dass ein  Prozess ausgelagert werden sollte und lagert bei  Bedarf Prozesse aus

• Der Kernel
• Zombies (brauchen kaum Speicher)
• Prozesse, die nicht mindestens 2 Sekunden im Speicher waren

Von ausgelagerten Prozessen werden nur die Seiten wieder geladen, die wirklich benötigt werden (demand paging)

Der Swapper lagert bei Bedarf ganze Prozesse auf Platte aus, wenn die Rate der Seitenfehler zu groß wird

Das Betriebssystem bzw ein Teil der CPU (Memory Management Unit)

Einzelne Speicherseiten von Prozessen werden auf Festplatte ausgelagert

Ganze Prozesse werden zeitweilig auf Festplatte ausgelagert

Linux: Partition

Windows: Datei

Auf einem  Swap-Devices werden die ausgelagerten Seiten gespeichert. Es sind Blockorientierte Geräte mit fortlaufenden Blöcken

Die FREIEN Blöcke eines Swap-Gerätes in form einer Liste von Blockadressen und den ab dort verfügbaren freien Blöcken

?

??

Gültigkeitsfehler (die gewünschte Seite ist gerade nicht im Speicher)

• Plattenblock-Deskriptor: gültige Seite erzeugen 
• Falls nötig, eine Seite aus dem Speicher auslagern
• Die benötigte Seite laden

Speicherschutzfehler (Verletzung des SchreibkopieBits) 

• Kopie der Seite bauen

Prepaging: Das System führt Buch, welche Seiten der Prozess vermutlich braucht und lädt sie vor Beginn der Ausführung  

Demand Paging: Die Seiten werden erst dann geladen, wenn der erste Zugriff erfolgt

 Bitmap: 1 Bit pro Seite (1: belegt, 0: frei)

Verkettete Liste: Verw auf voriges Element | Prozes/Loch Bit s

First Fit Algorithmus: Nimm das erste Loch, das groß genug ist

 +einfach, +schnell, -ineffiziente Speichernutzung

Best-Fit Algorithmus: Nimm das Loch, das am besten passt

+effiziente Speichernutzung, -langsam, -komplizierter

Quick-Fit Algorithmus: Führe Listen über freie Löcher verschiedener Größe

Kompromiss bezüglich Geschwindigkeit und Speichereffizienz

Das Dirty bit sagt aus ob eine Seite geändert wurde seit sie in den Hauptspeicher geladen wurde. Ist dies nicht der Fall muss sie nicht wieder auf die Festplatte geschrieben werden, da dort ja schon eine exakte Kopie liegt.

Das Dirty bit steht im Seitentabellen - Eintrag

Der Optimaler Algorithmus lagert  die Seite aus, die am längsten unbenutzt bleiben wird

- Nicht vorhersehbar welche Seite das sein wird

Nicht praktikabel, aber als Messlatte für die Effizienz realer Algorithmen beliebt