FIFO vs LRU vs Optimal Page Replacement: 6 Solved Problems

FIFO vs LRU page replacement differs in the victim rule: FIFO evicts the page loaded earliest, while LRU evicts the page unused for the longest time. A hit updates LRU's recency but does not change FIFO's arrival order. Optimal evicts the page whose next use is farthest in the future and is a benchmark, not a general online OS policy.

A page fault happens when the page you need is not in any memory frame. To count faults, walk through the reference string one page at a time and decide, only when memory is full, which page to throw out. FIFO throws out the oldest page, LRU the page unused for longest, and Optimal the page whose next use is farthest away.

Page replacement decision

Requested page in memory?

Yes: hit

No: fault

Free frame? Load it

Full: choose a victim

Concept map. Follow the stated algorithm and assumptions in the worked examples below.

This worksheet has six original solved problems with full frame tables, plus three self-tests with answers. For process basics first, read OS Part 1: process states and context switching. For scheduling numericals, see CPU scheduling worked examples. These are general BTech CSE practice questions, not an official university paper or a prediction.

1. Terms and the method

• Reference string: the order in which a program asks for pages.
• Frame: one slot of physical memory that can hold one page.
• Page fault: the requested page is not in a frame, so it must be loaded. The first loads into empty frames also count as faults.
• Hit ratio = hits / total references. Fault ratio = faults / total references.

1. Write the string and the number of frames.
2. For each page: if it is in a frame, mark a hit. Otherwise mark a fault.
3. On a fault with a free frame, just load it. On a fault with all frames full, apply the policy to pick a victim.
4. Count the faults. Check that hits + faults = length of the string.

Tie-break rule used here: in Optimal, if two pages are never used again, remove the one that was loaded earlier. Say your tie-break in the exam.

FIFO removes the oldest arrival, and hits do not change its order. LRU removes the least recently used page, and each hit moves that page to the most-recent end. The FIFO and LRU tables show an ordered resident list: Rank 1 is the next victim, and the last occupied rank is the newest arrival or most recent use. A page can move between rank rows without being evicted. Only the Optimal tables use fixed frame positions F1, F2 and so on.

Pocket reference: which clock chooses the victim?

Policy	Victim rule	Hit changes order?	More frames can hurt?
FIFO	Earliest current arrival	No	Yes
LRU	Oldest last use	Yes	No
Optimal	Farthest next use	No queue update	No

See why FIFO and LRU diverge

3 frames, request 1,2,3:
FIFO oldest -> newest: [1,2,3]
LRU least -> most used: [1,2,3]

Hit on 1:
FIFO order unchanged: [1,2,3]
LRU refreshes 1:      [2,3,1]

Fault on 4:
FIFO evicts 1:        [2,3,4]
LRU evicts 2:         [3,1,4]

These are order diagrams, not physical frame movements. Both policies have one hit on 1, but the hit changes only LRU's next victim.

2. Six solved problems

Problem 1: FIFO, LRU and Optimal on one string

Reference string: 5, 0, 1, 3, 0, 4, 0, 2, 3, 0, 3, 2, 1, 2, 0, with 3 frames, starting empty. Count the faults for each policy.

FIFO

Ref	5	0	1	3	0	4	0	2	3	0	3	2	1	2	0
Rank 1	5	5	5	0	0	1	3	4	0	0	0	0	2	2	3
Rank 2	-	0	0	1	1	3	4	0	2	2	2	2	3	3	1
Rank 3	-	-	1	3	3	4	0	2	3	3	3	3	1	1	0
Fault?	F	F	F	F	hit	F	F	F	F	hit	hit	hit	F	hit	F

FIFO ignores hits. At the hit on page 0 (5th reference) nothing moves. Page 5 leaves first because it arrived first. FIFO faults: 10.

LRU

Ref	5	0	1	3	0	4	0	2	3	0	3	2	1	2	0
Rank 1	5	5	5	0	1	3	3	4	0	2	2	0	3	3	1
Rank 2	-	0	0	1	3	0	4	0	2	3	0	3	2	1	2
Rank 3	-	-	1	3	0	4	0	2	3	0	3	2	1	2	0
Fault?	F	F	F	F	hit	F	hit	F	F	hit	hit	hit	F	hit	F

LRU refreshes a page on every hit. After the early hits on 0, page 0 survives longer than under FIFO. LRU faults: 9.

Optimal

Ref	5	0	1	3	0	4	0	2	3	0	3	2	1	2	0
F1	5	5	5	3	3	3	3	3	3	3	3	3	1	1	1
F2	-	0	0	0	0	0	0	0	0	0	0	0	0	0	0
F3	-	-	1	1	1	4	4	2	2	2	2	2	2	2	2
Fault?	F	F	F	F	hit	F	hit	F	hit	hit	hit	hit	F	hit	hit

At the first replacement (page 3 arrives), pages 5, 0, 1 are in memory. Page 5 is never used again, so it goes first. Optimal looks ahead, so it is a yardstick, not something an OS can run. Optimal faults: 7.

Answer: FIFO 10, LRU 9, Optimal 7 faults out of 15 references. Optimal is never worse than the others.

Problem 2: Four frames, and a tie between FIFO and LRU

String: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2, 4 frames. Find the faults for all three policies.

FIFO: 6 faults

Ref	2	3	2	1	5	2	4	5	3	2	5	2
Rank 1	2	2	2	2	2	2	3	3	3	1	1	1
Rank 2	-	3	3	3	3	3	1	1	1	5	5	5
Rank 3	-	-	-	1	1	1	5	5	5	4	4	4
Rank 4	-	-	-	-	5	5	4	4	4	2	2	2
Fault?	F	F	hit	F	F	hit	F	hit	hit	F	hit	hit

LRU: 6 faults

Ref	2	3	2	1	5	2	4	5	3	2	5	2
Rank 1	2	2	3	3	3	3	1	1	2	4	4	4
Rank 2	-	3	2	2	2	1	5	2	4	5	3	3
Rank 3	-	-	-	1	1	5	2	4	5	3	2	5
Rank 4	-	-	-	-	5	2	4	5	3	2	5	2
Fault?	F	F	hit	F	F	hit	F	hit	F	hit	hit	hit

Optimal: 5 faults

Ref	2	3	2	1	5	2	4	5	3	2	5	2
F1	2	2	2	2	2	2	2	2	2	2	2	2
F2	-	3	3	3	3	3	3	3	3	3	3	3
F3	-	-	-	1	1	1	4	4	4	4	4	4
F4	-	-	-	-	5	5	5	5	5	5	5	5
Fault?	F	F	hit	F	F	hit	F	hit	hit	hit	hit	hit

Answer: FIFO 6, LRU 6, Optimal 5. FIFO and LRU tie on the count here, but they do not choose the same victims at every step. Compare the two tables to see where they differ. Optimal saves one fault by looking ahead.

Problem 3: Bélády's anomaly with FIFO

String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Find FIFO faults with 3 frames and with 4 frames.

FIFO, 3 frames: 9 faults

Ref	1	2	3	4	1	2	5	1	2	3	4	5
Rank 1	1	1	1	2	3	4	1	1	1	2	5	5
Rank 2	-	2	2	3	4	1	2	2	2	5	3	3
Rank 3	-	-	3	4	1	2	5	5	5	3	4	4
Fault?	F	F	F	F	F	F	F	hit	hit	F	F	hit

FIFO, 4 frames: 10 faults

Ref	1	2	3	4	1	2	5	1	2	3	4	5
Rank 1	1	1	1	1	1	1	2	3	4	5	1	2
Rank 2	-	2	2	2	2	2	3	4	5	1	2	3
Rank 3	-	-	3	3	3	3	4	5	1	2	3	4
Rank 4	-	-	-	4	4	4	5	1	2	3	4	5
Fault?	F	F	F	F	hit	hit	F	F	F	F	F	F

Answer: 9 faults with 3 frames, 10 faults with 4 frames. More memory gave more faults. This is Bélády's anomaly. With 4 frames, FIFO throws out pages 1 and 2 just before they are needed again.

Problem 4: Does LRU show the same anomaly?

Use the same string as Problem 3 and count LRU faults for 3 and 4 frames.

LRU, 3 frames: 10 faults

Ref	1	2	3	4	1	2	5	1	2	3	4	5
Rank 1	1	1	1	2	3	4	1	2	5	1	2	3
Rank 2	-	2	2	3	4	1	2	5	1	2	3	4
Rank 3	-	-	3	4	1	2	5	1	2	3	4	5
Fault?	F	F	F	F	F	F	F	hit	hit	F	F	F

LRU, 4 frames: 8 faults

Ref	1	2	3	4	1	2	5	1	2	3	4	5
Rank 1	1	1	1	1	2	3	4	4	4	5	1	2
Rank 2	-	2	2	2	3	4	1	2	5	1	2	3
Rank 3	-	-	3	3	4	1	2	5	1	2	3	4
Rank 4	-	-	-	4	1	2	5	1	2	3	4	5
Fault?	F	F	F	F	hit	hit	F	hit	hit	F	F	F

Answer: LRU gives 10 faults with 3 frames and 8 with 4. Faults went down. LRU is a stack algorithm: the pages held with n frames are always a subset of the pages held with n+1 frames, so it cannot show Bélády's anomaly. Optimal has the same property. FIFO does not.

Problem 5: Hit ratio and fault ratio

For Problem 1 under LRU, find the hit ratio and fault ratio.

LRU had 9 faults in 15 references, so hits = 15 - 9 = 6.

Answer: hit ratio = 6/15 = 40.0%. Fault ratio = 9/15 = 60.0%. Check: they add to 100%.

Problem 6: Effective access time with page faults

Memory access takes 200 ns. A page fault takes 8 ms to service. The page fault rate is p = 1 in 1000. (a) Find the effective access time (EAT). (b) What fault rate keeps the slowdown below 10%?

EAT = (1 - p) x memory time + p x fault time

(a) Convert 8 ms to 8,000,000 ns. EAT = 0.999 x 200 + 0.001 x 8,000,000 = 199.8 + 8,000 = 8,199.8 ns, about 8.2 microseconds. That is about 41 times slower than 200 ns.

(b) A 10% slowdown means EAT below 220 ns. So 200 + p x (8,000,000 - 200) < 220, so p < 20 / 7,999,800, which is about 2.5 x 10^-6.

Answer: (a) about 8,199.8 ns. (b) p must be below about 2.5 x 10^-6, roughly one fault per 400,000 accesses. Even a tiny fault rate dominates, because a disk access is thousands of times slower than memory.

3. Common mistakes

• Not counting the first loads into empty frames as faults. They are faults.
• Updating FIFO order on a hit. FIFO order depends only on arrival time.
• Forgetting to refresh LRU order on a hit.
• In Optimal, looking backwards instead of forwards.
• Concluding that more frames always means fewer faults. That is true for LRU and Optimal, not for FIFO.
• Mixing units in the EAT formula. Convert ms to ns first.

4. Self-tests

Test A. String 4, 7, 6, 1, 7, 6, 1, 2, 7, 2, 3 frames. Find FIFO, LRU and Optimal faults.

Test B. String 1, 3, 5, 1, 2, 3, 4, 1, 5, 2, 3, 1, 3 frames. Find FIFO, LRU and Optimal faults. Which is surprising?

Test C. Memory access is 100 ns, fault service is 5 ms and p = 0.0002. Find the EAT.

Answers. A: FIFO 6, LRU 6, Optimal 5. B: FIFO 10, LRU 11, Optimal 7. LRU is worse than FIFO here. LRU is good on average for programs with locality, but it can lose on a particular string. C: EAT = 0.9998 x 100 + 0.0002 x 5,000,000 = 99.98 + 1,000 = 1,099.98 ns.

Continue from theory to a C program

Read FIFO, LRU and Optimal in the complete Operating Systems notes for the theory, then run the FIFO and LRU C programs in the Operating Systems lab file. Compare each program's frames with the solved tables above before trying a new reference string.

5. Where to practise next

Open the Exam Numericals Hub for more solved worksheets. Try your own reference string, solve it on paper, then check it with a small program.

Run the policy and EAT checks

This standalone Python 3 checker runs every reference string. FIFO and LRU keep resident pages in victim-first order; Optimal uses fixed positions and the stated tie-break. The simple lists favor readability over speed. The service time in this EAT model is the complete time for a faulting access.

def simulate(refs, capacity, policy):
    resident = []
    loaded = {}
    trace = []
    faults = 0
    for i, page in enumerate(refs):
        miss = page not in resident
        if miss:
            faults += 1
            if len(resident) < capacity:
                resident.append(page)
            elif policy in ("FIFO", "LRU"):
                resident.pop(0)
                resident.append(page)
            else:
                future = refs[i + 1:]
                def priority(p):
                    next_use = future.index(p) if p in future else float("inf")
                    return (next_use, -loaded[p])
                victim = max(resident, key=priority)
                resident[resident.index(victim)] = page
            loaded[page] = i
        elif policy == "LRU":
            resident.remove(page)
            resident.append(page)
        trace.append((resident.copy(), miss))
    return faults, trace

strings = [
    ("problem 1", [5,0,1,3,0,4,0,2,3,0,3,2,1,2,0], 3),
    ("problem 2", [2,3,2,1,5,2,4,5,3,2,5,2], 4),
    ("anomaly 3 frames", [1,2,3,4,1,2,5,1,2,3,4,5], 3),
    ("anomaly 4 frames", [1,2,3,4,1,2,5,1,2,3,4,5], 4),
    ("test A", [4,7,6,1,7,6,1,2,7,2], 3),
    ("test B", [1,3,5,1,2,3,4,1,5,2,3,1], 3),
]
for name, refs, frames in strings:
    counts = [simulate(refs, frames, p)[0] for p in ("FIFO", "LRU", "OPT")]
    assert counts[2] <= min(counts[:2])
    print(name + ": FIFO/LRU/OPT = " + "/".join(map(str, counts)))
print("problem 5: hits = 6/15 = 40%; faults = 9/15 = 60%")
print(f"problem 6: EAT = {(1-0.001)*200+0.001*8000000:.2f} ns")
print(f"problem 6: p < {20/(8000000-200):.9g}")
print(f"test C: EAT = {(1-0.0002)*100+0.0002*5000000:.2f} ns")

Executed output:

problem 1: FIFO/LRU/OPT = 10/9/7
problem 2: FIFO/LRU/OPT = 6/6/5
anomaly 3 frames: FIFO/LRU/OPT = 9/10/7
anomaly 4 frames: FIFO/LRU/OPT = 10/8/6
test A: FIFO/LRU/OPT = 6/6/5
test B: FIFO/LRU/OPT = 10/11/7
problem 5: hits = 6/15 = 40%; faults = 9/15 = 60%
problem 6: EAT = 8199.80 ns
problem 6: p < 2.5000625e-06
test C: EAT = 1099.98 ns

Exam and interview quick answers

1. Does a hit count as a fault? No. The requested page is already resident.
2. Do empty-frame loads count as faults? Yes. No eviction is needed, but the page is still missing.
3. Why does a hit not refresh FIFO? FIFO remembers arrival order, not last-use order.
4. Can LRU lose to FIFO on one string? Yes. Test B gives 11 LRU faults versus 10 FIFO faults.
5. Why is Optimal mainly a benchmark? It requires exact future references, which a general online OS does not know.
6. What if two Optimal pages are never used again? Either is an optimal victim. This worksheet breaks the tie by earlier load time.
7. Is a page fault always a disk read? No. Real faults can include zero-fill or other handling. The EAT questions use the stated fixed service-time model.
8. Does the EAT fault time include the restarted access? Here it is the total time of a faulting access, as assumed by the displayed formula. If a problem gives service overhead only, add the normal restarted access explicitly.

Sources checked

The policy definitions, stack property and EAT model were checked against University of Illinois Chicago: Virtual Memory. All ten original trace tables and every fault count were recomputed with the executable simulation below.

More practice on the memory side: cache memory numericals, and a deadlock worksheet in Banker's algorithm problems.

OS and memory exam study route

• Cache Memory Numericals: 6 Solved Problems on Address Bits, Hit Ratio and AMAT
• Banker's Algorithm and Deadlock: 6 Solved Problems with Safe Sequences
• Exam Numericals Hub