This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
In the discussion above we said that when a page fault occurs we evict a page
that is currently mapped and replace it with the page that we are currently
trying to access. In doing this, we need to write the page we are evicting to
disc, if it has been modified.
However, we have not said how we decide which page to evict. One of the easiest
methods would be to choose a mapped page at random but this is likely to lead
to degraded system performance. This is because the page chosen has a reasonable
chance of being a page that will need to be used again in the near future. Therefore,
it will be evicted (and may have to be written to disc) and then brought back
into memory; maybe on the next instruction.
There has been a lot of work done in this area and in this section we describe
some of the algorithms.
The interested student might like to look at (Smith, 1978) which lists over 300 papers on this topic.
You might recall, when we were discussing process scheduling, that there is
an optimal scheme where we always schedule the shortest job first. This leads
to the minimum average waiting time. The problem is we cannot identify the burst
time of a process before it is run. Therefore, it may be optimal, but we cannot
implement it.
This page replacement algorithm is similar in that it leads to an optimal solution,
but we cannot implement it.
The basis of the algorithm is that we evict the page that we will not use for
the longest period. For example, if we only have two pages to choose from, one
of which will be used on the next instruction and the other will not be used
for another one hundred instructions. It makes sense to evict the page that
will be used for one hundred instructions.
The problem, of course, is that we cannot look into the future and decide which page to evict. But, if we could, we could implement an optimal algorithm.
But, if we cannot implement the algorithm then why bother discussing it? In fact, we can implement it, but only after running the program to see which pages we should evict and at what point. Once we know that we can run the optimal page replacement algorithm. We can then use this as a measure to see how other algorithms perform against this ideal.
In order to implement this algorithm we make use of the referenced and modified
bits that were mentioned above. These bits are often implemented in hardware
(as they are updated so much) but they can be simulated in software as follows.
When a process starts, all its page entries are marked as not in memory (i.e. the present/absent bit). When a page is referenced a page fault will occur. The R (reference) bit is set and the page table entry modified to point to the correct page. In addition the page is set to read only. If the page is later written to, the M (modified) bit is set and the page is changed so that it is read/write.
Updating the flags in this way allows a simple paging algorithm to be built.
When a process is started up all R and M bits are cleared (set to zero). Periodically
(e.g. on each clock interrupt) the R bit is cleared. This allows us to recognise
which pages have been recently referenced.
When a page fault occurs (so that a page needs to be evicted), the pages are inspected and divided into four categories based on their R and M bits.
Class 0 : Not Referenced, Not Modified
Class 1 : Not Referenced, Modified
Class 2 : Referenced, Not Modified
Class 3 : Referenced, Modified
The Not-Recently-Used (NRU) algorithm removes a page at random from the lowest numbered class that has entries in it. Therefore, pages which have not been referenced or modified are removed in preference to those that have not been referenced but have been modified (which is not as impossible as it sounds due to the fact that the reference bit is periodically reset).
Although, not an optimal algorithm, NRU often provides adequate performance
and is easy to understand and implement.
This algorithm simply maintains the pages as a linked list, with new pages being added to the end of the list. When a page fault occurs, the page at the head of the list (the oldest page) is evicted. Whilst simple to understand and implement a simple FIFO algorithm does not lead to good performance as a heavily used page is just as likely to be evicted as a lightly used page.
The second chance (SC) algorithm is a modification of the FIFO algorithm. When a page fault occurs the page at the front of the linked list is inspected. If it has not been referenced (i.e. its reference bit is clear), it is evicted. If its reference bit is set, then it is placed at the end of the linked list and its reference bit reset. The next page is then inspected. In this way, a page that has been referenced will be given a second chance.
In the worst case, SC operates in the same way as FIFO. Take the situation
where the linked list consists of pages which all have their reference bit set.
The first page, call it a, is inspected and placed at the end of the list, after
having its R bit cleared. The other pages all receive the same treatment. Eventually
page a reaches the head of the list and is evicted as its reference bit is now
clear.
Therefore, even when all pages in a list have their reference bit set, the algorithm
will always terminate.
The clock page (CP) algorithm differs from SC only in its implementation.
Whilst SC is a reasonable algorithm it suffers in the amount of time it has
to devote to the maintenance of the linked list. It is more efficient to hold
the pages in a circular list and move the pointer rather than move the pages
from the head of the list to the end of the list.
It is called the clock page algorithm as it can be visualised as a clock face
with the hand (pointer) pointing at the pages, which represent the numbers on
the clock.
The next page will examine another page replacement strategy in more detail.
| Last Page | Back to Main Index | Next Page |
Last Updated : 23/01/2002