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)
Although we cannot implement an optimal algorithm by evicting the page that
will not be used for the longest time in the future, we can approximate the
algorithm by keeping track of when a page was last used. If a page has recently
been used then it is likely that it will be used again in the near future. Conversely,
a page that has not been used for some time is unlikely to be used again in
the near future.
Therefore, if we evict the page that has not been used for the longest amount of time we can implement a least recently used (LRU) algorithm.
Whilst this algorithm can be implemented (unlike the optimal algorithm) it is not cheap. Ideally, we need to maintain a linked list of pages which are sorted in the order in which they have been used. To maintain such a list is prohibitively expensive (even in hardware) as deleting and moving list elements is a time consuming process. Sorting a list is also expensive.
However, there are ways that LRU can be implemented in hardware. One way is as follows.
The hardware is equipped with a counter (typically 64 bits). After each instruction
the counter is incremented.
In addition, each page table entry has a field large enough to accommodate the counter. Every time the page is referenced the value from the counter is copied to the page table field. When a page fault occurs the operating system inspects all the page table entries and selects the page with the lowest counter. This is the page that is evicted as it has not been referenced for the longest time.
Another hardware implementation of the LRU algorithm is given below.
If we have n page table entries a matrix of n x n bits, initially all zero, is maintained. When a page frame, k, is referenced then all the bits of the k row are set to one and all the bits of the k column are set to zero. At any time the row with the lowest binary value is the row that is the least recently used (where row number = page frame number). The next lowest entry is the next recently used; and so on.
If we have four page frames and access them as follows
0 1 2 3 2 1 0 3 2 3
it leads to the algorithm operating as follows.
It might be worth working through it and calculating the binary value of each row to see which page frame would be evicted.
|
One of the main drawbacks with implementing LRU in hardware is that if the hardware does not provide these facilities then the operating system designers, obviously, cannot make use of them. Instead we need to implement a similar algorithm in software.
One method (called the Not Frequently Used - NFU algorithm) associates a counter with each page. This counter is initially zero but at each clock interrupt the operating system scans all the pages and adds the R bit for the page to its counter. As this is either zero or one, the counter either gets incremented or it does not.
When a page fault occurs the page with the lowest counter is selected for replacement.
The main problem with NFU is that it never forgets anything. For example, if
a multi-pass compiler is running, at the end of the first pass the pages may
not be needed anymore. However, as they will have high counts they will not
be replaced but pages from the second pass, which still have low counts, will
be replaced.
In fact, the situation could be even worse. If the first pass made a lot of
memory references but the second pass does not make as many, then the pages
from the first pass will always have higher counts than the second pass and
will therefore remain in memory.
To alleviate this problem we can make a modification to NFU so that it closely
simulates NRU. The modification is in two parts.
1. The counters are shifted right one bit before the R bit is added.
2. The R bit is added to the leftmost bit rather than the rightmost bit.
This implements a system of aging.
Look at the diagram below. This represents a page table with six entries. Working
from right to left we are showing the state of each of the pages (only the counter
entries) at each of the six clock ticks.
Consider the (a) column. After clock tick zero the R flags for the six pages
are set to 1, 0, 1, 0, 1 and 1. This indicates that pages 0, 2, 4 and 5 were
referenced.
This results in the counters being set as shown. We assume they all started
at zero so that the shift right, in effect, did nothing and the reference bit
was added to the leftmost bit.
If you look at the (b) clock tick you should be able to follow the algorithm
and similarly for (c) to (e) clicks.
 |
When a page fault occurs, the counter with the lowest value is removed. It is obvious that a page that has not been referenced for, say, four clocks ticks will have four zeroes in the leftmost positions and will have a lower value that a page that has not been referenced for three clock ticks.
The NFU algorithm differs from LRU in two ways.
Using the matrix LRU implementation we update the matrix after each instruction.
This, in effect, gives us more detailed information. If you look at pages 3
and 5 in the above diagram, after clock tick 4, both pages have not been referenced
for the last two clock ticks. But when they were referenced we do not know how
early (or late) in that clock tick the pages were referenced. All we are able
to do is evict page 3 as this has not been referenced anymore, whereas page
5 has.
The aging counters of NFU have a finite size. If two counters have a zero value, all we can do is choose one at random. Assuming that the counters are 8 bits then we do not know if the page was accessed 9 clock ticks ago or 1000 clock ticks ago. In practise, 8 bits are commonly used. If a clock tick is around 20ms and a page has a zero counter this means that the page has not been referenced for 160ms. In this case, it is probably not that important.
| Last Page | Back to Main Index | Next Page |
Last Updated : 23/01/2002