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

Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?

Answer: C. 2 — Solution: Simulate both LRU and optimal replacement with 3 page frames for the reference string: 1, 2, 1, 3, 7, 4, 5, 6, 3, 1. LRU simulation (3 frames):…

  1. A.

    0

  2. B.

    1

  3. C.

    2

  4. D.

    3

Attempted by 10 students.

Show answer & explanation

Correct answer: C

Solution: Simulate both LRU and optimal replacement with 3 page frames for the reference string: 1, 2, 1, 3, 7, 4, 5, 6, 3, 1.

LRU simulation (3 frames):

  • Reference 1 → frames = [1, -, -] — page fault (total faults = 1)

  • Reference 2 → frames = [1, 2, -] — page fault (total faults = 2)

  • Reference 1 → frames = [1, 2, -] — hit (total faults = 2)

  • Reference 3 → frames = [1, 2, 3] — page fault (total faults = 3)

  • Reference 7 → replace least recently used (2) → frames = [1, 7, 3] — page fault (total faults = 4)

  • Reference 4 → replace least recently used (1) → frames = [4, 7, 3] — page fault (total faults = 5)

  • Reference 5 → replace least recently used (3) → frames = [4, 7, 5] — page fault (total faults = 6)

  • Reference 6 → replace least recently used (7) → frames = [4, 6, 5] — page fault (total faults = 7)

  • Reference 3 → replace least recently used (4) → frames = [3, 6, 5] — page fault (total faults = 8)

  • Reference 1 → replace least recently used (5) → frames = [3, 6, 1] — page fault (total faults = 9)

Total LRU page faults = 9.

Optimal simulation (3 frames):

  • Reference 1 → frames = [1, -, -] — page fault (total faults = 1)

  • Reference 2 → frames = [1, 2, -] — page fault (total faults = 2)

  • Reference 1 → frames = [1, 2, -] — hit (total faults = 2)

  • Reference 3 → frames = [1, 2, 3] — page fault (total faults = 3)

  • Reference 7 → look ahead: 1 appears later, 2 never appears, 3 appears later → replace 2 → frames = [1, 7, 3] — page fault (total faults = 4)

  • Reference 4 → look ahead: 1 appears later, 7 never appears, 3 appears later → replace 7 → frames = [1, 4, 3] — page fault (total faults = 5)

  • Reference 5 → look ahead: 1 appears later, 4 never appears, 3 appears later → replace 4 → frames = [1, 5, 3] — page fault (total faults = 6)

  • Reference 6 → look ahead: 1 appears later, 5 never appears, 3 appears later → replace 5 → frames = [1, 6, 3] — page fault (total faults = 7)

  • Reference 3 → frames = [1, 6, 3] — hit (total faults = 7)

  • Reference 1 → frames = [1, 6, 3] — hit (total faults = 7)

Total optimal page faults = 7.

Answer: LRU has 9 faults and optimal has 7 faults, so LRU produces 2 more page faults than optimal (9 − 7 = 2).

Explore the full course: Wipro Preparation

Loading lesson…