Least Recently Used (LRU) Page Replacement Algorithm

Introduction

• LRU is a page replacement algorithm used to manage memory.
• It replaces the least recently used pages first when the memory is full.
• Previous algorithm discussed: FIFO (First-In, First-Out).

Key Concepts

• Reference String: Sequence of pages the CPU requests.
• Page Fault: Occurs when the requested page is not found in the main memory (RAM).
• Page Hit: Occurs when the requested page is found in the main memory.

Steps in LRU Algorithm

1. Initialize: Main memory begins with 3 free frames.
2. Process Page Requests:
   • Page 7: Not in RAM → Page fault. Load from disk to RAM.
   • Page 0: Not in RAM → Page fault. Load from disk to RAM.
   • Page 1: Not in RAM → Page fault. Load from disk to RAM.
   • Page 2: Not in RAM, memory full → Replace least recently used page (Page 7) with Page 2 → Page fault.
   • Page 0: Already in RAM → Page hit.
   • Page 3: Not in RAM, memory full → Replace least recently used page (Page 1) with Page 3 → Page fault.
   • Page 0: Already in RAM → Page hit.
   • Page 4: Not in RAM, memory full → Replace least recently used page (Page 2) with Page 4 → Page fault.
   • Page 2: Not in RAM, memory full → Replace least recently used page (Page 3) with Page 2 → Page fault.
   • Page 3: Not in RAM, memory full → Replace least recently used page (Page 0) with Page 3 → Page fault.
   • Page 0: Not in RAM, memory full → Replace least recently used page (Page 4) with Page 0 → Page fault.
   • Page 3: Already in RAM → Page hit.
   • Page 1: Not in RAM, memory full → Replace least recently used page (Page 2) with Page 1 → Page fault.
   • Page 2: Not in RAM, memory full → Replace least recently used page (Page 0) with Page 2 → Page fault.
   • Page 0: Not in RAM, memory full → Replace least recently used page (Page 3) with Page 0 → Page fault.

Summary

• Page Hits: 3 (Pages 0, 0, and 3).
• Page Faults: 12 (Pages 7, 0, 1, 2, 3, 4, 2, 3, 0, 1, 2, 0).
• Observation: The hit ratio and the fault ratio depend on the given reference string.

Conclusion

• The LRU algorithm is a useful method for managing memory but performance can vary significantly based on the reference string used.