LRU-Approximation Page Replacement
i. Additional reference bits algorithm:
The ordering information can be gained by recording
the reference bits at regular intervals:
Storing the most recent 8 reference bits for each page in an 8-bit byte
in the page table entry, which is interpreted as an unsigned integer.
At periodic intervals ( clock interrupts ), the OS
takes over, and right-shifts each of the reference bytes by one bit.
The high-order ( leftmost ) bit is then filled in
with the current value of the reference bit, and the reference bits are
cleared.
At any given time, the page with the smallest value
for the reference byte is the LRU page.
Ex:
00000000 indicates page has not been used for
eight time periods.
11000100 indicate that page had referenced recently.
If the eight bit are interpreted as unsigned
integers, the page with lowest number is the page to be replaced.
ii. Second chance algorithm:
The basic algorithm of second chance replacement is
a FIFO replacement algorithm. When a page has been selected, the reference bit
is inspected. If the value is 0, the page is replaced but if the reference bit
is set to 1, the page is given 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 have been
replaced.
One way to implement the second chance algorithm is
a circular queue. Second chance replacement degenerates to FIFO replacement if
bits of all pages are set.
iii. Enhanced second-chance algorithm:
The enhanced second chance algorithm looks
at the reference bit and the modify bit ( dirty bit ) as an ordered
page, and classifies pages into one of four classes:
- (
0, 0 ) - Neither recently used nor modified.
- (
0, 1 ) - Not recently used, but modified.
- (
1, 0 ) - Recently used, but clean.
- (
1, 1 ) - Recently used and modified.
This algorithm searches the page table in a circular
fashion ( in as many as four passes ), looking for the first page it
can find in the lowest numbered category. I.e. it first makes a pass looking
for a ( 0, 0 ), and then if it can't find one, it makes another
pass looking for a ( 0, 1 ), etc.
The main difference
between this algorithm and the previous one is the preference for replacing
clean pages if possible.
No comments:
Post a Comment