Page Replacement Algorithms
Optimal Replacement (OPT)
When a page fault requires a new page and memory is full, a replacement algorithm selects a resident page to replace. Its goal is to reduce page transfers by removing pages not needed again or not needed soon.
OPT replaces the page whose next use is farthest in the future. This is an idealized policy: an OS cannot know exactly when each page will be used again. It serves as a reference for evaluating other algorithms.
| Time | Access | Frame 0 | Frame 1 | Frame 2 | Frame 3 | Fault |
|---|---|---|---|---|---|---|
| 0 | - | a | b | c | d | - |
| 1 | c | a | b | c | d | No |
| 2 | a | a | b | c | d | No |
| 3 | d | a | b | c | d | No |
| 4 | b | a | b | c | d | No |
| 5 | e | a | b | c | e | Yes |
| 6 | b | a | b | c | e | No |
| 7 | a | a | b | c | e | No |
| 8 | b | a | b | c | e | No |
| 9 | c | a | b | c | e | No |
| 10 | d | d | b | c | e | Yes |
OPT: look ahead
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
OPT: trace a new reference string
Frames 0–3 contain 2, 4, 6, 8. Initial loading and last-use order is oldest to newest from left to right. Do not count preloading faults. OPT ties choose the lowest frame index.
6 → 2 → 8 → 4 → 9 → 2 → 7 → 4 → 6 → 9 → 8 → 2
- Apply OPT; write the four frame contents after every access and label hit/fault.
- At each fault compare the next-use position of every resident page.
- Calculate faults, hits and page-fault rate.
| # | Page | Frames 0–3 | Hit / fault | Victim / order |
|---|---|---|---|---|
| 1 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 2 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 3 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 4 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 5 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
| 6 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 7 | 7 | ___ | ___ | ___ | ___ | ___ | ___ |
| 8 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 9 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 10 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
| 11 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 12 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
FIFO
FIFO replaces the page that has resided in memory longest. It keeps a queue, removes the head on a fault, and adds the new page at the tail. It is simple but may perform poorly by removing frequently accessed pages.
| Time | Access | Frame 0 | Frame 1 | Frame 2 | Frame 3 | Fault |
|---|---|---|---|---|---|---|
| 0 | - | a | b | c | d | - |
| 1 | c | a | b | c | d | No |
| 2 | a | a | b | c | d | No |
| 3 | d | a | b | c | d | No |
| 4 | b | a | b | c | d | No |
| 5 | e | e | b | c | d | Yes |
| 6 | b | e | b | c | d | No |
| 7 | a | e | a | c | d | Yes |
| 8 | b | e | a | b | d | Yes |
| 9 | c | e | a | b | c | Yes |
| 10 | d | d | a | b | c | Yes |
FIFO: follow arrival order
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
FIFO: trace a new reference string
Frames 0–3 contain 2, 4, 6, 8. Initial loading and last-use order is oldest to newest from left to right. Do not count preloading faults. OPT ties choose the lowest frame index.
6 → 2 → 8 → 4 → 9 → 2 → 7 → 4 → 6 → 9 → 8 → 2
- Apply FIFO; write the four frame contents after every access and label hit/fault.
- Maintain the arrival queue and mark the page removed from its head.
- Calculate faults, hits and page-fault rate.
| # | Page | Frames 0–3 | Hit / fault | Victim / order |
|---|---|---|---|---|
| 1 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 2 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 3 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 4 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 5 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
| 6 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 7 | 7 | ___ | ___ | ___ | ___ | ___ | ___ |
| 8 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 9 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 10 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
| 11 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 12 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
Least Recently Used (LRU)
LRU approximates optimal replacement by using the past to predict the future. Locality suggests that recently frequent pages may remain frequent, while pages unused for a long time may remain unused. It therefore replaces the page that has gone longest without a reference.
LRU records the last access of each resident page and chooses the one used least recently. It can match the optimal result on some sequences, but maintaining exact access order has substantial overhead.
| Time | Access | Frame 0 | Frame 1 | Frame 2 | Frame 3 | Fault |
|---|---|---|---|---|---|---|
| 0 | - | a | b | c | d | - |
| 1 | c | a | b | c | d | No |
| 2 | a | a | b | c | d | No |
| 3 | d | a | b | c | d | No |
| 4 | b | a | b | c | d | No |
| 5 | e | a | b | e | d | Yes |
| 6 | b | a | b | e | d | No |
| 7 | a | a | b | e | d | No |
| 8 | b | a | b | e | d | No |
| 9 | c | a | b | e | c | Yes |
| 10 | d | a | b | d | c | Yes |
LRU: follow recent use
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
LRU: trace a new reference string
Frames 0–3 contain 2, 4, 6, 8. Initial loading and last-use order is oldest to newest from left to right. Do not count preloading faults. OPT ties choose the lowest frame index.
6 → 2 → 8 → 4 → 9 → 2 → 7 → 4 → 6 → 9 → 8 → 2
- Apply LRU; write the four frame contents after every access and label hit/fault.
- Maintain least-to-most-recent order, including changes caused by hits.
- Calculate faults, hits and page-fault rate.
| # | Page | Frames 0–3 | Hit / fault | Victim / order |
|---|---|---|---|---|
| 1 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 2 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 3 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 4 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 5 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
| 6 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 7 | 7 | ___ | ___ | ___ | ___ | ___ | ___ |
| 8 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 9 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 10 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
| 11 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 12 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
Clock
Clock approximates LRU and improves on FIFO. It uses an access bit, which can start at zero when a page is loaded and becomes one on access. Pages form a ring, with a hand pointing to the next candidate, not necessarily the globally oldest page.
On a page fault, replace the candidate if its bit is zero. If the bit is one, clear it and advance until a victim is found. The newly accessed page has bit one, and the hand moves to the next frame.
For example, accessing 1, 2, 3, 4 fills four frames.
Then accessing 1, 2, 3, 4, 5 hits for the first four pages. Accessing 5 requires replacement: after clearing all four bits, replace the page 1 at the starting hand position with 5 and advance.
Clock: turn the hand
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Clock: trace a new reference string
Use four initially empty frames. The hand starts at frame 0. Each actual access sets R = 1; a hit leaves the hand unchanged. Count initial loading faults.
2 → 4 → 6 → 8 → 2 → 6 → 9 → 4 → 7 → 2 → 8 → 9
- Apply Clock; write the four frame contents after every access and label hit/fault.
- For every fault, record each scanned frame, bit clearing, victim and final hand. For hits, update only the reference bit.
- Calculate faults, hits and page-fault rate.
| # | Page | Frames 0–3 | Hit / fault | Victim / order |
|---|---|---|---|---|
| 1 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 2 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 3 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 4 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 5 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 6 | 6 | ___ | ___ | ___ | ___ | ___ | ___ |
| 7 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
| 8 | 4 | ___ | ___ | ___ | ___ | ___ | ___ |
| 9 | 7 | ___ | ___ | ___ | ___ | ___ | ___ |
| 10 | 2 | ___ | ___ | ___ | ___ | ___ | ___ |
| 11 | 8 | ___ | ___ | ___ | ___ | ___ | ___ |
| 12 | 9 | ___ | ___ | ___ | ___ | ___ | ___ |
KNOWLEDGE QUIZ