The simplest page replacement algorithm is a FIFO
algorithm.
A FIFO replacement algorithm associate the time with
each page when that page was brought into memory.
When a page must be replaced,
the oldest page is chosen, it not strictly necessary to record the time when a
page is brought in.
We can create a FIFO queue
to hold all pages in memory. We replace the page at the head of the queue.
When a page is brought
into memory, we insert it at the tail of the queue.
For our example reference
string, out three frames are initially empty.
1.
The first three references (7,0,1) cause
page faults, and are brought into these empty frames.
2.
The next reference (2) replaces page 7,
because page 7 was brought in first.
3.
Since 0 is the next reference and 0 is
already in memory, we have no page fault for this reference.
4.
The first reference to 3 results in page 0
being replaced, since it was the first of the three pages in memory (0, 1 and
2) to be brought in.
5.
This replacement means that the next
reference to 0 will fault. Page 1 is then replaced by page 0.
Advantage:
The FIFO page-replacement algorithm is easy to
understand and program.
Disadvantage:
1.
Its performance is not always good.
2.
A bad replacement choice increases the
page-fault rate and slows process execution, but does not cause incorrect
execution.