11.1 b Clock Algorithmus

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

Beitrag von mantra »

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
BSc Spammer
BSc Spammer
Beiträge: 1047
Registriert: 1. Dez 2003 11:52
Wohnort: Frankfurt
Kontaktdaten:

Beitrag von Thorti »

Hallo,
mantra hat geschrieben:kontraintuitiv
Das Wort gefällt mir :wink:

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
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 »

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
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 238
Registriert: 5. Okt 2005 15:52

Beitrag von Julius »

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 ^^

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

Beitrag von mantra »

Okay :twisted:

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

Beitrag von Thorti »

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
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 »

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

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

Beitrag von 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
BSc Spammer
BSc Spammer
Beiträge: 1047
Registriert: 1. Dez 2003 11:52
Wohnort: Frankfurt
Kontaktdaten:

Beitrag von Thorti »

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 :wink: 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
Assistent zur Vorlesung TGDI im WS 11/12

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

Beitrag von Thorti »

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
Assistent zur Vorlesung TGDI im WS 11/12

Antworten

Zurück zu „Archiv“