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)
Answer
6
Explanation
On a fault with all frames full, look at the current reference and the next three. Replace a resident page that is not in this window; if all of them are in it, replace the one needed last.
- 1, 3, 2: three faults fill the frames: {1, 3, 2}.
- 4: fault. Window 4, 2, 3, 1, so page 1 is needed last; replace it: {4, 3, 2}. The next 2 and 3 are hits.
- 1: fault. Window 1, 2, 4, 3, so page 3 is needed last; replace it: {4, 1, 2}. The next 2 and 4 are hits.
- 3: fault. Window 3, 1, 4 does not contain page 2; replace it: {4, 1, 3}. The last 1 and 4 are hits.
Total page faults \(= 3 + 1 + 1 + 1 = 6\).
Answer: 6