A page-replacement algorithm should minimize the number of page faults. We can achieve this minimization by distributing heavily used pages evenly over all of memory, rather than having them compete for a small number of page frames. We can associate with each page frame a counter of the number of pages associated with that frame. Then,to replace a page, we can search for the page frame with the smallest counter
$a$. Define a page-replacement algorithm using this basic idea. Specifically address these problems:
$i$. What is the initial value of the counters ?
$ii$. When are counters increased ?
$iii$. When are counters decreased ?
$iv$. How is the page to be replaced selected ?
$b$. How many page faults occur for your algorithm for the following reference string with four page frames ?
$1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.$
$c$. What is the minimum number of page faults for an optimal page replacement strategy for the reference string in part $b$ with four page frames?