Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies First In First Out (FIFO) and Least Recently Used (LRU)?

We have 5 page frames and the reference string of length 15: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3

### 1. FIFO Simulation:

• 3: Fault $\rightarrow [3]$

• 8: Fault $\rightarrow [3, 8]$

• 2: Fault $\rightarrow [3, 8, 2]$

• 3: Hit $\rightarrow [3, 8, 2]$

• 9: Fault $\rightarrow [3, 8, 2, 9]$

• 1: Fault $\rightarrow [3, 8, 2, 9, 1]$

• 6: Fault (replaces 3) $\rightarrow [8, 2, 9, 1, 6]$

• 3: Fault (replaces 8) $\rightarrow [2, 9, 1, 6, 3]$

• 8: Fault (replaces 2) $\rightarrow [9, 1, 6, 3, 8]$

• 9: Hit $\rightarrow [9, 1, 6, 3, 8]$

• 3: Hit $\rightarrow [9, 1, 6, 3, 8]$

• 6: Hit $\rightarrow [9, 1, 6, 3, 8]$

• 2: Fault (replaces 9) $\rightarrow [1, 6, 3, 8, 2]$

• 1: Hit $\rightarrow [1, 6, 3, 8, 2]$

• 3: Hit $\rightarrow [1, 6, 3, 8, 2]$

Total FIFO faults = 9

---

### 2. LRU Simulation:

• 3: Fault $\rightarrow [3]$

• 8: Fault $\rightarrow [3, 8]$

• 2: Fault $\rightarrow [3, 8, 2]$

• 3: Hit $\rightarrow [8, 2, 3]$

• 9: Fault $\rightarrow [8, 2, 3, 9]$

• 1: Fault $\rightarrow [8, 2, 3, 9, 1]$

• 6: Fault (LRU is 8) $\rightarrow [2, 3, 9, 1, 6]$

• 3: Hit $\rightarrow [2, 9, 1, 6, 3]$

• 8: Fault (LRU is 2) $\rightarrow [9, 1, 6, 3, 8]$

• 9: Hit $\rightarrow [1, 6, 3, 8, 9]$

• 3: Hit $\rightarrow [1, 6, 8, 9, 3]$

• 6: Hit $\rightarrow [1, 8, 9, 3, 6]$

• 2: Fault (LRU is 1) $\rightarrow [8, 9, 3, 6, 2]$

• 1: Fault (LRU is 8) $\rightarrow [9, 3, 6, 2, 1]$

• 3: Hit $\rightarrow [9, 6, 2, 1, 3]$

Total LRU faults = 9

Both algorithms incur 9 page faults. Therefore, Both incur the same number of page faults is true.