A process has been allocated 3 page frames. Assume that none of the pages of…

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 If optimal page replacement policy is used, how many page faults occur for the above reference string?

  1. A.

    7

  2. B.

    8

  3. C.

    9

  4. D.

    10

Attempted by 147 students.

Show answer & explanation

Correct answer: A

Use the optimal (Belady) page replacement policy with 3 frames. Reference string: 1, 2, 1, 3, 7, 4, 5, 6, 3, 1

  1. Reference 1 — page fault. Frames: [1] (faults = 1)

  2. Reference 2 — page fault. Frames: [1, 2] (faults = 2)

  3. Reference 1 — hit. Frames: [1, 2] (faults = 2)

  4. Reference 3 — page fault. Frames: [1, 2, 3] (faults = 3)

  5. Reference 7 — page fault. Evict page 2 (it is not used again). Frames: [1, 3, 7] (faults = 4)

  6. Reference 4 — page fault. Evict page 7 (it is not used again). Frames: [1, 3, 4] (faults = 5)

  7. Reference 5 — page fault. Evict page 4 (it is not used again). Frames: [1, 3, 5] (faults = 6)

  8. Reference 6 — page fault. Evict page 5 (it is not used again). Frames: [1, 3, 6] (faults = 7)

  9. Reference 3 — hit. Frames: [1, 3, 6] (faults = 7)

  10. Reference 1 — hit. Frames: [1, 3, 6] (faults = 7)

Total page faults: 7

Reason: At each page fault the optimal policy evicts the page whose next use is farthest in the future (or not used again). Following that rule for the given sequence and three frames yields 7 faults.

Explore the full course: Gate Guidance By Sanchit Sir