Page 178 - DCAP103_Principle of operating system

Unit 5: Memory Management

5.7.4 FIFO — First In First Out Notes
The simplest way of replacing frames is to keep track of their age (by storing their age in the
frame table). This could either be the date, as recorded by the system clock, or a sequential
counter. When a new page fault occurs, we can load in pages until the physical memory is
full — thereafter, we have to move out pages. The page which has been in memory longest is
then selected as the first to go.

This algorithm has the advantage of being very straightforward, but its performance can suffer
if a page is in heavy use for a long period of time. Such a page would be selected even though
it was still in heavy use.

FIFOs are used commonly in electronic circuits for buffering and flow control
which is from hardware to software. In hardware form a FIFO primarily
consists of a set of read and write pointers, storage and control logic.

Data sent via FIFO is not persisted in memory and can be an unreliable
method for data sources. To ensure your data is not lost.
5.7.5 Second Chance

A simple optimization we can add to the FIFO algorithm is the following. Suppose we keep a
reference bit for each page in the page table. Every time the memory management unit accesses
a page it sets that bit to. When a page fault occurs, the page replacement algorithm looks at that
bit and - if it is set to — sets the bit to but jumps over it and looks for another page.

The idea is that pages which are frequently use will have their bits set often and will
therefore not get paged out. Of course, this testing incurs an overhead. In the extreme case
that all pages are in heavy use the page algorithm must cycle through all the pages setting
their bits to zero before finding the original page again. Even then, it might not find a page
to replace, if the bit was set again while it was looking through the others. In such a case,
the paging system simply fails.

5.7.6 LRU—Least Recently Used
The best possible solution to paging would be to replace the page that will not be used for the
longest period of time—but unfortunately, the system has no way of knowing what that
is. A kind of compromise solution is to replace the page which has not been used for the
longest period. This does not require a crystal ball, but it does require some appropriate
hardware support to make it worthwhile. As with all good ideas, it costs the system quite
a lot to implement it.
Two possibilities for such an implementation are the following:
• We record the time at which each page was last referenced. Unlike the FIFO scheme
above, this means that we have to update the time-stamp every single time memory is
referenced, instead of only each time a page is replaced. If the copying operation takes,
say, five CPU instructions (jump to update routine, locate page table entry, load system
clock time, store system clock time, return), this means — roughly speaking — that the
system is slowed down by a factor of around five. This is an unacceptable loss, so unless
the memory management unit can do something fancy in hardware, this scheme is not
worth the system’s time.
• We keep a stack of page addresses, so that the page number of the most recently accessed
page is always on the top of the stack. Although this sounds cheaper in principle, since the

LOVELY PROFESSIONAL UNIVERSITY 171