Basic page replacement

Basic page replacement

If no frame is fee, find page that is not currently being used and free it. Frame is freed by writing its contents to swap space and changing the page table to indicate that the page is no longer in memory. The page fault service routine is modified to include page replacement.

1. Find the location of the desired page on the disk, either in swap space or in the file system.
2. Find a free frame:
1. If there is a free frame, use it.
2. If there is no free frame, use a page-replacement algorithm to select an existing frame to be replaced, known as the victim frame.
3. Write the victim frame to disk. Change all related page tables to indicate that this page is no longer in memory.
3. Read in the desired page and store it in the frame. Adjust all related page and frame tables to indicate the change.
4. Restart the process that was waiting for this page.

A modify bit or dirty bit is used to reduce the overhead of disk write. A dirty bit of each page indicate whether or not it has been changed since it was last loaded in from disk. If the dirty bit has not been set, then the page is unchanged, and does not need to be written out to disk. Otherwise the page write is required. It should come as no surprise that many page replacement strategies specifically look for pages that do not have their dirty bit set, and preferentially select clean pages as victim pages.

Page replacement is basic to demand paging. There are two major requirements to implement a successful demand paging system: developing a frame-allocation algorithm and a page-replacement algorithm. . The former decides how many frames are allocated to each process ( and to other needs ), and the latter deals with how to select a page for replacement when there are no free frames available.

The overall goal in selecting and tuning these algorithms is to generate the fewest number of overall page faults. 

Algorithms are evaluated using a given string of memory accesses known as a reference string, and computing the number of page faults. To determine the number of page faults for a particular reference string and page replacement algorithm, number of page frames available is also needed. As the number of page frames available increases the number of page faults decreases.