A system uses 3 page frames for storing process pages in main memory. It uses…

2014

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

Attempted by 70 students.

Show answer & explanation

Correct answer: 6

Answer: 6 page faults.

Key idea: Use the Least Recently Used (LRU) policy: when a new page must be loaded and all frames are full, evict the page that was used least recently.

  1. Reference 4 -> Frames = [4, -, -] -> page fault (1)

  2. Reference 7 -> Frames = [4, 7, -] -> page fault (2)

  3. Reference 6 -> Frames = [4, 7, 6] -> page fault (3)

  4. Reference 1 -> evict least recently used (4) -> Frames = [1, 7, 6] -> page fault (4)

  5. Reference 7 -> already in frames -> hit (no fault)

  6. Reference 6 -> already in frames -> hit (no fault)

  7. Reference 1 -> already in frames -> hit (no fault)

  8. Reference 2 -> not in frames; evict LRU (7) -> Frames = [1, 2, 6] -> page fault (5)

  9. Reference 7 -> not in frames; evict LRU (6) -> Frames = [1, 2, 7] -> page fault (6)

  10. Reference 2 -> already in frames -> hit (no fault)

Total page faults = 6.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir