• After discussing Optimal algorithm for the page replacement policy, now its time to move on the next page replacement algorithm which is “LRU Algorithm”.
  • LRU stands for Least Recently Used Algorithm and it is the variation of optimal page replacement algorithm.
  • The FIFO page replacement algorithm uses arrival time for page replacement decision while optimal algorithm uses a time when a page is to be used that means future reference.
  • In least recently used algorithm when a page fault generates, we choose the page that was used very less in the past. In other words, optimal algorithm checks forward reference while LRU checks backward reference in the page reference string.
  • The page table entry records the time when the page was last referenced and it is modified every time when the page is referenced. It is basically works on the assumption that if a page is not used frequently in the past then chances are there that it might not be required in the future also.
  • Let’s see this algorithm at work.
Example:

Consider the same page reference string and find out total number of page faults using least recently used algorithm. Assume total number of free frames are 3.

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

  • Initially all three frames are free so the first three page references for pages 7, 0 and 1 will result in page fault so first, second and third free frames will be allocated to page 7, 0, and page 1 respectively. At this point all the three frames are occupied and we have no more free frames available.

Least Recently Used Algorithm

  • Reference for page 2 will generate page fault as page 2 is not available in the memory and since we don’t have any free frame available, swapping is required according to least recently used algorithm by finding the page that has used least in the recent past.
  • To look back in the past we have to check in the backward direction of in the page reference string starting from the current page reference i.e. page 2. We can figure out that page 1 and page 0 is recently used  so page 7 will be selected as it is the least recently used page. Page 7 will be replaced by page 2.
  • Reference for the page 0 will generate no page fault as it is already available in the memory. Then after reference for page 3 will result in the page fault and by looking in the backward direction, we found the page  as least recently used and replaced with page 3.
  • Similarly all the reference will be checked against the available pages in the memory and in the page reference string to find out least recently used page. You can see complete calculation in the above figure.
  • The LRU is quite good compare to FIFO but the major problem is how to implement LRU algorithm. The problem is to determine an order for the frames defined by the time of last use. It can be implemented by two ways.

Counters:

  • In this case, we add extra time field in the page table that will record time of the page access. It will modify the timer each time when a page is referenced.

Stack:

  • Another possible way to implement LRU is the stack. Whenever a page is referenced it is removed from the stack and put on the top. So the stack will always have most recently used page at the top and the least recently used (LRU) page at the bottom of the stack.