FOR FREE MATERIALS

LRU page replacement algorithm

Least Recently Used (LRU) page replacement algorithm:

LRU policy follows the concept of locality of reference as the base for its page replacement decisions.

LRU policy says that pages that have not been used for the longest period of time will probably not be used for a long time.

So, when a page fault occurs, it is better to replace the page that has been unused for a long time. This strategy is called LRU (Least Recently Used) paging.

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

Disadvantage

The problem is to determine an order for the frames defined by the time of last use.

So, implementing LRU will require extra overhead either software implementation with extra computational time or implementation by hardware.

To implement LRU we can use a linked list of all pages in memory, with the most recent page at the font and the least recent page at the rare. So, update deletion and insertion of linked lists is a time-consuming operation.

Another way to implement LRU is special hardware either counter or stack. 

Example of LRU algorithm:

Consider the page reference string (GATE– 2015)

3, 8,  2,  3, 9,  1,  6, 3,  8,  9, 3,  6,  2, 1,  3

Find the number of page faults with LRU, where 5 page frames are present.

Solution:

Given page references or reference strings:

3, 8,  2,  3, 9,  1,  6, 3,  8,  9, 3,  6,  2, 1,  3

As per the concept of demand paging no pages will load until any request arises.

So, initially, frames are empty, now because our 5 frames are empty, we can load the first different 5 page references into frames.

Step 1: Now, we can load the first 5page references 3, 8, 2, 3, 9, but we are not considering page 3 a second time because it is already loaded in the frame. Now, we consider the next page 1, now it is new, not in frames, so, we load page 1 into the frame.

Step 2: Now, after loaded page reference 1, the next requirement of page reference is 6. But no frames are available; one loaded page should be replaced as per LRU policy. 

Now, if you see the lastly used page references 3, 8, 2, 3, 9, 1. 

So, as per LRU policy, we replace the page which is not recently used rather we can say which is not nearest to 6. 

Here 8 is not recently used i.e. 8 is not nearest to 6compare to other page references 2, 3, 9, 1. 

Note:  We are not considering the last page reference 3 because page 3 is already appearing before 2. 

So, we replace page reference 8 by page reference 6.

Step 3: After loaded page reference 6, the next requirement of page reference is 3, but not considered because already in the frame i.e. no page fault.

Next requirement of page reference is 8, new page. But all frames are full, so we have replaced one page from the frame.

Now, again we will apply the LRU solution to replace a page from the frame. Consider those lastly used pages 3, 8, 2, 3, 9, 1, 6, 3, and pages are in the frame right now are 3, 6, 2, 9, 1. 

3, 8, 2, 3, 9, 1, 6, 3, 8  - now, page 2 is not recently used or 2 is not nearest to a new page 8 compare to other page references 3, 6, 9, and 1. 

So, we replace page reference 2 by new page reference 8.

Step 4: After insert page reference 8 into the frame, the next requirement of page reference is 9, not considered because already in the frame, so, no page fault.

Next request for page reference is 3 which also present in the frame, so, no page fault.

Next request for page reference is 6 which also present in the frame, so, no page fault.

Next requirement of page reference is 2, new page. But all frames are full, so we have replaced one page from the frame.

Now, again we will apply LRU to replace the existing page. Consider those lastly used pages 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6 and pages are in the frame right now are 3, 6, 8, 9, 1. 

3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2 - now, page1 is not recently used or page 1 is not nearest to a new page 2 compare to other page references 3, 6, 8, and 1. 

So, we replace page reference 1 by new page reference 2.

Step 5: After insert page reference 2 into the frame, the next requirement of page reference is 1 again, which is not in frame i.e. new page requirement. But all frames are full, so we have replaced one page from the frame.

Now, again we will apply LRU to replace the existing page. Consider those lastly used pages 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, and pages are in the frame right now are 3, 6, 8, 9, 2. 

3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2,  1 - now, page 8 is not recently used or page 8 is not nearest to a new page 1 compare to other page references 3, 6, 9, and 2. 

So, we replace page reference 8 by new page reference 1.

Now, after insert page reference 1 into the frame, one page reference requirement is pending which is page reference 3 but which is already loaded in the frame. So, no page fault and no replacement requirement are required.

Page references: 3,  8,  2, 3,  9,  1,  6,  3, 8,  9,  3, 6,  2,  1,  3

So, the number of page faults = 9.

And page fault rate = number of page faults / number page references

So, page fault rate = 9 / 15 = 0.6

Shortcut method:

But in examination it is not possible to solve it by this elaborative way we can do it by a single frame like below:

Page references: 3,  8, 2,  3,  9, 1,  6,  3, 8,  9,  3, 6,  2,  1,  3

The above process is a shortcut and the easiest process to calculate page faults.

So, the number of page faults = 9.