Page 191 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes reference string. As a result, the optimal algorithm is used mainly for comparison studies. For
instance, it may be useful to know that, although a new algorithm is not optimal, it is within
12.3 per cent of optimal at worst, and within 4.7 per cent on average.
Figure 5.32: Optimal Page-replacement Algorithm

5.11 LRU Page Replacement

If the optimal algorithm is not feasible, perhaps an approximation to the optimal algorithm
is possible. The key distinction between the FIFO and OPT algorithms (other than looking
backward or forward in time) is that the FIFO algorithm uses the time when a page was
brought into memory; the OPT algorithm uses the time when a page is to be used. If we
use the recent past as an approximation of the near future, then we will replace the page that
has not been used for the longest period of time. This approach is the least-recently-used (LRU)
algorithm. LRU replacement associates with each page the time of that page’s last use. When a
page must be replaced, LRU chooses that page that has not been used for the longest period of
time. This strategy is the optimal page-replacement algorithm looking backward in time, rather
than forward. Strangely, if we let SR be the reverse of a reference string S, then the page-fault
R
rate for the OPT algorithm on S is the same as the page-fault rate for the OPT algorithm on S .
Figure 5.33: LRU Page-replacement Algorithm

Similarly, the page-fault rate for the LRU algorithm on S is the same as the page-fault rate for the
LRU algorithm on SR. The result of applying LRU replacement to our example reference string is
shown in the Figure 5.33. The LRU algorithm produces 12 faults. Notice that the first five faults
are the same as the optimal replacement. When the reference to page 4 occurs, however, LRU
replacement sees that, of the three frames in memory, page 2 was used least recently. The most
recently used page is page 0, and just before that page 3 was used. Thus, the LRU algorithm
replaces page 2, not knowing that page 2 is about to be used. When it then faults for page 2, the
LRU algorithm replaces page 3 since, of the three pages in memory {0, 3, 4}, page 3 is the least
recently used. Despite these problems, LRU replacement with 12 faults is still much better than
FIFO replacement with 15. The LRU policy is often used as a page-replacement algorithm and
is considered to be good. The major problem is how to implement LRU replacement.

An LRU page-replacement algorithm may require substantial hardware
assistance. The problem is to determine an order for the frames defined by
the time of last use. Two implementations are feasible.

184 LOVELY PROFESSIONAL UNIVERSITY