Question 59

Reference sequence: $S = (a_1, a_2, \dots, a_{20}, a_1, a_2, \dots, a_{20})$ of length 40, with $10$ page frames.
All $a_i$ ($1 \le i \le 20$) are distinct pages.

1. Last-In-First-Out (LIFO) Policy:

• First half ($a_1$ to $a_{20}$):
  • $a_1, \dots, a_{10}$ fill the 10 empty frames $\implies 10$ faults. Frames hold: $\{a_1, a_2, \dots, a_{10}\}$, with $a_{10}$ as the latest loaded page.
  • $a_{11}$ faults, replacing the most recently loaded page $a_{10}$. Frame contents: $\{a_1, \dots, a_9, a_{11}\}$.
  • For each subsequent page $a_{12}, \dots, a_{20}$, each page replaces the single frame slot occupied by the most recently loaded page. Each of $a_{11}, \dots, a_{20}$ causes a fault ($10$ faults).
  • At the end of the first half, frames hold $\{a_1, a_2, \dots, a_9, a_{20}\}$. Total faults so far $= 10 + 10 = 20$.
• Second half ($a_1$ to $a_{20}$):
  • Accesses $a_1, a_2, \dots, a_9$ are all hits since they remained in frames $1$ through $9$ ($0$ faults).
  • Access $a_{10}$ is not present $\implies$ fault. It replaces the most recently loaded page $a_{20}$.
  • Accesses $a_{11}, \dots, a_{19}$ fault successively, each replacing the single volatile frame slot ($9$ faults).
  • Access $a_{20}$ faults, replacing $a_{19}$ ($1$ fault).
  • Second half faults $= 1 + 9 + 1 = 11$ faults.
• Total LIFO page faults $= 20 + 11 = 31$.

2. Optimal (OPT) Policy:

• There are 20 distinct virtual pages and only 10 frames available.
• During the first half, all 20 distinct pages are referenced for the first time, causing at least 20 cold misses.
• The 10 frames can hold at most 10 distinct pages between the first and second passes.
• In the second pass, at most 10 pages can hit (specifically, the 10 pages chosen to be retained in memory). The remaining 10 pages must fault.
• Thus, the theoretical minimum number of page faults for any policy is $20 + 10 = 30$.
• OPT achieves this bound by retaining the first 10 pages $\{a_1, \dots, a_{10}\}$ (which will be accessed first in the second pass at positions 21 to 30) and immediately evicting pages $a_{11}, \dots, a_{20}$ as they arrive, ensuring 10 hits on $a_1, \dots, a_{10}$ during the second pass.
• Total OPT page faults $= 30$.

Calculate the difference: