Page 195 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes The least frequently used (LFU) page-replacement algorithm requires that the page with the
smallest count be replaced. The reason for this selection is that an actively used page should
have a large reference count. This algorithm suffers from the situation in which a page is used
heavily during the initial phase of a process, but then is never used again. Since it was used
heavily, it has a large count and remains in memory even though it is no longer needed. One
solution is to shift the counts right by 1 bit at regular intervals, forming an exponentially decaying
average usage count.
The most frequently used (MFU) page-replacement algorithm is based on the argument that the
page with the smallest count was probably just brought in and has yet to be used. As you might
expect, neither MFU nor LFU replacement is common. The implementation of these algorithms
is expensive, and they do not approximate OPT replacement well.
5.11.8 Page-buffering Algorithm

Other procedures are often used in addition to a specific page-replacement algorithm. For
example, systems commonly keep a pool of free frames. When a page fault occurs, a victim frame
is chosen as before. However, the desired page is read into a free frame from the pool before the
victim is written out. This procedure allows the process to restart as soon as possible, without
waiting for the victim page to be written out. When the victim is later written out, its frame is
added to the free-frame pool. An expansion of this idea is to maintain a list of modified pages.
Whenever the paging device is idle, a modified page is selected and is written to the disk. Its
modify bit is then reset. This scheme increases the probability that a page will be clean when it
is selected for replacement, and will not need to be written out. Another modification is to keep
a pool of free frames, but to remember which page was in each frame. Since the frame contents
are not modified when a frame is written to the disk, the old page can be reused directly from
the free-frame pool if it is needed before that frame is reused. No 1/0 is needed in this case.
When a page fault occurs, we first check whether the desired page is in the free-frame pool. If
it is not, we must select a free frame and read into it.

This technique is used in the VAX/VMS system, with a FIFO replacement algorithm. When
the FIFO replacement algorithm mistakenly replaces a page that is still in active use, that page
is quickly retrieved from the free-frame buffer, and no I/O is necessary. The free-frame buffer
provides protection against the relatively poor, but simple, FIFO replacement algorithm. This
method is necessary because the early versions of the VAX did not implement the reference
bit correctly.

5.12 Thrashing

If the number of frames allocated to a low-priority process falls below the minimum number
required by the computer architecture, we must suspend that process execution. We should
then page out its remaining pages, freeing all its allocated frames. This provision introduces
a swap-in, swap-out level of intermediate CPU scheduling. In fact, look at any process that
does not have “enough” frames. Although it is technically possible to reduce the number of
allocated frames to the minimum, there is some (larger) number of pages in active use. If the
process does not have this number of frames, it will quickly page fault. At this point, it must
replace some page. However, since all its pages are in active use, it must replace a page that
will be needed again right away. Consequently, it quickly faults again, and again, and again.
The process continues to fault, replacing pages for which it then faults and brings back in right
away. This high paging activity is called thrashing. A process is thrashing if it is spending more
time paging than executing.

188 LOVELY PROFESSIONAL UNIVERSITY