Page-Replacement-Algorithmen und Thrashing erklärt

Page-Replacement-Algorithmen

• Random: Die schlechteste aller Methoden, aber einfach zu implementieren.
• FIFO (First-In-First-Out): Ersetzt die Seite, die am längsten im Arbeitsspeicher liegt. Die Implementierung ist einfach, da die Seitenverwaltung über eine Liste erfolgt.
• LRU (Least Recently Used): Ersetzt die Seite, auf die am längsten nicht mehr zugegriffen wurde. Da die Vergangenheit ein guter Indikator für die Zukunft ist, gilt dies als eine der besten Methoden.
• NUR (Not Used Recently): Das Opfer wird zyklisch aus den Seiten gewählt, auf die in der letzten Zeit nicht zugegriffen wurde (basierend auf Referenz-Bits).
• LFU (Least Frequently Used): Ersetzt die Seite mit der geringsten Zugriffshäufigkeit. Erfordert einen Referenzzähler.
• Clock-Algorithmus: Eine Variante von LRU, die jeder Seite eine zweite Chance gibt. Die Seiten sind in einer zirkulären Liste angeordnet, die im Uhrzeigersinn durchlaufen wird.
• Clock mit zwei Zeigern: Ziel ist es, Seiten zu bevorzugen, die häufig im Speicher referenziert werden.

Lokalität von Prozessen

Dieses Phänomen beschreibt, dass Prozesse in einem bestimmten Zeitraum der Ausführung nur auf eine begrenzte Anzahl von Seiten zugreifen.

Thrashing (Seitenflattern)

Thrashing tritt auf, wenn ein System mehr Zeit mit dem Paging von Prozessen verbringt als mit deren Ausführung. Dies führt zu einem massiven Leistungsabfall und kann einen Systemkollaps durch Überlastung mit Seitenfehlern verursachen.

Thrashing steht in direktem Zusammenhang mit dem Grad der Multiprogrammierung. Eine Reduzierung dieses Grades kann das Problem der Überlastung lindern. Thrashing bedeutet vereinfacht, dass der Prozess eine schlechte Lokalität aufweist.

Working-Set-Modell

ermöglicht die Ausführung eines Prozesses, wo sie ihre Arbeit vollständig im Speicher.

Definieren WS (Working Set) als die Menge der virtuellen Seiten des Prozesses P k wurden in den letzten Sekunden der virtuellen Zeit von P. zugegriffen WS Strategie ist es, P-Wert für jeden Zeitpunkt k P komplette zweite CPU-Auslastung (virtuelle Zeit) zu berechnen.

WS Größe eines Prozesses hängt ab von:

• Der Ort der Zugriffe auf k wird der Speicher-Prozess.
• Die Zeit zwischen dem WS zu laden.
• Die Größe der Seite.