Page Replacement in Operating System:
Definition and Explanation:
In a multiprogramming environment, almost all programs use probably half of their size. For example, a program of 10 pages actually uses only 5 pages. The demand paging mechanism saves the I/O time necessary to load the fives pages that are never used. In this case, the degree of multiprogramming should be increased.
Increasing the degree of multiprogramming may lead to the situation where over allocation memory could occur. This can be explained as follow:
If a page fault occurs, the operating system checks the internal page table. It determines where the desired page is on the disk but finds no more free frames for these required pages to be swapped in. The operating system has some options to solve this problem:
- Either it terminates the user program immediately; or
- It swaps out one program and frees all of its frames. It reduces the degree of multiprogramming.
Page replacement is another possibility in this situation. It frees one frame that is not currently used. It writes the contents of the frame to the disk and changes the page table to indicate this page is no longer in memory. The freed frame can now be used to hold the page for which the program faulted. The page fault processing procedure can be modified to include the page replacement mechanism:
- Find the location of the desired page on the disk
- Find a free frame. If there is a free frame, use it. Otherwise use a page-replacement algorithm to select a frame, write the selected page to the disk and change the page and frame tables accordingly
- Read the desired page into the newly free frame; change the page and frame tables
- Restart the user process
If there is no free frame and the page replacement mechanism takes place, two page transfers are carried out. This doubles the page fault processing time and therefore increases the effective access time.
In order to reduce this overhead, the modify bit can be used. Each page or frame has a modify bit. Setting this bit to 1 indicates that the associated page has been modified since it was read from the disk. When we select a page for replacement, we check its modified bit first. If this bit is set, we must write this page to the disk before swapping in the desired page. Otherwise, we can avoid writing this page to the disk.
