Basic Page Replacement

• Page replacement takes the following approach (see Fig. 10).
  • If no frame is free, we find one that is not currently being used and free it.
  • We can free a frame by writing its contents to swap space and changing the page table (and al other tables) to indicate that the page is no longer in memory.
  • We can now use the freed frame to hold the page for which the process faulted.

  Figure 10: Page replacement.

  
• We modify the page-fault service routine to include page replacement:
  1. Find the location of the desired page on the disk.
  2. Find a free frame:

     a

     If there is a free frame, use it.

     b

     If there is no free frame, use a page-replacement algorithm to select a victim frame.

     c

     Write the victim frame to the disk; change the page and frame tables accordingly.

  3. Read the desired page into the newly freed frame; change the page and frame tables.
  4. Restart the user process.
• Notice that, if no frames are free, two page transfers (one out and one in) are required.
• We can reduce this overhead by using a modify bit (or dirty bit).
• The modify bit for a page is set by the hardware whenever any word or byte in the page is written into, indicating that the page has been modified.
• When we select a page for replacement, we examine its modify bit.
  • If the bit is set, we know that the page has been modified since it was read in from the disk (write that page to the disk).
  • If the modify bit is not set, the page has not been modified since it was read into memory (not write the memory page to the disk: It is already there).
• This technique also applies to read-only pages (for example, pages of binary code).
• This scheme can significantly reduce the time required to service a page fault, since it reduces I/O time by one-half if the page has not been modified.
• Page replacement is basic to demand paging. It completes the separation between logical memory and physical memory.
• We must solve two major problems to implement demand paging:
  1. develop a frame-allocation algorithm. If we have multiple processes in memory, we must decide how many frames to allocate to each process.
  2. develop a page-replacement algorithm. When page replacement is required, we must select the frames that are to be replaced.
• Designing appropriate algorithms to solve these problems is an important task, because disk I/O is so expensive. Even slight improvements in demand-paging methods yield large gains in system performance.
• Second major problem will be discussed firstly.
• For a given page size (and the page size is generally fixed by the hardware or system), we need to consider only the page number, rather than the entire address.
• If we have a reference to a page $p$, then any immediately following references to page $p$ will never cause a page fault (page $p$ will be in memory after the first reference).
• For example, if we trace a particular process, we might record the following address sequence:

  0100,0432,0101,0612,0102,0103,0104,0101,0611,0102,0103,
  0104,0101,0610,0102,0103,0104,0101,0609,O102,0105
  

• At 100 bytes per page, this sequence is reduced to the following reference string:

  1,4,1,6,1,6,1,6,1,6,1
  

• As the number of frames increases, the number of page faults drops to some minimal level (see Fig. 11).

  Figure 11: Graph of page faults versus number of frames.

  
• Next several page-replacement algorithms are illustrated. The following reference string will be used to exemplify for a memory with three frames.

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