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.
|
