11.1 b Clock Algorithmus

mantra · Beitrag von **mantra** » 21. Jan 2007 18:17

Hört sich nicht nur ineffizient an, sondern auch kontraintuitiv. Außerdem führt das anders als mit 1en stehen lassen ironischerweise zu der Situation, dass alle r-bits gesetzt sind (wohl, weil der Clock-Interrupt fehlt). Und plötzlich entscheidet die Strategie, ob man den Zeiger vorrückt oder nicht, darüber, wieviele Hits man hat..

Ist das wieder eine dieser "beispielsweise" Aufgaben, nur dass man das "beispielsweise" diesmal aus den in der Aufgabenstellung vorhanden Buchstaben selbst entnehmen muss?

Thorti · Beitrag von **Thorti** » 21. Jan 2007 19:00

Hallo,

mantra hat geschrieben:kontraintuitiv

Das Wort gefällt mir

Zum Thema: Hab den Tannenbaum nicht da, aber bei jedem Seitenfehler ALLE R-Bits auf 0 setzten kommt mir irgendwie seltsam vor...

Mein Verständnis des Algorithmus ist eigentlich so:
Man ordnet die Kacheln des Hauptspeichers im Kreis an (hier 4 Kacheln). Jede Kachel hat ein R-Bit, welches am Anfang 0 ist (ist ja noch leer). Der Zeiger zeigt auf die erste Kachel. Tritt nun ein Seitenfehler auf (d.h. das Element, auf das zugegriffen werden soll ist nicht im Speicher) sucht der Zeiger im Uhrzeigersinnn nach einer Kachel, deren R-Bit 0 ist. Während dieser Suche setzt er alle R-Bits, über die er geht auf 0. Wenn er eine Kachel gefunden hat, deren R-Bit 0 ist, wird diese Seite ausgelagert und durch die neue ersetzt. Das R-Bit wird auf 1 gesetzt. Bei der nächsten Anfrage läuft er zum nächsten Kachel und beginnt seine Suche dort. Tritt kein Seitenfehler auf, wird das entsprechende R-Bit auf 1 gesetzt.

Ich weis, im Skript auf Folie 9-180 steht es etwas anders. Ich weis nicht, was da in der Vorlesung dazu gesagt wurde, denke aber der Unterschied ist, dass hier immer nach dem Ersetzen noch eins vorgerückt wird und dann die neue Suche immer unter dem Zeiger begonnen wird. Das hat aber imho den selben Effekt.
Der Satz "Der Zeiger zeigt auf die älteste Seite" verstehe ich so auch nicht wirklich...

Gruss Thorti

mantra · Beitrag von **mantra** » 21. Jan 2007 19:05

Bei der nächsten Anfrage läuft er zum nächsten Kachel und beginnt seine Suche dort. Tritt kein Seitenfehler auf, wird das entsprechende R-Bit auf 1 gesetzt.

Das heißt, dass der Zeiger in jedem Zeitschritt vorrückt? Und der Zeiger zeigt immer auf das zuletzt benutzte Element, nicht auf das zuletzt Eingelagerte bzw dessen Nachfolger?

Julius · Beitrag von **Julius** » 21. Jan 2007 19:09

Ich denke das heisst, dass keiner Bescheid weiß und wir auf gut Glück morgen eine Hausübung abgeben und sich der Tutor auf Diskussionen über abgezogene Punkte wegen der schlechten Aufgabenstellung freuen darf...

oder dass ich das ganze nun zum 3. Mal mache und darauf hoffe, dass es dann stimmt ^^

mantra · Beitrag von **mantra** » 21. Jan 2007 19:10

Okay

Thorti · Beitrag von **Thorti** » 21. Jan 2007 19:34

Hallo,

mantra hat geschrieben:
Bei der nächsten Anfrage läuft er zum nächsten Kachel und beginnt seine Suche dort. Tritt kein Seitenfehler auf, wird das entsprechende R-Bit auf 1 gesetzt.
Das heißt, dass der Zeiger in jedem Zeitschritt vorrückt? Und der Zeiger zeigt immer auf das zuletzt benutzte Element, nicht auf das zuletzt Eingelagerte bzw dessen Nachfolger?

Nein. Sorry, war wohl missverständlich. Nur wenn ein Seitenfehler auftritt bewegt sich der Zeiger. Wenn kein Seitenfehler auftritt wird nur das entsprechende R-Bit auf 1 gesetzt.

Gruss Thorti

mantra · Beitrag von **mantra** » 21. Jan 2007 19:51

Okay

Und kannst du mir noch sagen, an welches Verfahren ich mich bei der c) halten soll? (siehe dort)

The One and Only Markus

Also um der allgemeinen Verwirrung evt. ein Ende zu setzen schreibe ich mal meinen Algo so auf wie ich ihn ausgeführt habe. Falls der so als richtig angesehen wird (= Bestätigung von Thorti ^^) können es ja alle so machen. Dann sind alle auf einem Nenner, alle bekommen viele Punkte und alle sind glücklich ohne lange Diskussionen.

Code: Alles auswählen

n := Anzahl gespeicherter Seiten
s[n] := Speicher

01. setze alle R-Bits auf 0
02.  i := 0
03. setze Zeiger auf s[i]
04. hole nächsten Seitenzugriff aus dem Referenzstring
05. falls Seite im Speicher:
06.   --> setze R-Bit der Speicherstelle wo die Seite gespeichert ist auf 1; weiter bei 4
07. falls Seite nicht im Speicher:
08.   --> prüfe R-Bit an Stelle s[i]
09.    falls s[i]=1:
10.      --> setze s[i]=0; i=nächste Speicherposition; weiter bei 8
11.    falls s[i]=0:
12.      --> angeforderte Seite in s[i] speichern; i=nächste Speicherposition; weiter bei 4

PS: Der Satz "Der Zeiger zeigt auf die älteste Seite" ist bei mir dann auch erfüllt. Der Zeiger zeigt nämlich immer auf die Kachel, die als ersten von den 4 eingelagert wurde.

Thorti · Beitrag von **Thorti** » 21. Jan 2007 20:12

Hallo,

The One and Only Markus hat geschrieben:Also um der allgemeinen Verwirrung evt. ein Ende zu setzen schreibe ich mal meinen Algo so auf wie ich ihn ausgeführt habe. Falls der so als richtig angesehen wird (= Bestätigung von Thorti ^^) können es ja alle so machen.

Ich finde deinen Code in Ordnung

ABER wie gesagt war ich nicht in der Vorlesung. Jedoch habe ich mal das mit dem Referenzstring gemacht und es stimmt mit der MuLö überein.

Dann sind alle auf einem Nenner, alle bekommen viele Punkte und alle sind glücklich ohne lange Diskussionen.

Darauf gibt es eh nur 1 Punkt.

Gruss Thorti

Thorti · Beitrag von **Thorti** » 21. Jan 2007 20:12

Hallo,

mantra hat geschrieben:Okay Und kannst du mir noch sagen, an welches Verfahren ich mich bei der c) halten soll? (siehe dort)

Antwort siehe dort.

Gruss Thorti