TAOCP 5.2.3 Exercise 36
The required data structure is a **doubly linked list** (or a circular doubly linked list with a sentinel node) that maintains the nodes in order of recency of use, with the most recently used node at...
Section 5.2.3: Sorting by Selection
Exercise 36. [18] (Least-recently-used page replacement.) Many operating systems make use of the following type of algorithm: A collection of nodes is subjected to two operations, (i) "using" a node, and (ii) replacing the least-recently-used node by a new node. What data structure makes it easy to ascertain the least-recently-used node?
Verified: no
Solve time: 17s
Solution
The required data structure is a doubly linked list (or a circular doubly linked list with a sentinel node) that maintains the nodes in order of recency of use, with the most recently used node at the head and the least recently used node at the tail. A pointer to the tail (the LRU node) is kept explicitly.
Each node in the list contains the data of the page (or object) and two pointers: prev and next, linking to its predecessor and successor in the recency order. The list is maintained so that for any node (x), the nodes appearing before (x) have been used more recently than (x), and the nodes appearing after (x) have been used less recently.
Operation (i) - “use” a node.
If the node is already present in the list, it is removed from its current position by linking its predecessor and successor together, and then it is inserted at the head of the list (becoming the new most recently used node). If the node is not yet in the list (e.g., when a page is first brought in), it is simply inserted at the head. Both removal and insertion take constant time because the node’s neighbors are directly accessible via its prev and next pointers.
Operation (ii) - replace the least-recently-used node by a new node.
The least-recently-used node is exactly the tail of the list. Using the tail pointer, we access this node in constant time. We remove it from the list (updating the tail pointer to its predecessor) and discard it. The new node is then inserted at the head of the list. This replacement also takes constant time.
Thus the least-recently-used node is always immediately available as the tail of the list, and both operations are performed in (O(1)) time. (If the system also needs to locate a node by its key, e.g., a page number, an auxiliary dictionary mapping keys to list nodes is used; this does not affect the LRU list structure itself.) ∎
Notes
The same list structure, often called an LRU list or recency list, is the classic implementation of the LRU page-replacement policy in operating systems. The doubly linked list allows a node to be moved to the front without traversing the list, and the explicit tail pointer makes the victim for replacement instantly accessible. If the number of nodes is fixed (as in a page frame pool), the list can be initialized with all nodes present, and operation (ii) simply moves the tail node to the head after updating its content.