GATE CS Mastery
Cheat sheets

GATE CS 2022 · Operating Systems

Question 64

NAT2 marksNo negative markingEasy (estimate)

Question

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,17, 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_________.

Official answer and solution
Official answer
0.6
From
Official GATE 2022 answer key

Solution

Trace the LRU page replacement algorithm step by step with 4 page frames.

Reference string of length 15: 7,2,7,3,2,5,3,4,6,7,7,1,5,6,17, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1 with 4 initially empty frames.

Step-by-step trace (frames ordered from LRU to MRU):

  1. Access 7: Page fault (1). Frames: [7]
  2. Access 2: Page fault (2). Frames: [7, 2]
  3. Access 7: Hit. Frames: [2, 7]
  4. Access 3: Page fault (3). Frames: [2, 7, 3]
  5. Access 2: Hit. Frames: [7, 3, 2]
  6. Access 5: Page fault (4). Frames: [7, 3, 2, 5] (Frames now full)
  7. Access 3: Hit. Frames: [7, 2, 5, 3]
  8. Access 4: Page fault (5). LRU page 7 evicted. Frames: [2, 5, 3, 4]
  9. Access 6: Page fault (6). LRU page 2 evicted. Frames: [5, 3, 4, 6]
  10. Access 7: Page fault (7). LRU page 5 evicted. Frames: [3, 4, 6, 7]
  11. Access 7: Hit. Frames: [3, 4, 6, 7]
  12. Access 1: Page fault (8). LRU page 3 evicted. Frames: [4, 6, 7, 1]
  13. Access 5: Page fault (9). LRU page 4 evicted. Frames: [6, 7, 1, 5]
  14. Access 6: Hit. Frames: [7, 1, 5, 6]
  15. Access 1: Hit. Frames: [7, 5, 6, 1]

Total page faults = 9.
Total memory accesses = 15.

Page fault rate=915=0.6\text{Page fault rate} = \frac{9}{15} = 0.6
Final answer

0.6

Common trap

Not moving a accessed page to the most recently used (MRU) position on a hit.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2022 Computer Science and Information Technology (CS)
Question
64 of 65
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.