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.
- Find
the location of the desired page on the disk, either in swap space or in
the file system.
- Find
a free frame:
- If
there is a free frame, use it.
- If
there is no free frame, use a page-replacement algorithm to select an
existing frame to be replaced, known as the victim frame.
- Write
the victim frame to disk. Change all related page tables to indicate that
this page is no longer in memory.
- Read
in the desired page and store it in the frame. Adjust all related page and
frame tables to indicate the change.
- 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.
No comments:
Post a Comment