Page 140 - DCAP403_Operating System

Unit 7: Memory Management

Least Recently Used (LRU) Notes

You have seen that an algorithm must use some kind of behavior prediction if it is to be effi cient.
One of the most basic page replacement approaches uses the usage of a page as an indication of
its “worth” when searching for a victim page: the Least Recently Used (LRU) Algorithm. LRU
was designed to take advantage of “normal” program operation, which generally consists of a
series of loops with calls to rarely executed code. In terms of the virtual addressing and pages,
this means that the majority of code executed will be held in a small number of pages; essentially
the algorithm takes advantage of the locality principal. As per the previous description of
locality, LRU assumes that a page recently referenced will most likely be referenced again soon.
To measure the “time” elapsed since a page has been a part of the reference stream, a backward
distance is stored. This distance must always be greater than zero, the point for the current position
in the reference stream, and can be defi ned as infi nite in the case of a page that has never been

referenced. Thus, the victim page is defined as the one with the maximum backward distance;
if two or more points meet this condition, a page is chosen arbitrarily. Actual implementation
of the backward distance number can vary, and does play an important role in the speed and

efficiency of this algorithm. This can be done by sorting page references in order of their age into

a stack, allowing quick identification of victims. However the overhead associated with sorting

does not generally justify the speed of identification, unless specific hardware exists to perform

this operation. Many operating systems do not assume this hardware exists (such as UNIX), and
instead increment an age counter for every active page during the page stream progression, as
described by. When a page is referenced once again, or is brought in due to a page fault, its value
is simply set to zero. Since storage for the backward age is limited, a maximum value may also
be defined; generally any page that has reached this age becomes a valid target for replacement.

As with any algorithm, modifications can be made to increase performance when additional
hardware resources are available.
Example: A machine with n page frames, the LRU hardware can maintain a matrix of
n × n bits, initially all zero. Whenever page frame k is referenced, the hardware first sets all the

bits of row k to 1, then sets all the bits of column k to 0. At any instant, the row whose binary
value is lowest is the least recently used, the row whose value is next lowest is next least recently
used, and so forth. The workings of this algorithm are given in Figure 7.12 for four page frames
and page references in the order.

0 1 2 3 2 1 0 3 2 3
After page 0 is referenced, we have the situation of Figure 7.12(a). After page 1 is reference, we
have the situation of Figure 7.12(b), and so forth.
Figure 7.12: LRU using a matrix when pages are referenced in the
order 0, 1, 2, 3, 2, 1, 0, 3, 2, 3.
Page Page Page Page Page
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0
2 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 0 1
3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0
(a) (b) (c) (d) (e)
0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0
1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0
1 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0
(f) (g) (h) (i) (j)

LOVELY PROFESSIONAL UNIVERSITY 133