In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows: *The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.* A process accesses the pages in the following order of page numbers: $$1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.$$ If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ________ . (Answer in integer)

We are given a sequence of 12 page references:

with 3 initially empty frames.

When a page fault occurs, the OS inspects a lookahead window of up to 4 page references (the current page plus the next 3 future page references) and replaces the page in memory that will not be used for the longest time within this 4-page window.

Let's trace step-by-step:

1. Ref 1: Frame state: $\{1\}$ $\rightarrow$ Page Fault (1)

2. Ref 3: Frame state: $\{1, 3\}$ $\rightarrow$ Page Fault (2)

3. Ref 2: Frame state: $\{1, 3, 2\}$ $\rightarrow$ Page Fault (3)

4. Ref 4: Page fault occurs. Lookahead window (4 references starting from index 4): $\langle 4, 2, 3, 1 \rangle$.

   • Page $2$ is accessed at index 5.

   • Page $3$ is accessed at index 6.

   • Page $1$ is accessed at index 7 (farthest in window).

   Therefore, page $1$ is replaced with page $4$. Frame state: $\{4, 3, 2\}$ $\rightarrow$ Page Fault (4)

5. Ref 2: Page $2$ is present $\rightarrow$ Hit (Frames: $\{4, 3, 2\}$)

6. Ref 3: Page $3$ is present $\rightarrow$ Hit (Frames: $\{4, 3, 2\}$)

7. Ref 1: Page fault occurs. Lookahead window (4 references starting from index 7): $\langle 1, 2, 4, 3 \rangle$.

   • Page $2$ is accessed at index 8.

   • Page $4$ is accessed at index 9.

   • Page $3$ is accessed at index 10 (farthest in window).

   Therefore, page $3$ is replaced with page $1$. Frame state: $\{4, 1, 2\}$ $\rightarrow$ Page Fault (5)

8. Ref 2: Page $2$ is present $\rightarrow$ Hit (Frames: $\{4, 1, 2\}$)

9. Ref 4: Page $4$ is present $\rightarrow$ Hit (Frames: $\{4, 1, 2\}$)

10. Ref 3: Page fault occurs. Lookahead window (remaining references starting from index 10): $\langle 3, 1, 4 \rangle$.

    • Page $1$ is accessed at index 11.

    • Page $4$ is accessed at index 12.

    • Page $2$ is not referenced at all within the window.

    Therefore, page $2$ is replaced with page $3$. Frame state: $\{4, 1, 3\}$ $\rightarrow$ Page Fault (6)

11. Ref 1: Page $1$ is present $\rightarrow$ Hit (Frames: $\{4, 1, 3\}$)

12. Ref 4: Page $4$ is present $\rightarrow$ Hit (Frames: $\{4, 1, 3\}$)

Total number of page faults $= 6$.