1. In a computer systems that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault (the processor wants to access a page and that page is currently not in the main memory) occurs and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.

2. The need for an efficient page replacement algorithm is mainly because, when the page that was selected for replacement and paged out is referenced again it has to be paged in (read in from disk), and this involves waiting for I/O completion. The lesser the time waiting for page-ins, the better the algorithm.

3. A page replacement policy looks at the limited information about accesses to the pages provided by hardware, and tries to guess which pages should be replaced to minimize the total number of page misses, while balancing this with the costs (primary storage and processor time) of the algorithm itself. Thus the algorithm in itself should not be too complex and should not result in unmanageable overheads and delays when implemented.

4. The Least Recently Used (LRU) page replacement policy replaces the page that has not been used for the longest period of time. It is one of the algorithms that were made to approximate if not better the efficiency of the optimal page replacement algorithm. The optimal algorithm assumes the entire reference string to be present at the time of allocation and replaces the page that will not be used for the longest period of time. LRU page replacement policy is based on the observation that pages that have been heavily used in the last few instructions will probably be heavily used again in the next few. Conversely, pages that have not been used for ages will probably remain unused for a long time.

5. It is rather expensive to implement in practice in many cases and hence alternatives to LRU or even variants to the original LRU are continuously being sought.

6. To fully implement LRU, it is necessary to maintain a linked list of all pages in memory, with the most recently used page at the front and the least recently used page at the rear. The difficulty is that the list must be updated on every memory reference. Finding a page in the list, deleting it, and then moving it to the front is a very time consuming operation, even in hardware (assuming that such hardware could be built) or special hardware resources need to be in place for LRU implementation which again is not satisfactory.

7. One important advantage of the LRU algorithm is that it is amenable to full statistical analysis. It has been proven, for example, that LRU can never result in more than N-times more page faults than Optimal (OPT) algorithm, where N is proportional to the number of pages in the managed pool.

8. On the other hand, LRU's weakness is that its performance tends to degenerate under many quite common reference patterns.

   Consider the following reference string as an example for better understanding of the LRU

algorithm.

The first three rows represent the page frames, the last row represents whether a fault has occurred denoted by ‘F’ or no (denoted by a blank cell)

Consider the example above, first page in the string is 7 since it is not already there it is put in one of the three free page frames and a page fault is recorded. Similarly for 0 and 1 the pages are directly inserted in the empty page frames (shown in columns 2 and 3). Now since all the three frames are full, when page 2 is referenced, the least recently used (in some way the page that was used before the other pages. In other words the page that has been unused for more time is swapped out) page is swapped out which in this case is 7.After this 0 is seen which is already present hence it’s a hit and no pages need to be swapped out. Now when page 3 is referenced, since page 0 was used in the last hit and page 2 was swapped in before that, this makes page 1 the least recently used and it is rightly swapped out and replaced by page 3. Similarly the entire process with all page faults is shown above.

Number of page faults = 12.

Number of page hits= 8.