Page Replacement Algorithms

Introduction

• Paging Concept: Processes are divided into pages and placed in main memory frames.
• Virtual Memory: Only a few pages of a process are kept in main memory at a time, enabling more processes to fit in the limited memory.
• Page Replacement: Swapping out old pages to bring in needed ones when memory is full.

Key Points

• CPU & Paging: CPU requests bytes, which are located in pages. Virtual memory manages this through paging.
• Page Fault: Occurs when a page needed by CPU is not in main memory. Involves fetching the page from the hard disk, which is time-consuming.
• Minimizing Page Faults: Crucial for performance as accessing hard disk is slow.

Page Replacement Algorithms

1. First In First Out (FIFO)
   • Oldest page in memory is replaced first.
   • Example: Given page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 1, 2, 0, and 3 frames
   • Steps:
     1. Page 7 -> Page Fault -> Add to Frame 1
     2. Page 0 -> Page Fault -> Add to Frame 2
     3. Page 1 -> Page Fault -> Add to Frame 3
     4. Page 2 -> Page Fault -> Remove 7 (oldest) -> Add 2
     5. Page 0 -> Hit (already in memory)
     6. Page 3 -> Page Fault -> Remove 0 (next oldest) -> Add 3
     7. Page 0 -> Page Fault -> Remove 1 -> Add 0
     8. Page 4 -> Page Fault -> Remove 2 -> Add 4
     9. Page 2 -> Page Fault -> Remove 3 -> Add 2
     10. Page 3 -> Page Fault -> Remove 0 -> Add 3
     11. Page 0 -> Page Fault -> Remove 4 -> Add 0
     12. Page 3 -> Hit
     13. Page 1 -> Page Fault -> Remove 2 -> Add 1
     14. Page 2 -> Page Fault -> Remove 3 -> Add 2
     15. Page 0 -> Hit
   • Hits: 3 times
   • Page Faults: 12 times
   • Hit Ratio: (3 hits / 15 references) * 100 = 20%
   • Miss Ratio: (12 misses / 15 references) * 100 = 80%

Conclusion

• FIFO Method: Use frame-wise replacement in sequence.
• Hit/Miss Calculation: Important for assessing performance.

Thank you for attending the lecture!