-
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__________.
-
- 1
- 7
- 0
- 17
Correct Option: B
The given reference string is:
1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6.
Available no. of frames = 3.
We know that in the optimal replacement policy, when a page fault occurs, the required page is loaded from secondary memory and “that page in main memory will be replaced which will not be used for the longest period of time”. Use of this algorithm guarantees the lowest possible page fault rate for a fixed number of frames. Furthermore, this algorithm also does not suffer with Belady’s Anomaly.
Required page
Frames
Page fault (Y/N)
We can see that “Page 4” replaced “Page 3” as it will not be used for longest period of time (Page 1, 2 both will be used before page 3). Similarly, Red marked page - 3 replaced page - 5 as both page - 2, 4 will be used in future. From the above table:
Total no. of page faults = 7.
