Consider a computer system with ten physical page frames. The system is provided with an access sequence $(a_1, a_2, \ldots, a_{20}, a_1, a_2, \ldots, a_{20})$, 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 ________.

We are given $10$ physical frames and an access string of $40$ page accesses containing $20$ distinct pages repeated twice:

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

• First 10 accesses ($a_1$ to $a_{10}$): Each page misses and is placed into an empty frame. Frame content: $\{a_1, a_2, \ldots, a_{10}\}$. (10 faults)

• Next 10 accesses ($a_{11}$ to $a_{20}$):

  • $a_{11}$ replaces $a_{10}$ (the last inserted page). Frame: $\{a_1, \ldots, a_9, a_{11}\}$.

  • $a_{12}$ replaces $a_{11}$, and so on, until $a_{20}$ replaces $a_{19}$. Frame content at the end of the first pass: $\{a_1, a_2, \ldots, a_9, a_{20}\}$. (10 faults)

• Second pass ($a_1$ to $a_{20}$):

  • $a_1$ through $a_9$ are all hits because they remained in the first $9$ frames (0 faults).

  • $a_{10}$ misses and replaces $a_{20}$. Frame: $\{a_1, \ldots, a_9, a_{10}\}$. (1 fault)

  • $a_{11}$ through $a_{20}$ all miss, each replacing the previously inserted page (10 faults).

• Total faults for LIFO $= 10 + 10 + 0 + 1 + 10 = 31$.

### 2. Optimal (OPT) Policy:

• First 10 accesses ($a_1$ to $a_{10}$): All miss and fill the 10 frames (10 faults).

• Accesses $a_{11}$ to $a_{20}$:

  • In the future, pages $a_1, \dots, a_9$ will be accessed earlier in the second pass than $a_{10}, a_{11}, \dots$

  • Thus, OPT always replaces the page that is needed furthest in the future. It can retain $\{a_1, \ldots, a_9, a_{20}\}$ or any 10 pages for the second pass.

  • Each of $a_{11}, \ldots, a_{20}$ causes a fault (10 faults).

• Second pass:

  • Exactly $10$ pages residing in frames will result in hits ($a_1, \ldots, a_9$ and $a_{20}$), while the remaining $10$ pages fault (10 faults).

• Total faults for OPT $= 10 + 10 + 10 = 30$.

### Difference:

Thus, the difference is 1.