Question
A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?
4, 7, 6, 1, 7, 6, 1, 2, 7, 2
Official answer and solution
- Official answer
- 6
- From
- Official GATE 2014 answer key
Solution
Simulate the Least Recently Used (LRU) page replacement algorithm step-by-step on 3 initially empty page frames.
We simulate the reference string on 3 frames with LRU replacement:
Reference string: 4, 7, 6, 1, 7, 6, 1, 2, 7, 2
- Ref 4: Miss (Fault 1). Frames:
[4] - Ref 7: Miss (Fault 2). Frames:
[4, 7] - Ref 6: Miss (Fault 3). Frames:
[4, 7, 6] - Ref 1: Miss (Fault 4). Least recently used page among is 4. Replace 4 with 1. Frames:
[1, 7, 6](recency order: 7, 6, 1). - Ref 7: Hit. Frames:
[1, 6, 7](recency order: 6, 1, 7). - Ref 6: Hit. Frames:
[1, 7, 6](recency order: 1, 7, 6). - Ref 1: Hit. Frames:
[7, 6, 1](recency order: 7, 6, 1). - Ref 2: Miss (Fault 5). Least recently used page among is 7. Replace 7 with 2. Frames:
[2, 6, 1](recency order: 6, 1, 2). - Ref 7: Miss (Fault 6). Least recently used page among is 6. Replace 6 with 7. Frames:
[2, 7, 1](recency order: 1, 2, 7). - Ref 2: Hit. Frames:
[1, 7, 2](recency order: 1, 7, 2).
Total page faults = .
6
Failing to update recency order upon page hits, leading to incorrect victim selection.
The answer is the one in the official GATE answer key. The solution is this site's own explanation.
Source
- Paper
- GATE 2014 Computer Science and Information Technology (CS) Session 3
- Question
- 30 of 65, printed as CS Q.20
- Section
- Computer Science and Information Technology
Report an error in this question
GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.