Fachrat Informatik - Forum

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.

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.

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.