Clock Page Replacement Algorithm

karimhanif
Mausschubser
Mausschubser
Beiträge: 86
Registriert: 3. Mär 2009 14:13

Clock Page Replacement Algorithm

Beitrag von karimhanif »

hallöchen,

da die folien bzgl. des "Clock Page Replacement Algorithm" (Kapiel: Betriebssysteme) einfach mal nur stupider müll sind, wäre ich den einem oder anderem sehr verbunden für eine genaue erklärung, wie ganz genau dieser algorithmus arbeitet, insbesondere WANN nun das R-Bit auf "1" gesetzt wird...

hat jemand vielleicht ein brauchbaren link? habe mit meiner Lerngruppe nichts brauchbares finden können...


muchas gracias 8)

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Clock Page Replacement Algorithm

Beitrag von Steven »

Ich versuche mich mal an einer Erklärung: Betrachten wir zuerst den "Two-Hand" Algorithmus. Stelle dir dazu eine Uhr mit zwei Zeigern vor. Dort wo bei der Uhr die Uhrzeiten stehen, stehen hier die Speicherseiten. Wenn eine neue Seite angefordert wird und der Speicher voll ist, wird das r-Bit der Seite, auf die der erste Zeiger zeigt, auf 0 gesetzt. Dann rückt der Zeiger um eine Seite weiter. Der zweite Zeiger prüft, ob das r-Bit der Seite, auf die er gerade zeigt, 0 ist. Wenn ja, wird diese Seite ausgelagert und in ihren Page Frame kommt die neue Seite. Danach rückt dieser Zeiegr ebenfalls um eine Seite weiter. War das r-Bit 1, ist also nichts passiert.

Du kannst dir das so vorstellen: Immer wenn auf eine Seite zugegriffen wird, wird das r-Bit auf 1 gesetzt, die Seite also als aktuell markiert. Sucht man nun eine Seite zum Ersetzen (Zeiger 2), bekommen Seiten mit r=1 eine zweite Chance. Der erste Zeiger aktualisiert die r-Bits, stellt also sicher, dass nach der zweiten Chance das r-Bit 0 ist und die Seite "frei zum Abschuss" ist.

twinkletoes
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 17. Mär 2009 16:01

Re: Clock Page Replacement Algorithm

Beitrag von twinkletoes »

steven, dir ist aber schon klar das 2-clock nicht klausurrelevant ist, oder? ;-)

könntest du mir das verfahren anhand des normalen one-clock algos erklären..?? danke
It is what you read when you don't have to that determines what you will be when you can't help it. ~Oscar Wilde

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: Clock Page Replacement Algorithm

Beitrag von Steven »

Bei One-Clock hast du nur einen Zeiger, der beide Aufgaben übernimmt. Zeigt dieser auf eine Seite mit r-Bit = 1, setzt er das r-Bit auf 0 und wird zur nächsten Seite vorgerückt. Dort prüft er wieder das r-Bit. Wenn's wieder 1 ist, wird auch das zurückgesetzt und der Zeiger geht abermals weiter, usw. Das machst du solange, bist du eine Seite mit r-Bit = 0 gefunden hast. Schlimmstenfalls heißt das, die ganze Runde einmal abzulaufen und wieder bei der ersten Seite anzukommen (deshalb der Hinweis "Worst case: degeneriert zu FIFO") in den Folien. Nun hast du also eine Seite mit r=0 und diese ersetzt du.

Antworten

Zurück zu „Archiv“