LRU Algorithm

LRU is short for least recently used and refers to various algorithms that attempt to find least used pages according to a similar scheme. This reverse approach avoids the need for more complex searching for most used pages.

Clearly, pages frequently used over a short period in the recent past are likely to be used in the (near) future. The LRU algorithm is based on the converse assumption that pages not used recently will not be needed frequently in the immediate future. Such pages are therefore likely candidates for swap-out when memory is scarce.

The fundamental LRU principle may be simple, but it is difficult to implement it appropriately. How can the kernel mark or sort pages as simply as possible in order to estimate access frequency without requiring an inordinate amount of time to organize data structures? The simplest LRU variant uses a (doubly) linked list with all the pages in the system. This list is resorted each time memory is accessed. The page in question is found and moved to the start of the list. In the course of time, this results in a kind of ''equilibrium'' in which frequently used pages are at the beginning of the list and least used pages are right at the end (a similar algorithm is used to manage the buffer caches discussed in Chapter 16).

The algorithm works beautifully but can only be implemented effectively for a small number of elements. This means that it cannot be used in its unadulterated form for memory management as this would be far too costly in terms of system performance. Simpler implementations that consume less CPU time are therefore required.

Special support by the processor makes implementation of the LRU algorithm significantly less costly. Unfortunately, this support is available on few architectures and cannot be used by Linux; after all, memory management should not be tailored to a specific processor type. A counter is then incremented by 1 in each CPU period. After each page access, a further counter field for the page is set to the value of the system counter. The processor itself must perform this action to ensure sufficient speed. If a page fault occurs because a required page is no longer available, the operating system need only compare the counters of all pages to ascertain which page was accessed the longest time ago. This technique still necessitates searching through the list of all memory pages every time a page fault occurs but does not require lengthy list operations after each memory access.

Continue reading here: Page Reclaim and Swapping in the Linux Kernel

Was this article helpful?

0 0