Question-1 Explain LRU (Least Recently Used) Page Replacement Algorithm
LRU (Least Recently Used) Page Replacement Algorithm
- A good approximation to the optimal algorithm is based on the observation that pages that have been heavily used in last few instructions will probably be heavily used again in next few instructions.
- When page fault occurs, throw out the page that has been used for the longest time. This strategy is called LRU (Least Recently Used) paging.
- 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 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 operations.
- There are other ways to implement LRU with special hardware.
- For a machine with n page frames, the LRU hardware can maintain a matrix of n × n bits, initially all zero.
- Whenever page frame k is referenced, the hardware first sets all the bits of row k to 1, and then sets all the bits of column k to 0.
- At any instant, the row whose binary value is lowest is the least recently used; the row whose value is next lowest is next least recently used, and so forth.
- The workings of this algorithm are given in Fig. below for four page frames and page references in the order 0 1 2 3 2 1 0 3 2 3.
- After page 0 is referenced, we have the situation of Fig. below (a).
- After page 1 is reference, we have the situation of Fig. below (b), and so forth.
- As shown in Fig. below (j), if page fault occurs at that moment, the page from the page frame 1 with lowest binary value will be replaced.
Figure – LRU using a matrix when pages are referenced in the order 0, 1, 2, 3, 2, 1, 0, 3, 2, 3.
You may be interested in:
Operating System Short Descriptive Questions and Answers