clock Algorithmus Ü10 1.3

Niggi
Mausschubser
Mausschubser
Beiträge: 82
Registriert: 15. Apr 2009 15:16
Kontaktdaten:

clock Algorithmus Ü10 1.3

Beitrag von 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

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: clock Algorithmus Ü10 1.3

Beitrag von 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. :P
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.

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: clock Algorithmus Ü10 1.3

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 82
Registriert: 15. Apr 2009 15:16
Kontaktdaten:

Re: clock Algorithmus Ü10 1.3

Beitrag von 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
Erstie
Erstie
Beiträge: 22
Registriert: 13. Okt 2009 20:29

Re: clock Algorithmus Ü10 1.3

Beitrag von 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...

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: clock Algorithmus Ü10 1.3

Beitrag von Patr0rc »

Niggi hat geschrieben: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
Mausschubser
Mausschubser
Beiträge: 82
Registriert: 15. Apr 2009 15:16
Kontaktdaten:

Re: clock Algorithmus Ü10 1.3

Beitrag von 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 :-P

Sascha
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 245
Registriert: 13. Apr 2004 19:23
Wohnort: Darmstadt
Kontaktdaten:

Re: clock Algorithmus Ü10 1.3

Beitrag von 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
Mausschubser
Mausschubser
Beiträge: 82
Registriert: 15. Apr 2009 15:16
Kontaktdaten:

Re: clock Algorithmus Ü10 1.3

Beitrag von Niggi »

genügt mir vollends :)

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: clock Algorithmus Ü10 1.3

Beitrag von Patr0rc »

Mir auch, danke!

Benutzeravatar
newizz
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 30. Jun 2009 16:41

Re: clock Algorithmus Ü10 1.3

Beitrag von newizz »

Sascha hat geschrieben: 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.. :)
It's your ATTITUDE and not your APTITUDE that determines your ALTITUDE

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

Re: clock Algorithmus Ü10 1.3

Beitrag von LucasR »

Perfekt, danke! :)

Antworten

Zurück zu „Archiv“