Working Set Model

Das Working Set Model ist eine Methode zur Vorbeugung von Thrashing. Es basiert auf der Annahme von Lokalität, also das ein Prozess eine gewisse Menge an Pages zusammen benutzt und sich diese Menge während der Prozessausführung verändert.

Dabei wird ein sogenanntes Working Set Window verwendet. Dieses ist eine Liste aller Ressourcen der letzten Schritte, die der Prozess getätigt hat.

Das Working Set ist dann die Menge aller Ressourcen im Working Set Window zu diesem Zeitpunkt.

Beispiel

Angenommen . Für einen Prozess könnte die Page Reference Table so aussehen:

Eingezeichnet ist bereits ein Zeitpunkt und das Working Set Window. Das Working Set sind dann alle Ressourcen aus diesem Window:

Anpassung von

Das Working Set beinhaltet jetzt also alle Ressourcen auf die der Prozess im im vergangenen Zeitfenster zugegriffen hat.

• Ist zu klein, wird es kaum Lokalitäten erfassen.
• Ist zu groß, werden oft mehrere Lokalitäten überdeckt.
• Ist = LOC, überdeckt das Window das gesamte Programm.

Gegenmaßnahmen

Sei die absolute Anzahl der Seiten die innerhalb des letzten referenziert wurden und

die Anzahl aller referenzierten Ressourcen (total demand frames). Ferner sei die Anzahl der verfügbaren Frames. Dann gilt:

Um Thrashing also zu verhindern, werden Prozesse suspendiert, sobald eintritt. Ist , können Prozesse wieder forthfahren.

Approximierung

• Mit Intval Timer und Reference Bits

Beispiel:

• Der Timer unterbricht z.B. alle 5000 Zeitschritte
• Jeder Eintrag der Page Table bekommt 2 zusätzliche Bits
• Bei jeder Timer Unterbrechung werden die Bitinhalte der ersten Spalte in die zweite kopiert und auf 0 gesetzt
• Wenn eines der Bits = 1 -> Page im Working Set
• Ungenau

Heuristische Anpassung

• Ist die Page Fault Rate niedrig, wird die Page Table verkleinert
• Ist die Page Fault Rate hoch, wird die Page Table vergrößert