L-5.25: Least Recently Used Page Replacement Algorithm | Operating System

Understanding LRU Page Replacement Algorithm

Introduction to LRU

• The Least Recently Used (LRU) algorithm replaces the page that has not been used for the longest time. It focuses on historical usage patterns to determine which page to evict.

Initial Page Requests

• Initially, all frames are empty. When page number 7 is requested, it results in a page fault as it is loaded into memory.

• The next request for page number 0 also results in a page fault since it is not present and must be fetched from the hard disk.

Handling Subsequent Requests

• Page number 1 is requested next, leading to another page fault as it too is absent and needs to be loaded.

• Following this, when page number 2 is requested, it also causes a page fault due to its absence in memory.

Page Hits and Faults

• When checking for page number 0 again, it is found present in memory; this counts as a "page hit."

• Upon requesting page number 3, it's determined that this page isn't present either, resulting in another fault.

Applying LRU Logic

• To accommodate the new request for page number 3, LRU checks which of the currently loaded pages was least recently used among them.

• The analysis reveals that among pages 3, 7, 0, and 1—page number 7 was used first; thus it will be replaced by page number 3.

Continuing with New Requests

• After replacing page number 7 with 3 successfully (a new fault), checking for page number 0 shows it's still present (another hit).

• Next comes request for page number 4. Since it's absent from memory, we need to identify which of the current pages should be replaced based on their last usage.

Final Replacements and Hits

• Among pages currently held (2,1,0,3), it's determined that page number 1 was least recently used; hence it gets replaced by new incoming request for page number 4 (this counts as a fault).

Understanding Page Replacement: LRU Algorithm

Introduction to Page Hits and Faults

• The discussion begins with checking the presence of page number 0, which is confirmed as a hit. This indicates that the page is already in memory.

• When checking for page number 1, it is found absent, leading to a need to check past pages (4, 3, 0) to determine which one was used first for replacement.

• A page fault occurs when replacing page number 4 with 1 since it was not present in memory.

Continuing with Page Checks

• The process continues by checking for other pages like numbers 2 and 0, both of which are hits as they are already present in memory.

• Upon checking for page number 7, it is absent again prompting a review of past pages (1, 2, 0, and 3) to find the least recently used one.

Replacement Strategy

• The algorithm identifies that among the past pages checked (1 came first), thus replacing page number 3 with page number 7 results in another page fault.

• After further checks confirm that pages like numbers 0 and 1 are hits again; this demonstrates how frequently accessed pages remain in memory.

Summary of Page Faults and Hits

• A total count reveals eight page faults throughout the process while there were twelve hits recorded. This highlights the efficiency of the LRU strategy.

Performance Comparison: LRU vs FIFO

• While LRU shows fewer overall faults compared to FIFO algorithms, its performance can be slower due to its reliance on searching through past usage history.