Page Replacement

When a page fault occurs and all frames are occupied a decision must be made as to what page to swap out. The page replacement algorithm is used to choose what page should be swapped.

Note that if there is no free frame a busy one must be swapped out and the new one swapped in. This means a double transfer – which takes time. However if we can find a busy page that has not been modified since it was loaded to disk then it does not need to be written back out. The modified bit in the page table entry indicates whether a page has been modified or not. Thus the I/O overhead is cut by half if the page is unmodified.

Page Replacement Algorithm

Optimal Replacement The best policy is one which swaps out a page that will not be used for the longest period of time. This will give the lowest possible page fault rate for a fixed number of frames.

Consider the following string of pages which are to be processed.

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

If we assume an address space of three frames, the pattern of page faults is shown below.

20 pages to be processed

Page Frames

Optimal page replacement

Unfortunately the optimum scheme is impossible to implement as we need to know in advance what pages will be demanded. However it can be used as a standard to judge other schemes by.