Subject : Computer Organization & Architecture

Topic : Module 5

Difficulty : Hard

LRU Page Replacement Policy

• LRU stands for Least Recently Used page replacement strategy.
• This algorithm works on the principle of “Last in First out“.
• It replaces the newest page that arrived at last in the main memory.
• It replaces the page that has not been referred by the CPU for the longest time.
• It is implemented by keeping track of all the pages in a stack.
• This strategy helps OS to find page usage over a short period of time.
• This policy should be implemented by associating a counter with an even page.
• Page, which has not been used for the longest time in the main memory, is the one that will be selected for replacement.
• Easy to implement, keep a list, replace pages by looking back into time.

Example:

String = 1, 3, 2, 4, 2, 1, 5, 1, 3, 2, 6, 7, 5, 4, 3, 2, 4, 2, 3, 1, 4

Frame Size = 3

Page Fault = 16