There are many different
page replacement algorithms. Probably every operating system has its own unique
replacement scheme.
How do we select a
particular replacement algorithm? In genrate, want the one with the lowest page
fault rate.
We evaluate an algorithm by running it on a
particular string of memory references and computing the number of page faults.
The string of memory references is called reference string.
We can generate reference
string:
1. Artificially(by
a random number generator for example) or
The second choice produces a large number of data (on
the order of 1 million address per second)
To reduce the number of
data, we note two things
1. For
a given page size (and the page size is
generally fixed by the hardware or system.) we need to consider only the page
number. Not the entire address.
2. If
we have a reference to a page, page p will be in memory after the first
reference; the immediately following reference will not fault.
0100,0432,0101,0612,0102,0103,0104,0101,0611,0102,0103,0104,0101,0610,0102,0103,0104,0101,0609,0102,0105,
Which at 100 bytes per page is reduced to the following
reference string.
1,4,1,6,1,6,1,6,1,6,1
To determine the number of
page faults for a particular reference
string and page replacement algorithm, we also need to know the number
of page frames available.
Obviously as the number of
frames available increases, the number of faults will decrease.
For the reference string
considered previously, for example if we had three or more frames we would have
only three faults one fault for the first reference to each page.
But with only one frame
available we would have replacement with every reference, resulting in 11 faults
As the number of frames increase the number of
page faults drops to some minimal level. Of course, adding physical memory
increases the number of frames.
To illustrate the page replacement algorithms, we shall
use the reference string
7,0,1,2,0,3,0,2,1,0,1,7,0,1 for a memory with three
frames.