Consider a demand paging system with four page frames (initially empty) and…
2022
Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string
7, 2,7,3, 2,5,3, 4,6,7,7,1,5,6,1
the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is_________.
Attempted by 77 students.
Show answer & explanation
Correct answer: 0.6
Key idea: simulate the reference string using LRU with four frames and count misses.
Access 1: 7 — page fault; frames: [7]
Access 2: 2 — page fault; frames: [7, 2]
Access 3: 7 — hit; frames: [7, 2]
Access 4: 3 — page fault; frames: [7, 2, 3]
Access 5: 2 — hit; frames: [7, 2, 3]
Access 6: 5 — page fault; frames: [7, 2, 3, 5]
Access 7: 3 — hit; frames: [7, 2, 3, 5]
Access 8: 4 — page fault; evict least recently used (7); frames: [4, 2, 3, 5]
Access 9: 6 — page fault; evict LRU (2); frames: [4, 6, 3, 5]
Access 10: 7 — page fault; evict LRU (5); frames: [4, 6, 3, 7]
Access 11: 7 — hit; frames: [4, 6, 3, 7]
Access 12: 1 — page fault; evict LRU (3); frames: [4, 6, 1, 7]
Access 13: 5 — page fault; evict LRU (4); frames: [5, 6, 1, 7]
Access 14: 6 — hit; frames: [5, 6, 1, 7]
Access 15: 1 — hit; frames: [5, 6, 1, 7]
Counting page faults: there are 9 page faults out of 15 accesses. Page fault rate = 9/15 = 0.6 (rounded to one decimal place: 0.6).
A video solution is available for this question — log in and enroll to watch it.