The second-chance
algorithm can be enhanced by considering both the reference bit and the modify
bit (refer second chance algorithm for information about R and M bit).
R and M bits can be used
to build a simple algorithm.
When a process is started
up, both page bits for all its pages are set to 0 by the operating system.
Periodically (e.g. on each
clock interrupt), the R bit is cleared to distinguish pages that have not been
referenced recently from those that have been referenced.
When a page fault occurs,
the operating system inspects all the pages divides them into four categories
(classes) based on the current values of their R and M bits.
R M
|
|||
Class 0
|
(0,0)
|
Not referenced
(not recently used)
Not modified
(clean)
|
Best page to
replace
|
Class 1
|
(0,1)
|
Not referenced,
modified
|
Not as good
because the page will need to be written out before replacement.
|
Class 2
|
(1,0)
|
Referenced, not
modified
|
Probably will be
used again soon
|
Class 3
|
(1,1)
|
Referenced,
modified
|
Probably will be
used again and will need to be written out before replacement.
|
When page replacement is
called for, each page is one of these four classes. We examine the class to
which that page belongs.
Although class 1 pages
seem impossible, but they occur when a class 3 page has it its R bit cleared by
a clock interrupts.
Clock interrupt do not
clear the M bit because this information is needed to know
Whether the page has be
written to disk or not.
We replace the first
page/random page encountered in the lowest nonempty class.
It is better to remove a
modified page that has not been referenced in at least one clock tick
(typically 20msec) than a clean page that is in heavy use.
The main attraction of NRU
is that is easy to understand, efficient to implement, and gives a performance
that while certainly not optimal is often adequate.
This algorithm is used in
the Macintosh, virtual-memory-management scheme. The major difference between
this algorithm and the simpler clock algorithm is that here we give preference
to those pages that have been modified to reduce the number of i/o s required.