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.
Understanding Page Replacement Algorithms Reference
Virtual memory works because a program does not need every part of its code and data in physical RAM at one moment. The program sees a large set of numbered pages. RAM holds only a limited number of these pages in page frames.
A page table records the mapping from each virtual page to a frame. It usually includes status information, such as whether the page is present, has been changed, or was recently referenced. When a requested page is absent, the processor traps into the operating system.
The operating system may need to save a changed victim page to storage before bringing in the needed page. This storage access is much slower than RAM access, so faults matter far more than the few instructions used to choose a victim.
Most programs show locality of reference. Temporal locality means a program often uses the same item again soon. A loop counter and a frequently used instruction are examples.
Spatial locality means a program often uses nearby addresses close together. Reading an array from left to right is a common example. Locality explains why keeping recently used pages is often a sensible strategy.
LRU uses this pattern directly, but exact LRU can be costly. The system would need to track the order of every reference or update timestamps very often. Clock avoids much of that work.
Its reference bit gives a page a second chance after recent use. A page can remain in memory even when it was used before another page, so Clock is an approximation rather than an exact record of recency.
When tracing an algorithm on paper, make a clear table before processing the reference string. Include one row for each request and one column for each frame. Add columns for the fault result, arrival order for FIFO, last use for LRU, or reference bits and hand position for Clock.
Start with empty frames. A request placed into an empty frame is a fault, but no victim is chosen yet. For LRU, update the recent-use information on every request, including hits.
For Clock, a hit normally sets the relevant reference bit to one. On a fault, move the clock hand only as the stated rule requires. Small bookkeeping errors often cause an entire trace to become wrong.
Optimal replacement is useful as a benchmark, not as a practical operating system policy. It relies on knowing future requests, which a real system cannot know exactly. In exam traces, inspect the remaining reference string after each fault.
A page that never appears again is the best victim. Otherwise compare the next future use of every page in a frame. FIFO is easy to implement because it only needs loading order, yet it may discard a page that a program is about to reuse.
This is why extra frames do not always improve FIFO. Comparing fault counts requires the same reference string and the same number of starting frames.
The fault rate gives a fair summary, though the pattern of faults can matter too. A burst of faults can make a computer feel slow when opening a program, switching tasks, or working with files larger than available RAM.