Page 193 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes Figure 5.34: Use of a Stack to Record the most recent Page References

Reference string
4 7 0 7 1 0 1 2 1 2 7 1 2

2 7 a b

1 2

0 1

7 0

4 4

Stack before a Stack after b

5.11.4 Additional-Reference-Bits Algorithm
We can gain additional ordering information by recording the reference bits at regular intervals.
We can keep an 8-bit byte for each page in a table in memory. At regular intervals (say, every
100 milliseconds), a timer interrupt transfers control to the operating system. The operating
system shifts the reference bit for each page into the high-order bit of its 8-bit byte, shifting the
other bits right 1 bit, discarding the low-order bit. These &bit shift registers contain the history
of page use for the last eight time periods. If the shift register contains 00000000, then the page
has not been used for eight time periods; a page that is used at least once each period would
have a shift register value of 11111111. A page with a history register value of 11000100 has been
used more recently than has one with 01110111. If we interpret these 8-bit bytes as unsigned
integers, the page with the lowest number is the LRU page, and it can be replaced. Notice that the
numbers are not guaranteed to be unique, however. We can either replace (swap out) all pages
with the smallest value, or use a FIFO selection among them. The number of bits of history can
be varied, of course, and would be selected (depending on the hardware available) to make the
updating as fast as possible. In the extreme case, the number can be reduced to zero, leaving only
the reference bit itself. This algorithm is called the second-chance page replacement algorithm.

5.11.5 Second-chance Algorithm
The basic algorithm of second-chance replacement is a FIFO replacement algorithm. When a
page has been selected, however, we inspect its reference bit. If the value is 0, we proceed to
replace this page. If the reference bit is set to 1, however, we give that page a second chance
and move on to select the next FIFO page. When a page gets a second chance, its reference bit
is cleared and its arrival time is reset to the current time. Thus, a page that is given a second
chance will not be replaced until all other pages are replaced (or given second chances). In
addition, if a page is used often enough to keep its reference bit set, it will never be replaced.
One way to implement the second-chance (sometimes referred to as the clock) algorithm is as a
circular queue. A pointer indicates which page is to be replaced next. When a frame is needed,
the pointer advances until it finds a page with a 0 reference bit. As it advances, it clears the
reference bits. Once a victim page is found, the page is replaced, and the new page is inserted in
the circular queue in that position. Notice that, in the worst case, when all bits are set, the pointer
cycles through the whole queue, giving each page a second chance. It clears all the reference
bits before selecting the next page for replacement. Second-chance replacement degenerates to
FIFO replacement if all bits are set.

186 LOVELY PROFESSIONAL UNIVERSITY