11.1 b Clock Algorithmus

Jannik
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 20. Okt 2005 12:01
Wohnort: Darmstadt
Kontaktdaten:

11.1 b Clock Algorithmus

Beitrag von Jannik »

Bonjour,

nach einer verwirrenden und langen Diskussion mit einem Komilitonen habe ich mich entschlossen hier mal zu fragen wie eigentlich dieser Clock-Algorithmus funktionieren soll. In den Folien ist die ganze Geschichte nämlich ziemlich unterspezifiziert, z.B. wird mit keinem Wort erwähnt wann das r-Bit gesetzt wird, nur wann es zurückgesetzt wird.

Folgendes habe ich mir mit Hilfe meines Tutors und der allmächtigen Wikipedia zusammengereimt:

Das r-Bit wird einfach bei jedem Zugriff auf die entsprechende Kachel gesetzt. D.h. dass es _auch_ gesetzt wird wenn die Kachel eingelagert wurde - da sie ja dann sofort gelesen bzw. geschrieben wird. Der Zeiger bleibt nach dem Einlagern auf dieser Kachel stehen bis zum nächsten Fehltreffer. Tritt der nächste Fehltreffer auf wird der Zeiger weitergeschoben, in dem Moment wo er aus der Kachel "herausgeschoben" wird wird das r-Bit wieder auf 0 gesetzt.

Ist meine kleine Exegese jetzt zulässig oder war das alles ganz anders gemeint?

Ach ja, in den Folien wird noch gesagt "der Zeiger der Uhr steht auf der ältesten Seite". Am Anfang? Immer? Kann beides irgendwie nicht sein (wie man sich leicht überlegen kann).
RC_KILL_CHILDREN="yes"

BastiS
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 224
Registriert: 3. Nov 2005 19:12
Kontaktdaten:

Beitrag von BastiS »

Also so haben wir es auch verstanden.
Wobei bei uns der Zeiger immer auf der ältesten Seite steht.
Ist zwar tatsächlich schwierig zu implementieren, aber immerhin steht das eindeutig in den Folien und somit kann uns da niemand was anhaben, falls das nicht so gedacht war. ;-)

Jannik
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 20. Okt 2005 12:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Jannik »

Das heißt er läuft immer von der ältesten Seite aus los sobald ein Miss eintritt?

Anders kann man das ja nicht machen, denn wenn "zu Beginn" gemeint wäre gäbe es ja garkeine sinnvolle Art "älteste Seite" zu definieren da noch gar keine Seite eingelagert wurde.

Wenn der Zeiger immer nur weitergeschoben wird steht er logischerweise nicht immer auf der ältesten Seite weil es ja möglich ist dass die eine zweite Chance bekommen hat.

Das würde aber auch bedeuten dass man einen zweiten Modulo-Zähler für den Zeiger braucht der strikt FIFO macht und auf den der Zeiger bei jedem Miss zurückgesetzt wird. Von dem hab ich aber in den Folien nichts gelesen und ich glaube rein praktisch betrachtet wäre das Schwachsinn. Wären ja dann zwei Zeiger. Stunden und Minuten oder so... O_o

Wäre aber cool wenn sich dazu noch mal ein Tutor oder jemand anders der zuständig ist äußern könnte...
RC_KILL_CHILDREN="yes"

Thorti
BSc Spammer
BSc Spammer
Beiträge: 1047
Registriert: 1. Dez 2003 11:52
Wohnort: Frankfurt
Kontaktdaten:

Re: 11.1 b Clock Algorithmus

Beitrag von Thorti »

Hallo,
Jannik hat geschrieben:n den Folien ist die ganze Geschichte nämlich ziemlich unterspezifiziert, z.B. wird mit keinem Wort erwähnt wann das r-Bit gesetzt wird, nur wann es zurückgesetzt wird.
Ja, das steht da irgendwie nicht :evil:
Das r-Bit wird einfach bei jedem Zugriff auf die entsprechende Kachel gesetzt. D.h. dass es _auch_ gesetzt wird wenn die Kachel eingelagert wurde - da sie ja dann sofort gelesen bzw. geschrieben wird.
Ja. Sonst ist das Verfahren sinnlos.
Der Zeiger bleibt nach dem Einlagern auf dieser Kachel stehen bis zum nächsten Fehltreffer. Tritt der nächste Fehltreffer auf wird der Zeiger weitergeschoben, in dem Moment wo er aus der Kachel "herausgeschoben" wird wird das r-Bit wieder auf 0 gesetzt.
Hört sich gut an.
BastiS hat geschrieben:Wobei bei uns der Zeiger immer auf der ältesten Seite steht.
Jein. Wenn in der Zeit (wie Jannik in seinem 2.Post schreibt) ein Zugriff auf diese Seite kommt, wird das r-Bit wieder auf 1 gesetzt. Somit steht der Zeiger dann nicht mehr über der ältesten Seite.
Jannik hat geschrieben:Das würde aber auch bedeuten dass man einen zweiten Modulo-Zähler für den Zeiger braucht der strikt FIFO macht und auf den der Zeiger bei jedem Miss zurückgesetzt wird. Von dem hab ich aber in den Folien nichts gelesen und ich glaube rein praktisch betrachtet wäre das Schwachsinn. Wären ja dann zwei Zeiger. Stunden und Minuten oder so... O_o
Das vergessen wir am besten schnell.

Ich hoffe das hilft, wenn nicht gerne nochmal fragen.

Gruss Thorti
Assistent zur Vorlesung TGDI im WS 11/12

Jannik
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 20. Okt 2005 12:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Jannik »

Yup danke! :)
RC_KILL_CHILDREN="yes"

MuldeR
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 18. Okt 2005 16:14
Wohnort: (d)armstadt
Kontaktdaten:

Beitrag von MuldeR »

Im Skript steht:
[font=Courier New]"Second Chance (SC): Es wird wie beim FIFO ersetzt. Allerdings werden Seiten übersprungen, auf die seit dem letzten Seitenfehler zugegriffen wurde"[/font]

Daraus kann man schließen, dass das R-Bit nicht dirket beim Einlagern einer Seite gesetzt wird, sondern nur falls auf die Seite danach noch einmal zugegriffen wird. Sprich: R-Bit auf 1 setzten findet bei einem "Hit" statt.

// EDIT

Was ich noch nich gefunden hab: Wie ist das beim Aging? Wann werden hier die R-Bits gesetzt bzw. zurückgesetzt? Also wenn ich eine Seite zum ersetzten auswähle, weil sie den niedrigsten Counter hat, aber das R-Bit noch auf 1 steht, wird die Seite dan sofort ersetzt, oder setz ich erstmal das R-Bit auf 0 zurück und ersetzte die Seite mit dem nächst kleineren Counter ???

The One and Only Markus
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 169
Registriert: 10. Nov 2005 19:28
Wohnort: Darmstadt

Re: 11.1 b Clock Algorithmus

Beitrag von The One and Only Markus »

Thorti hat geschrieben:
Jannik hat geschrieben: Der Zeiger bleibt nach dem Einlagern auf dieser Kachel stehen bis zum nächsten Fehltreffer. Tritt der nächste Fehltreffer auf wird der Zeiger weitergeschoben, in dem Moment wo er aus der Kachel "herausgeschoben" wird wird das r-Bit wieder auf 0 gesetzt.
Hört sich gut an.
Das kann nicht sein. Wenn eine Kachel ausgelagert wird um eine neue einzulagern wird erst ein- und ausgelagert und der Zeiger dann vorgerückt. Der Zeiger bleibt also keinesfalls auf der neue eingelagerten Kachel stehn (siehe Folie 9-180). Das wäre ja auch sinnlos, da dann der Zeiger auf der neusten Kachel steht und nicht auf der ältesten.

Gruß,
Markus

Thorti
BSc Spammer
BSc Spammer
Beiträge: 1047
Registriert: 1. Dez 2003 11:52
Wohnort: Frankfurt
Kontaktdaten:

Beitrag von Thorti »

Hallo,

also meiner Meinung nach kann man beides machen.
Entweder man bleibt nach dem Zugriff darauf stehen und rückt beim nächsten Zugriff vor und testet dort.
Oder man rückt direkt nach dem Zugriff vor und testet beim nächsten Zugriff dort.
Das sollte doch den selben Effekt haben.

Gruss Thorti
Assistent zur Vorlesung TGDI im WS 11/12

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Beitrag von mantra »

MuldeR hat geschrieben:Im Skript steht:
[font=Courier New]"Second Chance (SC): Es wird wie beim FIFO ersetzt. Allerdings werden Seiten übersprungen, auf die seit dem letzten Seitenfehler zugegriffen wurde"[/font]

Daraus kann man schließen, dass das R-Bit nicht dirket beim Einlagern einer Seite gesetzt wird, sondern nur falls auf die Seite danach noch einmal zugegriffen wird. Sprich: R-Bit auf 1 setzten findet bei einem "Hit" statt.
Das sehe ich auch so und finde es auch sinnvoller. Wenn man z.B. 3 Seiten Platz hat und am Anfang 4x einlagern muss und alle r-bits wären schon auf 1, dann müsste man eine überflüssige Runde drehen, um die älteste Seite rauszuschmeißen. Wenn jetzt aber zwischendrin auf die älteste Seite zugegriffen würde, würde sie immernoch als erste ausgelagert, weil die anderen auch schon alle ihr r = 1 haben. Dabei verdient gerade diese Seite eine zweite Chance.

*edit: Dann muss auch der Zeiger beim Einlagern vorgerückt werden, sonst würde beim nächsten Seitenfehler die gerade eingelagerte Seite wieder verdrängt.

Randy
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 21. Okt 2005 15:27

Beitrag von Randy »

Laut Tanenbaum laeuft es folgendermassen ab:

Das R-Bit wird ausschliesslich durch die Hardware auf 1 gesetzt und zwar bei jedem Schreib-/Lesezugriff, d.h. auch beim Einlagern im Zuge eines Seitenfehlers. Das ist ganz unabhaengig vom verwendeten Algorithmus. Das Betriebssystem erhaelt durch einen "Clock Interrupt" alle paar Millisekunden die Kontrolle und setzt alle R-Bits auf 0 zurueck. Wenn dann irgendwann ein Seitenfehler auftritt, gibt es zwei Faelle:

(i) Es ist noch Platz, d.h. keine Seite muss ersetzt werden. Dann ist das Vorgehen wie bei FIFO: einfach die neue Seite hinten anhaengen und R-Bit der neuen Seite auf 1 setzen. Der Zeiger bleibt wo er ist.

(ii) Kein Platz mehr, eine Seite muss ersetzt werden. Das Betriebssystem inspiziert das R-Bit der Seite, auf die der Zeiger gerade zeigt. Wenn das R-Bit 0 ist wurde die Seite seit dem letzten Clock Interrupt nicht referenziert und kann ersetzt werden. Wenn das R-Bit 1 ist dann wurde die Seite seit dem letzten Clock Interrupt benutzt und erhaelt die zweite Chance, d.h. das R-Bit wird auf 0 gesetzt und der Zeiger in der Liste um eine Position weitergerueckt, bis ein Element gefunden wird, dessen R-Bit 0 ist. Im schlimmsten Fall muss also die ganze Liste einmal durchlaufen werden, bis man wieder vorne ankommt (zyklisch verkettet). Dann ist das Verfahren zu FIFO entartet.

Da es bei der Aufgabe keinen Clock Interrupt gibt scheint es Sinn zu machen, bei einem Seitenfehler erst eine passende Seite zum Ersetzen auszusuchen (falls erforderlich), d.h. eine Seite zu finden, deren R-Bit 0 ist (so lange den Zeiger weiterruecken und R-Bits zuruecksetzen bis eine Seite mit R-Bit = 0 gefunden wurde). Diese Seite dann ersetzen, alle R-Bits auf 0 setzen und nur das R-Bit der gerade ersetzen Seite auf 1 setzen. Auf die Seite zeigt dann auch der Zeiger. Im weiteren Verlauf der Seitenzugriffe werden die R-Bits dann wieder gesetzt bis zum naechsten Seitenfehler, usw.
Zuletzt geändert von Randy am 21. Jan 2007 16:01, insgesamt 1-mal geändert.

Julius
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 238
Registriert: 5. Okt 2005 15:52

Beitrag von Julius »

Das habe ich genau so gemacht, nur dass ich nicht nach dem Ersetzen alle R-Bits zurückgesetzt habe.

Bin mir aber gerade nicht ganz sicher, ob das sinnvoll ist.

Was spricht der Tutor dazu?

Randy
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 21. Okt 2005 15:27

Beitrag von Randy »

Alle R-Bits beim Ersetzen zurueckzusetzen wuerde sich mit der Aussage aus den Folien decken, dass Seiten, die seit dem letzten Seitenfehler referenziert wurden uebersprungen werden (= zweite Chance erhalten). Ob eine Seite seit dem letzten Seitenfehler referenziert wurde kann der Algorithmus nur feststellen, wenn er bei jedem Seitenfehler alle R-Bits zuruecksetzt, jedoch erst nachdem er eine Seite mit R-Bit = 0 zum Ersetzen gefunden hat, sonst wuerde es wenig Sinn ergeben.

Julius
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 238
Registriert: 5. Okt 2005 15:52

Beitrag von Julius »

da gebe ich dir Recht. Das passt zu den Folien. Dann korrigiere ich das mal schnell. ;-)

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Beitrag von mantra »

Argl... :evil:

Jannik
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 20. Okt 2005 12:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Jannik »

Randy hat geschrieben:Alle R-Bits beim Ersetzen zurueckzusetzen wuerde sich mit der Aussage aus den Folien decken, dass Seiten, die seit dem letzten Seitenfehler referenziert wurden uebersprungen werden (= zweite Chance erhalten). Ob eine Seite seit dem letzten Seitenfehler referenziert wurde kann der Algorithmus nur feststellen, wenn er bei jedem Seitenfehler alle R-Bits zuruecksetzt, jedoch erst nachdem er eine Seite mit R-Bit = 0 zum Ersetzen gefunden hat, sonst wuerde es wenig Sinn ergeben.
D.h. bei jedem Miss wird die Komplette Seitenliste einmal durchlaufen um jedes r-Bit auf 0 zu setzen? Hört sich ziemlich ineffizient an...
RC_KILL_CHILDREN="yes"

Antworten

Zurück zu „Archiv“