Question

Explain LRU page replacement algorithm for following reference string. 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 Calculate the page fault.

Answer 1

LRU:

The Least Recently Used (LRU) page replacement policy replaces the page that has not been used for the longest period of time.

LRU replacement associates with each page the time of that page's last use.

When a page must be replaced, LRU chooses the page that has not been used for the longest period of time.

The LRU policy is often used as a page-replacement algorithm and is considered to be good.

An LRU page-replacement algorithm may require substantial hardware assistance.

Counters:

In the simplest case, we associate with each page-table entry a time-of-use field and add to the CPU a logical clock or counter.

The clock is incremented for every memory reference.

Whenever a reference to a page is made, the contents of the clock register are copied to the time-of-use field in the pagetable entry for that page.

In this way, we always have the "time" of the last reference to each page. We replace the page with the smallest time value.

Stack:

Another approach to implementing LRU replacement is to keep a stack of page numbers.

Whenever a page is referenced, it is removed from the stack and put on the top.

In this way, the most recently used page is always at the top of the stack and the least recently used page is always at the bottom.

Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

(Frame size have not mentioned in question so assume frame size as 3

or 4)

LRU: Assume frame size=3