3.3.2.2.3.5 Working Set Algorithmus

Der Working Set Seitenersetzungsalgorithmus basiert auf interessanten Erkenntnissen:

• Wird ein Prozess auf der CPU ausgeführt, so werden seine Befehle der Reihe nach von Steuerwerk und Rechenwerk verarbeitet. Jeder Befehl stammt aus einer bestimmten virtuellen Seite aus dem Adressraum des Prozesses.
• Der jeweils nächste zu verarbeitende Befehl stammt ebenfalls aus einer virtuellen Seite. In vielen Fällen wird es sogar dieselbe virtuelle Seite wie beim Befehl zuvor sein, denn die Befehle werden überwiegend sequentiell abgearbeitet.
• Zum Beispiel bei Sprüngen kann ein Befehl zur Ausführung kommen, der aus einer anderen virtuellen Seite stammt. Werden danach weitere Befehle sequentiell abgearbeitet, so stammen diese mit hoher Wahrscheinlichkeit wieder alle von derselben virtuellen Seite.

Insgesamt ist damit erkennbar, dass bei vielen nacheinander auf der CPU ausgeführten Befehlen nur relativ wenig verschiedene virtuelle Seiten angesprochen werden. Genau diese Seiten bilden nun das Working Set des betrachteten Prozesses.

Der Working Set Algorithmus versucht nun, alle zum Working Set eines Prozesses gehörenden Seiten ständig im Hauptspeicher zu halten.

Optimalerweise geht der Algorithmus dabei sogar noch einen Schritt weiter:
Halte für alle Prozesse auch alle zum jeweiligen Working Set gehörigen virtuellen Seiten stets in einem Seitenrahmen eingelagert.

Sofern dies gelingt, kann man ein System erwarten, welches nur noch eine verhältnismäßig kleine Zahl an Seitenfehlern produziert.

Lokalitätseffekt

Der Working Set Algorithmus nutzt den sogenannten Lokalitätseffekt von Prozessen, der nach Glatz 2010 wie folgt umschrieben werden kann:

Der Lokalitätseffekt bezeichnet die Idee, dass innerhalb größerer Zeiträume immer nur ein Teil des gesamten Codeumfangs eines Prozesses ausgeführt wird.

Aufgabe 1

Aufgabe

 Aufg. 178: Die 80/20-Regel und das Working Set

Du kennst sicher die 80/20-Regel:
80 Prozent der von einer Software bereitgestellten Funktionen werden höchstens von 20 Prozent der Nutzer tatsächlich eingesetzt.

Erläutere (unter der Voraussetzung, dass die Regel zutrifft):
Wie unterstützt diese Regel den Working Set Algorithmus bei seinem Ziel, möglichst wenig Seitenfehler entstehen zu lassen?

Weiterführende Literatur

Eine detailliertere Auseinandersetzung mit dem Working Set Algorithmus findet sich u.a. bei:

• Glatz 2010, Kapitel 7.5.2
• Mandl 2013, Kapitel 7.2.3
• Strelen 2012, Kapitel 6.6.1
• Tanenbaum 2009, Kapitel 3.4.8

und kann dort - je nach Verfügbarkeit der Quellen - nachgelesen werden.

---

_{Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png}