A page-replacement algorithm should minimize the number of page
faults. We can do 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 that are associated with that frame. Then, to
replace a page, we search for the page frame with the smallest counter.
a. Define a page-replacement algorithm using this basic idea. Specifically address the problems of
faults. We can do 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 that are associated with that frame. Then, to
replace a page, we search for the page frame with the smallest counter.
a. Define a page-replacement algorithm using this basic idea. Specifically address the problems of
(1) what the initial value of the counters is,
(2) when counters are increased,
(3) when counters are decreased,
(4) how the page to be replaced is selected.
b. How many page faults occur for your algorithm for the following reference string, for four page frames?
b. How many page faults occur for your algorithm for the following reference string, for 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 pagereplacement strategy for the reference string in part b with four page frames?
1. Initial value of the counters—0.
2. Counters are increased—whenever a new page is associated with that frame.
3. Counters are decreased—whenever one of the pages associated with that frame is no longer required.
4. How the page to be replaced is selected —find a frame with the smallest counter. Use FIFO for breaking ties.
b. 14 page faults
c. 11 page faults