Approximating LRU

Use bits

As it turns out, the answer is yes: approximating LRU is more feasible from a computational-overhead standpoint, and indeed it is what many modern systems do. The idea requires some hardware support, in the form of a use bit (sometimes called the reference bit), the first of which was implemented in the first system with paging, the Atlas one-level store“One-level Storage System” by T. Kilburn, D.B.G. Edwards, M.J. Lanigan, F.H. Sum- ner. IRE Trans. EC-11:2, 1962. Although Atlas had a use bit, it only had a very small number of pages, and thus the scanning of the use bits in large memories was not a problem the authors solved.. There is one use bit per page of the system, and the use bits live in memory somewhere (they could be in the per-process page tables, for example, or just in an array somewhere). Whenever a page is referenced (i.e., read or written), the use bit is set by hardware to 1. The hardware never clears the bit, though (i.e., sets it to 0); that is the responsibility of the OS.

Clock algorithm

How does the OS employ the use bit to approximate LRU? Well, there could be a lot of ways, but with the clock algorithm“A Paging Experiment with the Multics System” by F.J. Corbato. Included in a Festschrift published in honor of Prof. P.M. Morse. MIT Press, Cambridge, MA, 1969. The original (and hard to find!) reference to the clock algorithm, though not the first usage of a use bit. Thanks to H. Balakrishnan of MIT for digging up this paper for us., one simple approach was suggested. Imagine all the pages of the system arranged in a circular list. A clock hand points to some particular page, to begin with (it doesn’t really matter which). When a replacement must occur, the OS checks if the currently-pointed to page P has a use bit of 1 or 0. If 1, this implies that page P was recently used and thus is not a good candidate for replacement. Thus, the use bit for $P$ set to 0 (cleared), and the clock hand is incremented to the next page $(P + 1)$. The algorithm continues until it finds a use bit that is set to 0, implying this page has not been recently used (or, in the worst case, that all pages have been and that we have now searched through the entire set of pages, clearing all the bits).

Note that this approach is not the only way to employ a use bit to approximate LRU. Indeed, any approach which periodically clears the use bits and then differentiates between which pages have use bits of 1 versus 0 to decide which to replace would be fine. The clock algorithm of Corbato’s was just one early approach that met with some success and had the nice property of not repeatedly scanning through all of the memory looking for an unused page.

The behavior of a clock algorithm variant is shown in the figure below.