clock Algorithmus Ü10 1.3

[Niggi]

Hi,

habe eine kleine Verständnisfrage zum Clockalgorithmus. Ich finde ihn in den Folien nicht eindeutig beschrieben, bzw. zu ungenau, jedenfalls habe ich Verständnisprobleme trotz Diskussion mit Mitstudenten.
Mittlererweile haben sich 2 Versionen des Algorithmus herauskristallisiert bei uns wobei mit beiden das Ergebnis der Musterlösung herauskommt. Da wir aber sonst leider wie bei so vielen Themen sonst keine Aufgaben bzw. Übungen oder Lösungen haben, können wir ja nicht testen welche davon, denn nun den eigentlichen Clock-Algorithmus wie er sein sollte, darstellt bzw. wir haben einfach ungenügend Material dafür. Leider muss ich gestehen habe ich auch keine Literatur, in der ich das nachschauen könnte, deshalb kurze Frage, vll weiß es ja einer und das Problem ist schnell geklärt und wir müssen nicht so viel reverse engineering machen.

aufgabe war mittels Clockalgorithmus als Seitenersetzungstrategie folgende Zugriffsreihenfolge bei 4physischen Seiten eines Virtuellen Speichers zu simulieren: w r s t r u v t r u q

Clock-Algo Version 1:
in den ersten 4 Schritten werden die 4 Seiten gefüllt mit w r s t und die r-Bits auf 1 gesetz, da nach Folien bei jedem Zugriff das r-Bit gesetzt wird, der Zeiger steht auf w. Beim Zugriff auf r nun wird das r-Bit von w auf 0 gesetzt und der Zeiger rückt vor und man betrachtet einen Zugriff bei vorhandenem Block in den Seiten als "Seitenfehler" und "Ersetzung an dieser Stelle", d.h. wir rücken den Zeiger bis r vor, setzen auf dem Weg alle r-bits =0 wenn sie 1 sind , bei r angekommen setzen wir r=1, da wir ja auf r zugreifen und rücken den zeiger anschließend eins vor. zeigerstand ist nun auf s und r-bit von w hat sich geändert -> 0 , bei dem Seitenfehler mit zugriff auf u wird nun der zeiger vorgerückt, jeweils r-bits auf 0 gesetzt wenn sie 1 sind solange bis der Zeiger auf ein r-bit, das 0 ist trifft -> hier passiert dies bei w und jetzt wird u mit w ersetzt und r-bit von u auf 1 gesetzt usw....

Clock-Algo Version 2:
in den ersten 4 Schritten werden die 4 Seiten gefüllt mit w r s t und alle r-bits initial auf 0 gesetzt (obwohl es auch zugriffe sind was mich verwundert). Der Zeiger steht auf w. Wenn wir nun auf r zugreifen bewegt sich der Zeiger nicht, aber das r-bit von r wird auf 1 gesetzt. Beim Zugriff auf u wird bei aktuellem Zeigerstand das r-bit = 0 von w erkannt und ersetzt mit u und r-bit auf 1 gesetzt. Beim Zugriff auf v erfolgt wieder ein Seitenfehler und der Zeiger rückt vor, setzt bei r das r-bit auf 0 und "findet" ein r-bit =0 bei s, was er im folgenden ersetzt mit v. Darauffolgend setzt er das r-bit von v auf 1 usw....

wie ihr seht ist eigentlich das Hauptproblem, wie verhält sich der Algo, wenn bei einem Zugriff kein Seitenfehler auftritt, verändert sich der Zeiger ? also ein Hit vorliegt. Am konsistentesten zu den Folien wäre die Version 2, weil die Folien ja leider so unausführlich sind und nur besagen:" Bei zugriff wird r-bit gesetzt", aber dann verwirrt es mich warum wir initial Seiten reinladen und r-bits 0 sind obwohl das auch Zugriffe sind.
Oder ich bin generell gerade etwas verwirrt und werf sachen übereinander. Hilfe wäre hilfreich =)

Vielen Dank

grüße

[AlexPi11]

Hmmmm... stimmt, hier hätte man ruhig noch eine Folie spendieren können.

Am Zeiger passiert nicht, außer es muss etwas ersetzt werden. Behaupte ich jetzt einfach mal dreist.
Der Clock-Algorithmus ist ja der Second-Chance-Algorithmus - nur schöner. Der Second-Chance-Algorithmus wiederum ist wie FIFO, nur dass Seiten, die benutzt wurden, sich nochmal hinten an die Schlange anstellen dürfen, anstatt ersetzt zu werden. Der Zeiger ist nun nichts anderes, als der Anfang der Schlange.

Um das mit der Musterlösung zu vereinbaren, müsste man das r-Bit von neuen Seiten 0 setzen. Also würde das folgendem in Variante 2 widersprechen.

...und ersetzt mit u und r-bit auf 1 gesetzt...

Aber warum man jetzt bei neuen Seiten das r-Bit 0 setzen sollte... - kA.

Im Kommentar der Lösung steht folgendes:

In diesem Fall ist die 2-Hand-Clock-Strategie ebenso effektiv wie echtes LRU.

Wo kommt der 2te Zeiger her und welchen Winkel hat er zum vorderen?
Wenn man animmt, dass der Zeiger, der auf 0 setzt, dem anderen mit 90° Abstand (also direkt dahinter) folgt, dann wäre das wie, als ob man bei neuen Seiten das r-Bit=0 setzt. Also könnte es auch sein, dass neue Seiten mit r-Bit = 1 in die Warteschlange kommen und uns ein zweiter Zeiger verheimlicht wurde.

Auf alle Fälle bin ich jetzt auch verwirrt.

[Patr0rc]

Hallo.
Meines Erachtens nach ist Variante 1 korrekt, denn ein Zugriff auf eine Seite bedeutet automatisch, dass das r-Bit auf 1 gesetzt wird. Werden also Seiten geladen, wird ja auf sie zugegriffen und deshalb werden ihre r-Bits auf 1 gesetzt.
Es ergibt keinen Sinn, zwei Zeiger zu benutzen, da ein Clockalgorithmus ausreicht und somit kein 2-Hand-Clockalgorithmus gebraucht wird (ich glaube, hier ist die MuLö mal wieder falsch).
Ich hab es mit Variante 1 gemacht und sehe diese Variante auch eher mit dem Skript konform als Variante 2...

[Niggi]

also ich fand Version 1 auch schöner, aber was da halt etwas rumgemogelt ist und so nie im Skript erwähnt wird, ist die Behandlung eines Hit, dass sich der Zeiger bewegt alles zwischen "Hitseite" und aktueller position auf null ballert ... ich weiß nicht, so ne offizielle Erklärung wäre cool

[alex05]

Also das Problem mit dem zwei Zeigern geht glaub ich auf die Übung aus dem letzten Jahr zurück, dort wird die Aufgabe in der 10.Übung mit einer 2-Hand-Clock-Strategie gestellt, in der Lösung vom letzten Jahr wird dann seltsamerweise eine "normale" Clock-Strategie verwendet...
Sieht mal wieder noch Copy&Paste aus, ohne sich den Kontext anzuschauen...

[Patr0rc]

also ich fand Version 1 auch schöner, aber was da halt etwas rumgemogelt ist und so nie im Skript erwähnt wird, ist die Behandlung eines Hit, dass sich der Zeiger bewegt alles zwischen "Hitseite" und aktueller position auf null ballert ... ich weiß nicht, so ne offizielle Erklärung wäre cool

Naja, eigentlich ist das doch nicht so schwer bei einem Hit:
Du bewegst den Zeiger so lange vorwärts, bis du bei deinem Hit bist. Alle Seiten dazwischen werden entsprechend nach ihrem r-Bit behandelt: Für r=0 wird die Seite rausgeworfen und bei r=1 wird r:=0 gesetzt. Wenn du bei deinem Hit angekommen bist, setzt du dessen r:=1 und den Zeiger eins weiter.
Oder siehst du das anders?

[Niggi]

ja
ich bewege meinen zeiger entlang bei einem hit und schmeiße nix raus bei r=0 geh ich einfach nur weiter und bei r=1 setze ich auf r=0 , sonst wäre es ja komisch bei einem Hit etwas rauszuschmeißen .

Ja natürlich ist das nicht schwer zu verstehen, nur ob das jetzt wirklich richtig ist , das ist doch meine eigentliche Frage ?

ob du richtig stehst, merkst du wenn das licht angeht .... ich hoffe mein Licht kommt noch vor der klausur

[Sascha]

Es gibt leider immer noch jedes Jahr Verwirrung um den Clock-Algorithmus, da leider die verschiedenen Quellen unterschiedliche Begrifflichkeiten verwenden, sich auch die angegebenen Algorithmen in Details unterscheiden und bisher die entsprechenden Folien wie Sie bemerkt haben etwas dünn sind.

Genügt es Ihnen, wenn ich schreibe, dass weder 2-Hand-Clock noch irgendein anderer Algorithmus, der "Clock" im Namen hat, in der Klausur vorkommt?

[Niggi]

genügt mir vollends

[Patr0rc]

Mir auch, danke!

[newizz]

Genügt es Ihnen, wenn ich schreibe, dass weder 2-Hand-Clock noch irgendein anderer Algorithmus, der "Clock" im Namen hat, in der Klausur vorkommt?

Das genügt mir vollem,da ich nicht mehr daran setzen muss..

[LucasR]

Perfekt, danke!