Your phone's home screen has room for only a few apps in the dock. When you want a new one there, one of the existing apps has to go. If you remove the app you use every hour, you will soon have to put it back, wasting time. If you remove an app you have not opened in months, you will probably never miss it.
An operating system faces this exact choice many times a second. In Virtual Memory & Demand Paging we saw that when a page fault happens and no frame is free, the OS must evict some page to make room. The rule it uses to pick that page is called a page-replacement algorithm.
A page-replacement algorithm decides which page in memory (the victim) to remove when a new page must be loaded and no free frame is available. Its goal is to minimise the number of page faults.
In this chapter we will trace FIFO, Optimal and LRU on the same example, see Belady's anomaly, learn how real systems approximate LRU with reference bits and the clock algorithm, and compare everything in one table. Every trace and count in this chapter was checked with a small simulator; the FIFO / OPT / LRU part of it is included at the end so you can check your own answers.
Page Replacement in the Page-Fault Path
When a page fault finds no free frame, the OS does this:
Run the replacement algorithm to choose a victim frame.
If the victim page is dirty (modified since it was loaded), write it to disk. If it is clean, skip the write: the disk already has an identical copy.
Mark the victim's page-table entry invalid and remove it from the TLB.
Read the new page into the frame, update its page-table entry, and restart the faulting instruction.
A clean victim costs one disk transfer; a dirty one costs two. That is why the dirty (modify) bit from Page Tables & TLB matters, and why some algorithms prefer clean victims.
A bad choice is expensive: if we evict a page that is needed again soon, we immediately take another fault to bring it back. A good algorithm evicts pages that will not be needed for a long time.
Reference Strings
To compare algorithms we do not need full addresses, only the sequence of page numbers a process touches. This sequence is the reference string.
Two simplifications are made:
Replace each address by its page number (address ÷ page size).
Drop immediate repeats: if page p was just referenced, referencing it again right away can never cause a fault.
Example. Page size = 256 bytes. The process touches addresses:
Addresses : 300 310 1030 520 530 1100 300 2050 2060 540
Page no. : 1 1 4 2 2 4 1 8 8 2 (address div 256)
Reference string (repeats removed): 1, 4, 2, 4, 1, 8, 2The number of page faults depends on two things: the reference string and the number of frames the process has. More frames usually (but, as we will see, not always) means fewer faults.
For the main traces we will use this reference string with 3 frames, all initially empty:
5, 4, 3, 1, 4, 6, 4, 3, 6, 2, 6, 4, 5, 6, 2 (15 references, 6 distinct pages)Since the frames start empty, the first reference to each distinct page is always a fault (a compulsory or cold-start fault). With 6 distinct pages, no algorithm can do better than 6 faults on this string.
FIFO (First-In, First-Out)
Rule: evict the page that has been in memory the longest, i.e. the one that was loaded first. A hit does not change the order: FIFO only cares about when a page arrived, not when it was last used.
It is implemented with a simple queue: new pages join the tail, the victim is taken from the head. Equivalently, a pointer moves round the frames in a circle, which is what the table below shows.
Step | Ref | Frame 1 | Frame 2 | Frame 3 | Result | Evicted |
|---|---|---|---|---|---|---|
1 | 5 | 5 | - | - | Fault | - |
2 | 4 | 5 | 4 | - | Fault | - |
3 | 3 | 5 | 4 | 3 | Fault | - |
4 | 1 | 1 | 4 | 3 | Fault | 5 |
5 | 4 | 1 | 4 | 3 | Hit | - |
6 | 6 | 1 | 6 | 3 | Fault | 4 |
7 | 4 | 1 | 6 | 4 | Fault | 3 |
8 | 3 | 3 | 6 | 4 | Fault | 1 |
9 | 6 | 3 | 6 | 4 | Hit | - |
10 | 2 | 3 | 2 | 4 | Fault | 6 |
11 | 6 | 3 | 2 | 6 | Fault | 4 |
12 | 4 | 4 | 2 | 6 | Fault | 3 |
13 | 5 | 4 | 5 | 6 | Fault | 2 |
14 | 6 | 4 | 5 | 6 | Hit | - |
15 | 2 | 4 | 5 | 2 | Fault | 6 |
FIFO: 12 page faults, 3 hits. Fault rate = 12/15 = 80%.
Look at steps 6 and 7. At step 6, page 6 arrives and FIFO evicts 4, because 4 arrived before 3 and 1. But 4 was used just one step earlier (step 5) and is needed again immediately at step 7, which costs another fault. FIFO threw out a busy page only because it was old. This is FIFO's weakness: age is not the same as usefulness. A page loaded early may be one that is used all the time (like a loop's code page).
FIFO pros | FIFO cons |
|---|---|
Very simple, O(1) per fault with a queue | Ignores how often or how recently a page is used |
No work at all on a hit | Often a high fault rate |
Easy to explain and analyse | Suffers from Belady's anomaly |
Belady's Anomaly
Common sense says: give a process more frames and it will have fewer (or at least not more) page faults. For FIFO, common sense is wrong. Take the reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5FIFO with 3 frames:
Step | Ref | Frame 1 | Frame 2 | Frame 3 | Result | Evicted |
|---|---|---|---|---|---|---|
1 | 1 | 1 | - | - | Fault | - |
2 | 2 | 1 | 2 | - | Fault | - |
3 | 3 | 1 | 2 | 3 | Fault | - |
4 | 4 | 4 | 2 | 3 | Fault | 1 |
5 | 1 | 4 | 1 | 3 | Fault | 2 |
6 | 2 | 4 | 1 | 2 | Fault | 3 |
7 | 5 | 5 | 1 | 2 | Fault | 4 |
8 | 1 | 5 | 1 | 2 | Hit | - |
9 | 2 | 5 | 1 | 2 | Hit | - |
10 | 3 | 5 | 3 | 2 | Fault | 1 |
11 | 4 | 5 | 3 | 4 | Fault | 2 |
12 | 5 | 5 | 3 | 4 | Hit | - |
That is 9 faults.
FIFO with 4 frames:
Step | Ref | Frame 1 | Frame 2 | Frame 3 | Frame 4 | Result | Evicted |
|---|---|---|---|---|---|---|---|
1 | 1 | 1 | - | - | - | Fault | - |
2 | 2 | 1 | 2 | - | - | Fault | - |
3 | 3 | 1 | 2 | 3 | - | Fault | - |
4 | 4 | 1 | 2 | 3 | 4 | Fault | - |
5 | 1 | 1 | 2 | 3 | 4 | Hit | - |
6 | 2 | 1 | 2 | 3 | 4 | Hit | - |
7 | 5 | 5 | 2 | 3 | 4 | Fault | 1 |
8 | 1 | 5 | 1 | 3 | 4 | Fault | 2 |
9 | 2 | 5 | 1 | 2 | 4 | Fault | 3 |
10 | 3 | 5 | 1 | 2 | 3 | Fault | 4 |
11 | 4 | 4 | 1 | 2 | 3 | Fault | 5 |
12 | 5 | 4 | 5 | 2 | 3 | Fault | 1 |
That is 10 faults, one more than with 3 frames!
Belady's anomaly: for some algorithms (FIFO is the classic example), increasing the number of frames can increase the number of page faults for some reference strings.
Why does it happen? With 3 frames, the fault on 5 at step 7 evicts 4, and the recently reloaded pages 1 and 2 survive, so steps 8 and 9 are hits. With 4 frames, FIFO keeps 1 and 2 until exactly the wrong moment: at step 7 it evicts 1 (the oldest), then needs 1, evicts 2, needs 2, and so on. The order in which pages leave depends on arrival times, which shift when the frame count changes, so the set of pages held with 4 frames is not always a superset of the set held with 3.
Stack algorithms never show this anomaly. An algorithm is a stack algorithm if, at every point in time, the set of pages in memory with n frames is always a subset of the set with n + 1 frames. Then adding a frame can only turn faults into hits, never the reverse. Optimal and LRU are stack algorithms; FIFO is not.
Optimal (OPT / MIN)
Rule: evict the page that will not be used for the longest time in the future. If a page will never be used again, it is the perfect victim.
This algorithm, described by László Belady in 1966 (hence the names OPT, MIN or Belady's algorithm), gives the lowest possible number of page faults for any reference string and frame count.
Step | Ref | Frame 1 | Frame 2 | Frame 3 | Result | Evicted |
|---|---|---|---|---|---|---|
1 | 5 | 5 | - | - | Fault | - |
2 | 4 | 5 | 4 | - | Fault | - |
3 | 3 | 5 | 4 | 3 | Fault | - |
4 | 1 | 1 | 4 | 3 | Fault | 5 |
5 | 4 | 1 | 4 | 3 | Hit | - |
6 | 6 | 6 | 4 | 3 | Fault | 1 |
7 | 4 | 6 | 4 | 3 | Hit | - |
8 | 3 | 6 | 4 | 3 | Hit | - |
9 | 6 | 6 | 4 | 3 | Hit | - |
10 | 2 | 6 | 4 | 2 | Fault | 3 |
11 | 6 | 6 | 4 | 2 | Hit | - |
12 | 4 | 6 | 4 | 2 | Hit | - |
13 | 5 | 6 | 5 | 2 | Fault | 4 |
14 | 6 | 6 | 5 | 2 | Hit | - |
15 | 2 | 6 | 5 | 2 | Hit | - |
OPT: 7 page faults, 8 hits. Only one fault above the minimum of 6 compulsory faults.
How each victim was chosen (look ahead from the current step):
Step 4 (page 1 arrives, memory = 5, 4, 3): next uses are 5 at step 13, 4 at step 5, 3 at step 8. Page 5 is needed farthest in the future, so evict 5.
Step 6 (page 6, memory = 1, 4, 3): 1 is never used again. Evict 1.
Step 10 (page 2, memory = 6, 4, 3): 3 is never used again. Evict 3.
Step 13 (page 5, memory = 6, 4, 2): 4 is never used again (6 is used at step 14, 2 at step 15). Evict 4.
If two or more pages are never used again, any of them can be evicted; the fault count is the same.
The Catch
OPT needs to know the future reference string, which a real OS does not know when a fault happens. So OPT cannot be implemented in a real system. It is still very useful:
As a benchmark: if an algorithm is within a few percent of OPT, it is excellent.
In exam questions, where the whole string is given.
LRU (Least Recently Used)
We cannot see the future, but we can see the past. Because of locality, the recent past is a good predictor of the near future: a page used a moment ago will probably be used again soon, and a page untouched for a long time probably will not.
Rule: evict the page that has not been used for the longest time. LRU is "OPT looking backwards".
Step | Ref | Frame 1 | Frame 2 | Frame 3 | Result | Evicted |
|---|---|---|---|---|---|---|
1 | 5 | 5 | - | - | Fault | - |
2 | 4 | 5 | 4 | - | Fault | - |
3 | 3 | 5 | 4 | 3 | Fault | - |
4 | 1 | 1 | 4 | 3 | Fault | 5 |
5 | 4 | 1 | 4 | 3 | Hit | - |
6 | 6 | 1 | 4 | 6 | Fault | 3 |
7 | 4 | 1 | 4 | 6 | Hit | - |
8 | 3 | 3 | 4 | 6 | Fault | 1 |
9 | 6 | 3 | 4 | 6 | Hit | - |
10 | 2 | 3 | 2 | 6 | Fault | 4 |
11 | 6 | 3 | 2 | 6 | Hit | - |
12 | 4 | 4 | 2 | 6 | Fault | 3 |
13 | 5 | 4 | 5 | 6 | Fault | 2 |
14 | 6 | 4 | 5 | 6 | Hit | - |
15 | 2 | 2 | 5 | 6 | Fault | 4 |
LRU: 10 page faults, 5 hits. Fault rate = 10/15 ≈ 67%, between FIFO (12) and OPT (7).
Compare step 6 with FIFO. When 6 arrives, memory is 1, 4, 3. Their last uses were: 3 at step 3, 1 at step 4, 4 at step 5 (a hit). LRU evicts 3, the least recently used, and keeps 4, which is used again at step 7. FIFO evicted 4 here and paid for it.
How Can LRU Be Implemented?
LRU needs to know the order of last use, updated on every memory reference, not just on faults. That is the hard part. Two exact methods:
Method | On every reference | On a fault | Problem |
|---|---|---|---|
Counters / timestamps | CPU copies a logical clock into the page's table entry | Search all pages for the smallest timestamp | Extra memory write per access; O(n) search |
Stack (doubly linked list) | Move the referenced page to the top of the stack | Victim is at the bottom: O(1) | Several pointer updates per access |
Both need work on every single memory access, which happens billions of times a second. Doing this in software would make every access many times slower, and doing it in hardware is too costly. So real operating systems do not implement exact LRU for page replacement. They use cheap approximations based on the hardware reference bit.
(In software caches, such as a web cache or an "LRU cache" interview problem, exact LRU is common: a hash map plus a doubly linked list gives O(1) for both get and put, because those caches are accessed far less often than RAM.)
FIFO Is Not Always Worse
LRU is usually better than FIFO, but not always. On the short string from earlier, 1, 4, 2, 4, 1, 8, 2 with 3 frames, FIFO takes 4 faults while LRU takes 5. When 8 arrives, LRU evicts 2 (least recently used), which is needed next; FIFO evicts 1 (oldest), which is never needed again. No practical algorithm wins on every string; only OPT does.
LRU Approximation Algorithms
Most CPUs provide a reference bit (also called accessed bit) in each page-table entry. The hardware sets it to 1 whenever the page is read or written. The OS can read it and clear it to 0. One bit cannot give the exact order of use, but it tells the OS "was this page used since I last cleared the bit?", which is enough for good approximations.
Additional-Reference-Bits Algorithm
Keep an 8-bit history byte for each page. At regular intervals (for example every 100 ms, on a timer interrupt), the OS shifts each page's history one bit to the right and copies the page's reference bit into the leftmost (most significant) bit, then clears the reference bit.
The byte then records whether the page was used in each of the last 8 intervals, newest on the left. Treating the bytes as unsigned numbers, the page with the smallest value is the least recently used, and is the victim.
Example. Three pages, four intervals (reference bit at the end of each interval, oldest first):
Page | Interval 1 | Interval 2 | Interval 3 | Interval 4 (latest) | History byte | Value |
|---|---|---|---|---|---|---|
A | 1 | 0 | 0 | 1 | 10010000 | 144 |
B | 1 | 1 | 1 | 0 | 01110000 | 112 |
C | 0 | 0 | 1 | 1 | 11000000 | 192 |
Page B has the smallest value (112), so B is evicted. B was used in three intervals, more than A, but not in the most recent one; the leftmost bit outweighs all the bits to its right, which is exactly the "recency first" rule of LRU.
Second-Chance (Clock) Algorithm
This is FIFO plus one reference bit, and it is the basis of most real implementations.
Arrange the frames in a circle with a pointer, the clock hand, pointing at the next candidate. On a fault:
Look at the page under the hand.
If its reference bit is 0: this is the victim. Replace it, set the new page's bit to 1, advance the hand. Done.
If its reference bit is 1: give it a second chance. Clear the bit to 0, advance the hand, and repeat from step 1.
On a hit, the hardware just sets the page's reference bit to 1; nothing else moves.
hand
|
v
frame 1: page 3 R=1 -> clear R to 0, move on (second chance)
frame 2: page 7 R=0 -> victim: replace page 7
frame 3: page 2 R=1 (not examined this time)
(after frame 3 the hand wraps back to frame 1)If every page has R = 1, the hand goes all the way round clearing bits and comes back to where it started, which now has R = 0. In that case clock behaves exactly like FIFO.
Here is the clock algorithm on our string with 3 frames. The ref bits and the hand position are shown after each step. A newly loaded page gets R = 1 (it was just referenced), which is the common convention; some textbooks load with R = 0, which can change the trace, so always follow the convention your question states.
Step | Ref | Frame 1 | Frame 2 | Frame 3 | Ref bits | Hand → frame | Result | Evicted |
|---|---|---|---|---|---|---|---|---|
1 | 5 | 5 | - | - | 1 0 0 | 2 | Fault | - |
2 | 4 | 5 | 4 | - | 1 1 0 | 3 | Fault | - |
3 | 3 | 5 | 4 | 3 | 1 1 1 | 1 | Fault | - |
4 | 1 | 1 | 4 | 3 | 1 0 0 | 2 | Fault | 5 |
5 | 4 | 1 | 4 | 3 | 1 1 0 | 2 | Hit | - |
6 | 6 | 1 | 4 | 6 | 1 0 1 | 1 | Fault | 3 |
7 | 4 | 1 | 4 | 6 | 1 1 1 | 1 | Hit | - |
8 | 3 | 3 | 4 | 6 | 1 0 0 | 2 | Fault | 1 |
9 | 6 | 3 | 4 | 6 | 1 0 1 | 2 | Hit | - |
10 | 2 | 3 | 2 | 6 | 1 1 1 | 3 | Fault | 4 |
11 | 6 | 3 | 2 | 6 | 1 1 1 | 3 | Hit | - |
12 | 4 | 3 | 2 | 4 | 0 0 1 | 1 | Fault | 6 |
13 | 5 | 5 | 2 | 4 | 1 0 1 | 2 | Fault | 3 |
14 | 6 | 5 | 6 | 4 | 1 1 1 | 3 | Fault | 2 |
15 | 2 | 5 | 6 | 2 | 0 0 1 | 1 | Fault | 4 |
Clock: 11 page faults. Better than FIFO (12), not as good as LRU (10) here: an approximation, as expected.
Look at step 12 (page 4 arrives). Memory is 3, 2, 6 with all bits 1, and the hand at frame 3. The hand clears 6's bit, then 3's, then 2's, comes back to frame 3 where 6 now has bit 0, and evicts 6. With every bit set, it degenerated into FIFO for this fault.
Enhanced Second-Chance (NRU)
Use both the reference bit R and the dirty (modify) bit M. Every page falls into one of four classes:
Class | (R, M) | Meaning | Replacement preference |
|---|---|---|---|
0 | (0, 0) | Not recently used, clean | Best victim |
1 | (0, 1) | Not recently used, dirty | Needs a write-back first |
2 | (1, 0) | Recently used, clean | Probably needed again soon |
3 | (1, 1) | Recently used, dirty | Worst victim |
The algorithm scans the clock for a page in the lowest non-empty class. It prefers not used recently over everything else, and among those it prefers clean pages because they can be dropped without a disk write. Class 1 can exist even though the page was modified, because the OS clears R periodically but M stays set until the page is written back.
Counting-Based Algorithms
Keep a counter of how many times each page has been referenced:
LFU (Least Frequently Used): evict the page with the smallest count. Idea: busy pages are important. Problem: a page used heavily long ago (say during start-up) keeps a high count and stays forever. Counts are often aged by shifting them right periodically.
MFU (Most Frequently Used): evict the page with the largest count. Idea: a page with a small count was probably just brought in and has not been used yet.
Neither approximates OPT well in general, and both are expensive to implement, so they are rarely used for page replacement. They appear in exams and in application caches.
Page Buffering
Real systems add tricks around the algorithm itself:
Keep a pool of free frames. On a fault, the new page is read into a free frame immediately, without waiting for a victim to be written out. The victim is written later and its frame joins the pool.
Write dirty pages in the background when the disk is idle, so that more victims are clean when they are needed.
Remember which page was in each free frame. If the evicted page is referenced again before its frame is reused, it can be taken back from the pool with no disk I/O (a minor fault).
Linux does all three: the kernel thread kswapd reclaims pages in the background to keep a reserve of free memory, and evicted file pages that are still in memory can be reclaimed cheaply.
What Real Operating Systems Use
Linux approximates LRU with two lists (kept per NUMA node and per memory cgroup), active and inactive, filled using the accessed bits. Pages are evicted from the tail of the inactive list, and a page that is referenced again while inactive is promoted back to the active list, which is a second-chance idea. Linux 6.1 added an optional multi-generational LRU (MGLRU) that sorts pages into several age generations for better decisions under memory pressure.
Windows gives each process a working set and trims pages from it using an aging scheme based on accessed bits; trimmed pages go to standby lists from which they can be recovered without disk I/O.
Databases such as MySQL's InnoDB manage their own buffer pool with an LRU variant (split into "young" and "old" sublists) so that one big table scan does not flush out all the frequently used pages.
The common pattern: clock-like approximations of LRU, plus a free-page reserve.
Comparison of Algorithms
Page faults for our reference string 5, 4, 3, 1, 4, 6, 4, 3, 6, 2, 6, 4, 5, 6, 2 as the number of frames changes:
Frames | FIFO | OPT | LRU | Clock |
|---|---|---|---|---|
1 | 15 | 15 | 15 | 15 |
2 | 13 | 10 | 13 | 13 |
3 | 12 | 7 | 10 | 11 |
4 | 8 | 6 | 7 | 7 |
5 | 7 | 6 | 7 | 7 |
6 | 6 | 6 | 6 | 6 |
With 6 frames every distinct page fits, so every algorithm has only the 6 compulsory faults. With very few frames every algorithm suffers. The differences show up in between, which is where real systems operate.
Algorithm | Victim | Implementable? | Belady's anomaly? | Cost |
|---|---|---|---|---|
FIFO | Oldest arrival | Yes | Yes | Very low |
OPT | Used farthest in future | No (needs future) | No | Benchmark only |
LRU | Used farthest in past | Exact LRU too costly for RAM | No | High (work on every access) |
Second chance / Clock | First page with R = 0 under the hand | Yes, widely used | Possible (degrades to FIFO) | Low |
Enhanced clock (NRU) | Lowest (R, M) class | Yes | Possible | Low, fewer write-backs |
LFU / MFU | Smallest / largest count | Yes, but costly | Possible | Medium to high |
Check Your Answers with a Simulator
This short Python program counts page faults for FIFO, LRU and OPT. Use it to check homework and exam practice:
def simulate(refs, frames, policy):
memory = [] # pages currently in frames
last_used = {} # page -> time of last use (for LRU)
faults = 0
for t, page in enumerate(refs):
if page in memory: # hit
last_used[page] = t
continue
faults += 1 # page fault
if len(memory) == frames: # memory full: choose a victim
if policy == "FIFO":
victim = memory[0] # oldest arrival
elif policy == "LRU":
victim = min(memory, key=lambda p: last_used[p])
else: # OPT
future = refs[t + 1:]
victim = max(memory, key=lambda p: future.index(p)
if p in future else len(future))
memory.remove(victim)
memory.append(page)
last_used[page] = t
return faults
refs = [5, 4, 3, 1, 4, 6, 4, 3, 6, 2, 6, 4, 5, 6, 2]
for policy in ("FIFO", "OPT", "LRU"):
print(policy, [simulate(refs, n, policy) for n in range(1, 7)])
belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
print("FIFO, 3 frames:", simulate(belady, 3, "FIFO"))
print("FIFO, 4 frames:", simulate(belady, 4, "FIFO"))Output:
FIFO [15, 13, 12, 8, 7, 6]
OPT [15, 10, 7, 6, 6, 6]
LRU [15, 13, 10, 7, 7, 6]
FIFO, 3 frames: 9
FIFO, 4 frames: 10The first three lines are the FIFO, OPT and LRU rows of the comparison table (1 to 6 frames). The last two lines reproduce Belady's anomaly. Notice that the OPT and LRU lists never go up as frames increase, while FIFO's can on other strings.
Common Mistakes
Updating FIFO order on a hit. FIFO only cares about arrival time. A hit does not move the page to the back of the queue (that would be LRU).
Forgetting compulsory faults. With empty frames, the first reference to every page is a fault, whatever the algorithm.
Looking backwards in OPT or forwards in LRU. OPT looks at the future; LRU looks at the past.
Thinking Belady's anomaly applies to LRU or OPT. It cannot happen in stack algorithms. It applies to FIFO (and FIFO-like algorithms such as clock in some cases).
Assuming more frames always means fewer faults. True for stack algorithms, not for FIFO.
Saying the OS implements exact LRU. Real kernels approximate it with reference bits; exact LRU for RAM needs work on every memory access.
Mixing clock conventions. Whether a newly loaded page starts with R = 1 or R = 0, and where the hand moves after a replacement, changes the trace. State your convention.
Interview Questions
Why do we need page replacement?
With demand paging, memory fills up. When a page fault occurs and there is no free frame, some resident page must be evicted to make room for the needed page.
What is Belady's anomaly?
The situation where giving a process more frames increases its page faults. It happens with FIFO, e.g. the string 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 faults with 3 frames but 10 with 4.
Which algorithms are free from Belady's anomaly and why?
Stack algorithms such as OPT and LRU. For them, the set of pages in memory with n frames is always a subset of the set with n + 1 frames, so an extra frame can only turn faults into hits.
Why can't the optimal algorithm be implemented?
It needs to know which page will be used farthest in the future, and the OS does not know the future reference string. OPT is used as a benchmark.
Why is exact LRU not used for page replacement in real OSes?
It requires updating a timestamp or a list on every memory access, which is far too expensive in software and costly in hardware. Systems approximate it with reference bits (clock, aging, active/inactive lists).
Explain the second-chance (clock) algorithm.
Frames form a circle with a hand. On a fault, if the page under the hand has R = 1, clear it and move on (second chance); the first page with R = 0 is the victim. If all bits are 1, it behaves like FIFO.
Why does the dirty bit matter in page replacement?
A clean victim can be discarded because disk already has a copy; a dirty victim must be written back first, doubling the I/O. Enhanced second chance prefers clean, not-recently-used pages.
How would you implement an LRU cache in O(1)?
Use a hash map from key to a node in a doubly linked list ordered by recency. On access, move the node to the front; on insert when full, remove the node at the tail and delete its key from the map.
What does Linux use for page replacement?
An LRU approximation with active and inactive lists driven by accessed bits, background reclaim by kswapd, and optionally the multi-generational LRU (MGLRU) added in Linux 6.1.
Summary
A page-replacement algorithm picks a victim page when a page fault needs a frame and none is free. Dirty victims must be written back first.
Algorithms are compared on a reference string with a fixed number of frames. On our 15-reference string with 3 frames: FIFO 12, Clock 11, LRU 10, OPT 7 faults.
FIFO evicts the oldest page; simple but can evict busy pages and suffers from Belady's anomaly (9 faults with 3 frames, 10 with 4 on 1,2,3,4,1,2,5,1,2,3,4,5).
OPT evicts the page used farthest in the future: lowest possible faults, but not implementable; used as a benchmark.
LRU evicts the page unused for the longest time; a stack algorithm with no anomaly, but too expensive to run exactly.
Real systems use reference-bit approximations: additional-reference-bits (aging), second chance / clock, and enhanced clock using (R, M) classes, plus page buffering.
Even the best algorithm cannot help if a process simply has too few frames for the pages it is actively using. That situation, and how the OS detects it, is the subject of the next chapter, Thrashing.