Page 194 - DCAP103_Principle of operating system

Unit 5: Memory Management

Figure 5.35: Second-chance (clock) Page-replacement Algorithm Notes

Reference Pages Reference Pages
bits bits
EI

0

Next
victim 1 EI

1

0
. . . .
. . . .
. . . .
1

1

Circular queue of pages Circular queue of pages
(a) (b)

5.11.6 Enhanced Second-chance Algorithm

We can enhance the second-chance algorithm by considering both the reference bit and the
modify bit as an ordered pair. With these two bits, we have the following four possible classes:
1. (0,0) neither recently used nor modified—best page to replace

2. (0,l) not recently used but modified—not quite as good, because the page will need to be
written out before replacement
3. (1,0) recently used but clean—it probably will be used again soon
4. (1,l) recently used and modified—it probably will be used again soon, and the page will be
need to be written out to disk before it can be replaced when page replacement is called
for, each page is in one of these four classes.
We use the same scheme as the clock algorithm, but instead of examining whether the
page to which we are pointing has the reference bit set to 1, we examine the class to
which that page belongs. We replace the first page encountered in the lowest nonempty
class. Notice that we may have to scan the circular queue several times before we find
a page to be replaced.
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/Os required.

5.11.7 Counting-based Page Replacement
There are many other algorithms that can be used for page replacement. For example, we could
keep a counter of the number of references that have been made to each page, and develop the
following two schemes.

LOVELY PROFESSIONAL UNIVERSITY 187