CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 4 of 7 · 3 min read

OPT and LRU

In plain words: Suppose the kernel could see the future. Then the best victim would be the page whose next use is farthest away, or that is never used again. This is the optimal rule (OPT), also called MIN. It gives the lowest possible number of faults for any string. It cannot be built, because the kernel does not know the future, and its use is as a yardstick: an algorithm that comes close to OPT is good.

On S with 3 frames, OPT faults on the first three pages. On the reference to 6 (the fifth), the frames hold 5, 2 and 4. The next use of 4 is at position 6, of 5 at position 8 and of 2 at position 15, so 2 is the farthest and leaves. The table shows the frames sorted by page number, and a star marks a fault:

Ref OPT frames
5 5 *
2 2 5 *
4 2 4 5 *
5 2 4 5
6 4 5 6 * (2 leaves)
4 4 5 6
6 4 5 6
5 4 5 6
3 3 4 6 * (5 leaves, never used again)
6 3 4 6
4 3 4 6
6 3 4 6
1 1 3 6 * (4 leaves, never used again)
1 1 3 6
2 2 3 6 * (1 leaves, never used again)
3 2 3 6
6 2 3 6
2 2 3 6

OPT causes 7 faults. At the fifth reference, 2 is removed because its next use (the 15th reference) is the farthest of the three.

Since the future is unknown, the practical rule uses the past as a guide. Least recently used (LRU) removes the page that has gone unused for the longest time. The reasoning is that a page used a short time ago is likely to be used again soon, because of locality (page 5). LRU is the mirror image of OPT: OPT looks forward for the farthest use, and LRU looks backward for the oldest use.

Ref LRU frames, least recently used first
5 5 *
2 5 2 *
4 5 2 4 *
5 2 4 5
6 4 5 6 * (2 leaves)
4 5 6 4
6 5 4 6
5 4 6 5
3 6 5 3 * (4 leaves)
6 5 3 6
4 3 6 4 * (5 leaves)
6 3 4 6
1 4 6 1 * (3 leaves)
1 4 6 1
2 6 1 2 * (4 leaves)
3 1 2 3 * (6 leaves)
6 2 3 6 * (1 leaves)
2 3 6 2

LRU causes 10 faults, between OPT (7) and FIFO (12). The cost of true LRU is high: the order of use must be updated on every memory access, which the hardware does not do for free. A counter or a list updated by the kernel on each access would slow every instruction. Real systems therefore use cheaper ways to approximate LRU (section 4).

Least recently used

Least recently used (LRU) is the replacement rule that removes the page whose last use lies farthest in the past, on the guess that pages unused for a long time will stay unused.

Example: with frames holding pages 5, 3 and 6 where 6 was used last and 5 before it, a fault removes 3 if 3 was used longest ago.

Common mistake

LRU is not always better than FIFO. On string S, LRU wins with 3 frames (10 against 12), and FIFO wins with 4 frames (7 against 8). LRU is only a good guess when recent use predicts the next use, as it does for most programs.

Check yourself: 1. Why can OPT not be built, and what is it used for? 2. Which page does LRU remove from the frames 4 6 5 (least recent first) when a new page arrives? 3. Why is exact LRU expensive?