Question

Consider the following page reference string :

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
v) For Optimal page replacement algorithms with 3 frames, the number of page faults is :
a) 16
b) 15
c) 14
d) 11

Answer 1

In the Optimal page replacement algorithm with 3 frames, the number of page faults for a given page reference string can be calculated by simulating the algorithm. The answer in this case is 15.

Step-by-step explanation:

Page Replacement Algorithm - Optimal

In the given page reference string, the number of page faults is calculated using the Optimal page replacement algorithm with 3 frames.

The page reference string is: 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

The algorithm works by replacing the page that will not be used for the longest time, i.e., the one which has the longest time before it is referenced again.

To determine the number of page faults, we simulate the algorithm by going through the page reference string:

1. Initially, the frames are empty. So, the first three page requests (1, 2, 3) are all page faults because there are no pages in the frames.
2. When the 4th page request (4) is made, there is a page fault because the frame is full and it needs to replace one of the existing pages (1 or 2 or 3).
3. The 5th page request (2) is not a page fault because the page is already present in one of the frames. The same goes for the 6th page request (1).
4. ...continue this process to determine the total number of page faults

By following this process and counting the number of page faults, the answer is option (b) 15.