Question

Consider a computer system with ten physical page frames. The system is provided with an access sequence (a₁, a₂,…,a₂₀, a₁, a₂,…,a₂₀), where each a_i is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is ______.

Answer 1

Concept:

Last-in-first-out page replacement policy: It replaces the newest page that arrives at last in the main memory.

Optimal Page replacement policy: It replaces the page whose next use will occur farthest in the future.

Explanation:

Access sequence is (a₁, a₂,…,a₂₀, a₁, a₂,…,a₂₀)

a₁ to a₁₀ will result in page faults. Total 10 page faults in this.

Then a₁₁ comes, it replaces a₁₀, a₁₂ replaces a₁₁, a₁₃ replaces a₁₂ and so on,….10 page faults from a₁₁ to a₂₀.

Now when a₁ to a₉ occurs again, it will result in 0 page fault because these are already present in the page frame. Again a₁₀ will replace a₂₀, a₁₁ replaces a₁₀ and so on. So, in this way total 11 page faults from a₁₀ to a₂₀­.

Total page faults = 10 + 10 + 11 = 31

Using optimal page replacement:

a₁ to a₁₀ will result in page faults. Total 10 page faults in this.

Then a₁₁ will replace a₁₀ because from a₁ to a₁₀, a₁₀ will be used later, a₁₂ replaces a₁₁ and so on. 10 page faults from a₁₁ to a₂₀.

Again a₁ to a₉, 0 page faults. a₁₀ will replace a₁, a₁₀ to a₁₉ will have 10 page faults.

Total page faults in this = 10 + 10 + 10 = 30

So, difference in number of page faults = 31 – 30 = 1