LRU removes the least recently used page, but missing a recency update on a hit changes later victims. Attempt each question on paper before reading its explanation, then use the trace to find the step where your frame table drifted. The twelve are all previous-year papers: GATE 2007 and GATE IT 2008, five UGC NET sets, and one each from ISRO, KVS, DSSSB, TPSC and Coal India. More than 30 questions on this topic sit inside CS Fundamentals for Exams and Placements.
1. LRU page replacement: use one trace rule for every question
On a hit, keep the frames and make that page newest. On a fault, use an empty frame or evict the oldest last access. Hits can change the next victim without changing the frame set.
For 7, 0, 1, 2, 0, 3 with three empty frames:
7:F [7]; 0:F [7,0]; 1:F [7,0,1]; 2:F, evict 7 -> [2,0,1]; 0:H -> [2,0,1], with 0 newest; 3:F, evict 1 -> [2,0,3].
Total: 5 faults and 1 hit. Mark H or F, update recency, replace only on a full-frame fault, then count. Compare policies in Page Replacement Algorithms for GATE: FIFO, LRU and Optimal.
2. Questions 1-2: identify the LRU rule and the stack-property result
Question 1. Select the LRU victim
Asked in: TPSC Programmer 2026
In the Least Recently Used (LRU) page replacement algorithm, which page is selected for replacement ?
A.
The page that will not be used for the longest timeB.
The page that has been in memory for the longest timeC.
The page that was least recently accessedD.
The page with the lowest priority
Answer: C. LRU uses the oldest last access. A is Optimal, B is FIFO, and D is unrelated. Solved page.
Question 2. Test Belady's anomaly
Asked in: DSSSB TGT 2024
Which of the following page replacement algorithm(s) does not suffer from Belady's anomaly in Operating System?
I. Least-Recently Used (LRU) page replacement.
II. First-In, First-Out (FIFO) page replacement.
A.
Only IB.
Neither I nor IIC.
Only IID.
Both I and II
Answer: A. Only I. By the stack property, n-frame residents are a subset of n+1-frame residents for the same prefix, so extra frames cannot increase LRU faults. FIFO has no such guarantee. Solved page.
3. Questions 3-5: count LRU faults without losing the recency order
Question 3. Trace four frames
Asked in: Coal India Computer Science 2020
What is number of page faults by least recently used page replacement for a memory with 4 frames for the page reference string 2, 0, 1, 2, 4, 0, 5, 1, 4, 6, 4, 2, 1, 3, 0 ?
A.
7B.
8C.
9D.
10
Answer: D. 10. F,F,F,H,F,H,F,F,H,F,H,F,H,F,F: 10 faults, 5 hits. Loads 5, 1, 6, 2, 3, 0 evict 1, 2, 0, 5, 6, 4. Final set: {0,1,2,3}. Solved page.
Question 4. Separate hits from faults
Asked in: ISRO Computer Science 2014
A computer has 16 pages of virtual address space but the size of main memory is only four frames. Initially the memory is empty. A program references the virtual pages in the order 0, 2, 4, 5, 2, 4, 3, 11, 2, 10. How many page faults occur if LRU page replacement algorithm is used?
A.
3B.
5C.
7D.
8
Answer: C. 7. F,F,F,F,H,H,F,F,H,F. Hits refresh 2 and 4; loads 3, 11, 10 evict 0, 5, 4. Final set: {2,3,10,11}. Solved page.
Question 5. Count a longer trace
Asked in: KVS Computer Science 2018
How many page faults occur in LRU page replacement algorithm for the given reference string, with four page frames?
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1
A.
6B.
8C.
7D.
9
Answer: C. 7. F,F,F,F,H,F,H,F,H,H,H,H,H,F,H,H,H. After four fills, faults on 3, 4, 1 evict 7, 1, 4. Thus 4 + 3 = 7; final set {0,1,2,3}. Solved page.
4. Questions 6-8: short UGC NET traces with different fault patterns
Question 6. Read a compact string
Asked in: UGC NET Computer Science, June 2015
A LRU page replacement is used with 4 page frames and eight pages. How many page faults will occur with the reference string 0172327103 if the four frames are initially empty ?
A.
6B.
7C.
5D.
8
Answer: B. 7. Read 0172327103 as 0,1,7,2,3,2,7,1,0,3: F,F,F,F,F,H,H,H,F,F. Loads 3, 0, 3 evict 0, 3, 2. It is ten references, not one integer. Solved page.
Question 7. Refresh repeated 2s
Asked in: UGC NET Computer Science, July 2018
Consider a virtual page reference string 1, 2, 3, 2, 4, 2, 5, 2, 3, 4. Suppose LRU page replacement algorithm is implemented with 3 page frames in main memory. Then the number of page faults are_________.
A.
5B.
7C.
9D.
10
Answer: B. 7. F,F,F,H,F,H,F,H,F,F. Hits make 2 newest; loads 4, 5, 3, 4 remove 1, 3, 4, 5. Final set: {2,3,4}. Solved page.
Question 8. Find the two hits
Asked in: UGC NET Computer Science, June 2022
For the following page reference string 4,3,2,1,4,3,5,4,3,2,1,5, the number of page faults that occur in Least Recently Used (LRU) page replacement algorithm with frame size 3 is
A.
6B.
8C.
10D.
12
Answer: C. 10. F,F,F,F,F,F,F,H,H,F,F,F. Only the second 4 and 3 hit, so 12 - 2 = 10 faults. Final set: {1,2,5}. Solved page.
5. Questions 9-10: long traces and the initial-fill convention
Question 9. Audit 24 references
Asked in: UGC NET Computer Science, August 2016
Suppose that the virtual Address space has eight pages and physical memory with four page frames. If LRU page replacement algorithm is used, _____ number of page faults occur with the reference string. 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1
A.
13B.
12C.
10D.
9
Answer: A. 13. F F F F F F F H F H H H H F H H F H H H F H F F. There are 13 Fs; final set {1,2,3,4}. Refresh 3 on every hit. Solved page.
Question 10. Exclude compulsory fills
Asked in: UGC NET Computer Science, June 2014
Consider a program that consists of 8 pages (from 0 to 7) and we have 4 page frames in the physical memory for the pages. The page reference string is : 1 2 3 2 5 6 3 4 6 3 7 3 1 5 3 6 3 4 2 4 3 4 5 1 The number of page faults in LRU and optimal page replacement algorithms are respectively (without including initial page faults to fill available page frames with pages) :
A.
9 and 6B.
10 and 7C.
9 and 7D.
10 and 6
Answer: B. 10 and 7. Totals are 14 for LRU and 11 for Optimal, so 14 - 4 = 10 and 11 - 4 = 7. Optimal uses farthest future access; LRU uses oldest past access. Subtract four distinct-page fills because position 4 is a hit. Solved page.
6. Questions 11-12: compare policies and translate addresses into pages
Question 11. Compare LRU with Optimal
Asked in: GATE Computer Science 2007
A process has been allocated 3-page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1 Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?
A.
0B.
1C.
2D.
3
Answer: C. 2. LRU F,F,H,F,F,F,F,F,F,F gives 9; Optimal F,F,H,F,F,F,F,F,H,H gives 7. Thus 9 - 7 = 2. Both may discard 2 at 7; Optimal later preserves 3 and 1. Solved page.
Question 12. Convert addresses first
Asked in: GATE Information Technology 2008
Assume that a main memory with only 4 pages, each of 16 bytes, is initially empty. The CPU generates the following sequence of virtual addresses and uses the Least Recently Used (LRU) page replacement policy. 0, 4, 8, 20, 24, 36, 44, 12, 68, 72, 80, 84, 28, 32, 88, 92 How many page faults does this sequence cause? What are the page numbers of the pages present in the main memory at the end of the sequence?
A.
6 and 1, 2, 3, 4B.
7 and 1, 2, 4, 5C.
8 and 1, 2, 4, 5D.
9 and 1, 2, 3, 5
Answer: B. 7 and 1, 2, 4, 5. floor(address / 16) gives 0,0,0,1,1,2,2,0,4,4,5,5,1,2,5,5. Trace F,H,H,F,H,F,H,H,F,H,F,H,F,F,H,H has 7 faults. Slots [2,5,1,4] mean set {1,2,4,5}. Solved page.
7. LRU MCQ answer key, error repair, and the next step
Answer key: 1-C, 2-A, 3-D, 4-C, 5-C, 6-B, 7-B, 8-C, 9-A, 10-B, 11-C, 12-B.
Use a correction ledger:
Question | First wrong step | Correct recency or conversion |
|---|---|---|
Q7 | Ignored hit on 2 | Every hit on 2 makes it newest |
Q10 | Kept total faults |
|
Q12 | Traced addresses | First convert to |
At 10-12, redo your slowest trace. At 7-9, repeat Section 1, Q3, Q7, and Q12. Below 7, work through Page Replacement Algorithms for GATE: FIFO, LRU and Optimal, then Virtual Memory and Demand Paging MCQs, and retry this set.
For structured Operating Systems study, use CS Fundamentals for Placements by Sanchit Sir. Convert addresses if needed, update recency, mark H or F, then count.
