Wenn bei der Simulation des Algorithmus zum Ersetzen der Uhrenseite eine Referenz eingeht, die sich bereits im Speicher befindet, erhöht sich der Uhrzeiger dann noch?
Hier ist ein Beispiel:
Mit 4 Steckplätzen unter Verwendung des Algorithmus zum Ersetzen der Uhrenseite
Referenzliste: 1 2 3 4 1 2 5 1 3 2 4 5
Die anfängliche Liste würde folgendermaßen aussehen:
-> [1][1]
[2][1]
[3][1]
[4][1]
Die nächste Referenz zum Einfügen wäre 1, dann 2. Würde die Hand nach 1 und nach 2 immer noch auf 1 zeigen? Mit anderen Worten, nach dem Einfügen der 5 würde die Uhr folgendermaßen aussehen:
-> [5][1]
[2][0]
[3][0]
[4][0]
?
quelle
Wenn eine Referenz für eine bereits im Speicher befindliche Seite eintrifft, wird der Ersetzungsalgorithmus überhaupt nicht aufgerufen.
Der Taktersetzungsalgorithmus versucht, einige der Vorteile des LRU-Austauschs zu erzielen, jedoch ohne den massiven Aufwand, die LRU-Bits bei jedem Seitentreffer zu manipulieren.
Eine Seite kann sich in einem von drei Zuständen befinden:
recently-used
Bit isttrue
. In diesem Fall liegt kein Seitenfehler vor, wenn auf die Seite zugegriffen wird, sodass sich keine Bits ändern.recently-used
Bit istfalse
. In diesem Fall wird die Seite auch in der Seitentabelle so markiert, dass beim Zugriff auf die Seite ein Seitenfehler auftritt. (Und wenn der Seitenfehler in diesem Fall auftritt, ändert der Seitenfehler-Handler nur den Status inrecently-used
.)clock-hand
. Während dasclock-hand
auf eine Seite mitrecently-used
gesetztem Bit zeigt,true
drehen wir dasrecently-used
Bit auffalse
und erhöhenclock-hand
es dann , um auf die nächste Seite zu zeigen. Wenn wir eine Seite finden, dierecently-used
bereits gelöscht wurde, ersetzen wir diese Seite. Dann markieren wir die neue Seite alsrecently-used
und erhöhen sieclock-hand
auf die nächste Seite.Die Uhr ist im Kern ein probabilistischer Algorithmus zur Approximation der LRU. Wenn die Rate, mit der auf die Seite zugegriffen wird, viel höher ist als die Rate, mit der die
clock-hand
Seite wieder auf dieselbe Seite zurückkehrt, besteht eine hohe Wahrscheinlichkeit, dass die Seite markiert wirdrecently-used
. Wenn die Rate , mit der die Seite zugegriffen wird niedrig , um die Rate verglichen wird , bei dem dasclock-hand
kommt wieder um, dann ist die Seite eher im Zustand sein , nichtrecently-used
. Die zuletzt verwendete Seite wird niemals ersetzt. (Warum?)quelle