Page 187 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
Figure 5.27: Need for Page Replacement

Valid-invalid
0 H Frame, bit 0 Monitor
1 load M 3 v 1
PC
2 J 4 v 2 D
5 v
3 M l 3 H B
Logical memory Page table 4 bad M
for user 1 for user 1
5 J
6 A
M
Valid-invalid 7 E
0 A Frame bit
Physical
1 B 6 v memory
i
2 D
2 v
3 E 7 v
Logical memory page table
for user 2 for user 2

Users should not be aware that their processes are running on a paged system-paging should be
logically transparent to the user. So this option is not the best choice. The operating system could
swap out a process, freeing all its frames, and reducing the level of multiprogramming. This
option is a good one in certain circumstances; Here, we discuss a more intriguing possibility—
page replacement.
5.10.1 Basic Scheme
Page replacement takes the following approach. 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 all 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. 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 page to the disk; change the page and frame tables accordingly.
3. Read the desired page into the (newly) free 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. This
situation effectively doubles the page-fault service time and increases the effective access time
accordingly. We can reduce this overhead by using a modify bit (or dirty bit). Each page or
frame may have a modify bit associated with it in the hardware. The modify m 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. In
this case, we must write that page to the disk. If the modify bit is not set, however, the page
has not been modified since it was read into memory. Therefore, if the copy of the page on the
disk has not been overwritten (by some other page, for example), then we can avoid writing the

180 LOVELY PROFESSIONAL UNIVERSITY