LRU-Approximation Page Replacement

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:

1. ( 0, 0 ) - Neither recently used nor modified.
2. ( 0, 1 ) - Not recently used, but modified.
3. ( 1, 0 ) - Recently used, but clean.
4. ( 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.