Counting Based Page
replacement:
There are several
algorithms based on counting the number of references that have been made to a
given page, such as:
o
. Least
Frequently Used, LFU: Replace the page with the lowest
reference count. A problem can occur if a page is used frequently initially and
then not used any more, as the reference count remains high. A solution to this
problem is to right-shift the counters periodically, yielding a time-decaying
average reference count
o Most
Frequently Used, MFU: Replace the page with the highest
reference count. The logic behind this idea is that pages that have already
been referenced a lot have been in the system a long time, and we are probably done
with them, whereas pages referenced only a few times have only recently been
loaded, and we still need them.
In
general counting-based algorithms are not commonly used, as their
implementation is expensive and they do not approximate OPT well.
Page-Buffering
Algorithms:
There
are number of page buffering algorithms often used in addition to a specific
page replacement algorithm.
For
example, maintain a certain minimum number of free frames at all times. When a
page-fault occurs, go ahead and allocate one of the free frames from the free
list first, to get the requesting process up and running again as quickly as
possible, and then select a victim page to write to disk and free up a frame as
a second step.
Keep
a list of modified pages, and when the I/O system is otherwise idle, have it
write these pages out to disk, and then clear the modify bits, thereby
increasing the chance of finding a "clean" page for the next
potential victim.
Keep
a pool of free frames, but remember what page was in it before it was made
free. Since the data in the page is not actually cleared out when the page is
freed, it can be made an active page again without having to load in any new
data from disk. This is useful when an algorithm mistakenly replaces a page
that in fact is needed again soon.
Applications and
Page replacement:
·
Some applications ( most notably
database programs ) understand their data accessing and caching needs better
than the general-purpose OS, and should therefore be given reign to do their
own memory management.
·
Sometimes such programs are given
a raw disk partition to work with, containing raw data blocks
and no file system structure. It is then up to the application to use this disk
partition as extended memory or for whatever other reasons it sees fit.
No comments:
Post a Comment