LRU page replacement links with all pages the time of that page’s last use. At the point when a page must be replaced with LRU page replacement picks the page that has not been utilized for the longest time frame. We can think about this technique as the optimal page-replacement algorithm glancing in reverse in time, as opposed to advance.
LRU page replacement algorithms
The consequences of applying LRU page replacement to our example reference string is shown in Figure 1. The LRU page replacement algorithm produces 12 (twelve) faults. Notice that the first five faults are the equivalent to those for optimal page replacement. At the point when the reference to page 4 happens, be that as it may, LRU page replacement sees that, of the 3 (three) frames in memory, page 2 was utilized as least recently. Thus, the LRU page replacement algorithm replaces page 2, not realizing that page 2 is going to be utilized. At the point when it at that point faults for page 2, the LRU page replacement algorithm replaces page 3, since it is presently the least as of late utilized of the three pages in memory. Regardless of these issues, LRU page replacement with twelve faults is obviously surprise to FIFO page replacement with fifteen.
Also check: Memory Fragmentation in Operating System
Calculation of Page Hit ratio:
Total number of reference strings = 20
Total number of page misses or page faults = 12
∵We know that;
Total number of page hits = Total number of reference strings – Total number of page misses or page faults
∴ Total number of page hits (from figure 1) = 20 – 12 = 8
Thus, Page Hit ratio = Total no. of page hits/Total no. of references = 8/20 = 0.4 = 40%
Policies of LRU page replacement:
The policy of LRU page replacement is frequently utilized as a page-replacement algorithm and is viewed as acceptable. The serious issues are the way to execute LRU page replacement. An LRU page-replacement algorithm may need considerable hardware help. The issue is to decide a request for the frames characterized frames when of last use. Two implementations are possible:
- Counters: In the least difficult case, we partner with each page-table passage a period-of-utilization field and add to the CPU a logical clock or counter. The clock is increased for each memory reference. At whatever point a reference to a page is made, the contents of the clock register are replicated to the period-of-utilization field in the page-table entry for that page. Along these lines, we generally have the “time” of the last reference to each page. We replace the page with the littlest time worth. This plan requires an inquiry of the page table to discover the LRU page and a write to memory (to the period-of-utilization field in the page table) for each memory get to. The times should likewise be kept up when page tables are changed (because of CPU scheduling). The overflow of the clock must through of.
- Stack: Another way to deal with actualizing LRU page replacement is to keep a stack of page numbers. At whatever point a page is referenced, it is expelled from the stack and put on the top. Along with these lines, the most as of late utilized page is consistently at the top of the stack and the least as of late utilized page is consistently at the bottom. Since entries must be removed from the middle of the stack, it is ideal to execute this methodology by utilizing a doubly linked list with a head pointer and a tail pointer. Evacuating a page and putting it on the top of the stack at that point requires evolving six-pointers under the least favorable conditions. Each update is somewhat more costly, yet there is no quest for a replacement; the tail pointer focuses to the base of the stack, which is the LRU page. This methodology is especially suitable for software, programming or microcode usage of LRU replacement.
Like optimal replacement, LRU replacement doesn’t suffer from Belady’s anomaly. Both belong to a class of page-replacement algorithms, called stack algorithms that can never exhibit Belady’s anomaly. A stack algorithm is an algorithm for which it tends to be indicated that the set of pages in memory for ‘n‘ frames is constantly a subset of the set of pages that would be in memory with (n + 1) frames. For LRU replacement algorithm, the set of pages in memory would be the n most recently referenced pages. On the off chance that the number of frames is expanded, these ‘n’ pages will at present be the most as of late referenced thus will at present be in memory.
Also check: Demand Paging in Operating System
Advantages of LRU Page Replacement Algorithm:
- It is amenable to full statistical examination.
- This algorithm is very efficient.
- It never suffers from Belady’s anomaly.
Disadvantages of LRU Page Replacement Algorithm:
- Its execution is bit complicated.
- Its execution may need substantial hardware assistance.