Skip to content

Latest commit

 

History

History
53 lines (38 loc) · 2.54 KB

README.md

File metadata and controls

53 lines (38 loc) · 2.54 KB
Raw

Program for LRU page-replacement algorithm

solution raw output

In Least Recently Used (LRU) algorithm is a Greedy algorithm where the page to be replaced is least recently used.

Least Recently Used (LRU) page replacement algorithm works on the concept that the pages that are heavily used in previous instructions are likely to be used heavily in next instructions. And the page that are used very less are likely to be used less in future. Whenever a page fault occurs, the page that is least recently used is removed from the memory frames. Page fault occurs when a referenced page in not found in the memory frames.

In simple words, on a page fault, the frame that has been in memory the longest is replaced.

Implementation :

Let capacity be the number of pages that memory can hold. Let set be the current set of pages in memory.

  • Start traversing the pages.

    • If set holds less pages than capacity.
      • Insert page into the set one by one until the size of set reaches capacity or all page requests are processed.
      • Simultaneously maintain the recent occurred index of each page in a map called indexes.
      • Increment page fault
    • Else
      • If current page is present in set, do nothing.
      • Else
        • Find the page in the set that was least recently used. We find it using index array. We basically need to replace the page with minimum index.
        • Replace the found page with current page.
        • Increment page faults.
        • Update index of current page.

  • Return page faults.

LRU is a marking algorithm, so it is -competitive.

Output

output_img

Reference