Page replacement algorithms help an operating system decide which memory page to remove when physical memory is full. This cheat sheet covers the rules, strengths, and weaknesses of common algorithms such as FIFO, LRU, Optimal, and Clock. Students need this reference to trace page requests correctly, count page faults, and compare algorithm performance in operating systems problems.
The core idea is that each page reference is either a hit or a fault. If the page is not already in a frame, the algorithm chooses a victim page to replace. FIFO removes the oldest loaded page, LRU removes the least recently used page, Optimal removes the page used farthest in the future, and Clock uses reference bits to approximate LRU efficiently.
Key Facts
- A page hit occurs when the requested page is already in a frame, so no replacement is needed.
- A page fault occurs when the requested page is not in memory, so the operating system must load it into a frame.
- FIFO replacement removes the page that has been in memory the longest, using the rule victim = earliest loaded page.
- LRU replacement removes the page that has not been used for the longest time, using the rule victim = least recently referenced page.
- Optimal replacement removes the page whose next use is farthest in the future, using the rule victim = latest next reference or never used again.
- Clock replacement scans frames in a circle and replaces the first page with reference bit 0, while pages with reference bit 1 are changed to 0 and skipped.
- The page fault rate is page fault rate = number of page faults / total page references.
- More frames usually reduce page faults, but FIFO can show Belady's anomaly, where adding frames causes more faults.
Vocabulary
- Page
- A fixed-size block of virtual memory that can be loaded into physical memory.
- Frame
- A fixed-size block of physical memory that can hold one page.
- Page Fault
- An event that occurs when a program requests a page that is not currently in a frame.
- Page Hit
- An event that occurs when a requested page is already loaded in physical memory.
- Victim Page
- The page selected for removal when a new page must be loaded into a full set of frames.
- Reference String
- The ordered list of page numbers requested by a program during execution.
Common Mistakes to Avoid
- Counting the first load of a page as a hit is wrong because a page not already in a frame causes a page fault.
- Replacing a page when an empty frame exists is wrong because replacement happens only after all frames are full.
- Using FIFO order for LRU is wrong because FIFO tracks load time, while LRU tracks most recent use time.
- Choosing the page used soonest in Optimal is wrong because Optimal replaces the page whose next use is farthest away or never occurs again.
- Forgetting to update the reference bit in Clock is wrong because the algorithm depends on setting referenced pages to 1 and clearing skipped pages to 0.
Practice Questions
- 1 Using FIFO with 3 frames, trace the reference string 1, 2, 3, 4, 1, 2, 5 and find the number of page faults.
- 2 Using LRU with 3 frames, trace the reference string 7, 0, 1, 2, 0, 3, 0, 4 and find the number of page faults.
- 3 For the reference string 1, 2, 3, 2, 4, 1, 5 with 3 frames, which page would Optimal replace when page 4 is requested?
- 4 Explain why Optimal page replacement is useful for comparison but cannot usually be implemented perfectly in a real operating system.