Sie sind nicht angemeldet.

sebid

Junior Schreiberling

  • »sebid« ist männlich
  • »sebid« ist der Autor dieses Themas

Beiträge: 168

Registrierungsdatum: 05.10.2004

Wohnort: Hannover

1

08.09.2010, 17:51

[Betriebssysteme] Least-Frequently-Used, Least-Recently-Used, Not-Recently-Used?

Hallo,

probiere mich gerade an alten Klausuraufgaben, dort wird nach dem Paging-Verfahren "Least-Recently-Used" gefragt.
Im Skript und in den Übungen findet sich aber nur "Least-Frequently-Used" und "Not-Recently-Used".

Wo ist LRU?

Noch merkwürdiger: die Überschrift zur Folie (T13.pdf, Seite 9, Folie 35) Seitenersetzung spricht von LFU und LRU, auf der Folie gibt's dann aber LFU und NRU.

Sollte etwas NRU und LRU am Ende das gleiche sein?


Sehr verwirrend…
Cee Uhh!
:o) sebid

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »sebid« (08.09.2010, 17:53)


Skuld

Erfahrener Schreiberling

  • »Skuld« ist männlich

Beiträge: 344

Registrierungsdatum: 02.10.2007

Beruf: Student

2

08.09.2010, 18:40

Letzteres stimmt, so weit ich das im Kopf habe.

Not recently used = Es wird die Page verdrängt, die in letzter Zeit nicht benutzt wurde, also die, die den ehesten Zugriffszeitpunkt hat.
Least recently used = Es wird die Page verdrängt, die am wenigsten "recent" benutzt wurde. Also ebenfalls die, die den ehesten Zugriffszeitpunkt hat.
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

Salz

Opa

  • »Salz« ist männlich

Beiträge: 144

Registrierungsdatum: 03.12.2009

3

08.09.2010, 18:45

Eine kurze Suche auf Google ergibt u.a. diese Links zum Thema:

http://en.wikipedia.org/wiki/Page_replacement_algorithm
http://www.lira.dist.unige.it/teaching/OS/files/sample-4.pdf

LRU ist nicht NRU, sondern ein um einiges aufwändigerer Algorithmus, der zu jeder Seite den letzten Zugriffszeitpunkt speichert und dann die Seite ersetzt, die tatsächlich am längsten unbenutzt ist. Die Implementierung davon ist allerdings ziemlich aufwändig.

NRU ersetzt einfach nur eine Seite zufällig, derern Referenz-Bit = 0 ist. Diese Bits werden regelmäßig alle gelöscht, so daß NRU nur bis zum Löschen aller Referenz-Bits die Nutzung der Seite kennt.
Damals…

Skuld

Erfahrener Schreiberling

  • »Skuld« ist männlich

Beiträge: 344

Registrierungsdatum: 02.10.2007

Beruf: Student

4

08.09.2010, 18:55

Ah, tatsächlich. NRU arbeitet so:

Höchste Priorität: Ersetze eine noch nicht referenzierte Seite (r=0)
Falls alle schon benutzt: Ersetze eine noch nicht modifizierte Seite (d=0)
Falls auch alle schon modifiziert: Teile die Pages in Klassen ein:
r=0, d=0 => Klasse 0
r=0, d=1 => Klasse 1
r=1, d=0 => Klasse 2
r=1, d=1 => Klasse 3

Nun wird eine zufällige Page aus der niedrigsten nicht-leeren Klasse verdrängt.

Und, wie Salz auch schon sagte, die r-bits werden regelmäßig für alle wieder auf 0 gesetzt, und zwar genau dann, wenn sämtliche r-bits auf 1 stehen.
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?