Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the *optimal replacement policy* is _________.

We trace the optimal page replacement algorithm with 3 frames for the reference string:

1. Ref 1: Miss (Page Fault 1). Frames: $[1, -, -]$

2. Ref 2: Miss (Page Fault 2). Frames: $[1, 2, -]$

3. Ref 3: Miss (Page Fault 3). Frames: $[1, 2, 3]$

4. Ref 4: Miss (Page Fault 4). Future references: $2$ (next), $1$ (soon after), $3$ (later). Replace page $3$ (farthest in future). Frames: $[1, 2, 4]$

5. Ref 2: Hit. Frames: $[1, 2, 4]$

6. Ref 1: Hit. Frames: $[1, 2, 4]$

7. Ref 5: Miss (Page Fault 5). Future references: $3$, $2$, $4$, $6$. Pages in frames are $1, 2, 4$. Page $1$ is never referenced again. Replace page $1$. Frames: $[5, 2, 4]$

8. Ref 3: Miss (Page Fault 6). Future references: $2$, $4$, $6$. Pages in frames are $5, 2, 4$. Page $5$ is never referenced again. Replace page $5$. Frames: $[3, 2, 4]$

9. Ref 2: Hit. Frames: $[3, 2, 4]$

10. Ref 4: Hit. Frames: $[3, 2, 4]$

11. Ref 6: Miss (Page Fault 7). Replace any page (e.g., $3$). Frames: $[6, 2, 4]$

Total number of page faults = 7.