Consider the following page reference string : 1, 2, 3, 4, 2, 1, 5, 6, 2, 1,…
2016
Consider the following page reference string :
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Which of the following options, gives the correct number of page faults related to LRU, FIFO, and optimal page replacement algorithms respectively, assuming 05 page frames and all frames are initially empty ?
- A.
10, 14, 8
- B.
8, 10, 7
- C.
7, 10, 8
- D.
7, 10, 7
Attempted by 15 students.
Show answer & explanation
Correct answer: B
Final counts: LRU = 8 page faults, FIFO = 10 page faults, Optimal = 7 page faults.
LRU (Least Recently Used) — 8 page faults.
Reasoning: The first five distinct pages (1, 2, 3, 4, 5) cause five faults to fill the frames. Subsequent accesses cause three additional faults (when page 6 is first loaded, and later when pages 3 and 7 are referenced and not in frames under LRU), giving a total of 8 faults.
FIFO (First-In First-Out) — 10 page faults.
Reasoning: The first five distinct pages again produce five initial faults. After that, FIFO evicts pages in arrival order, causing five more faults during the remainder of the reference string, for a total of 10 faults.
Optimal (Belady's algorithm) — 7 page faults.
Reasoning: After the five initial faults to fill frames, optimal replacement looks ahead and evicts pages that are used farthest in the future (or not used again). Only two additional faults are necessary in the remainder of the sequence, so the total is 7.
Quick verification tip: simulate each policy step-by-step. Count the five initial faults for the distinct pages, then for each subsequent reference determine whether it is a hit or a fault and apply the policy-specific eviction rule to update frames and counts.
A video solution is available for this question — log in and enroll to watch it.