LRU page replacement, explained

LRU stands for least recently used. Instead of asking which page arrived first, it asks which page has gone unused for the longest time, and removes that one.

The idea behind it is simple: a page that was used recently is likely to be used again soon, and a page that has not been touched for a while is a good candidate to remove.

How it works

• Read the next page request.
• If the page is already in a frame, it is a hit. Note that it was just used, so it becomes the most recently used page.
• If it is not in memory, it is a page fault. Load it into an empty frame if there is one.
• If every frame is full, remove the page whose last use was the longest time ago and load the new page.

A small example

Request list, with 3 frames:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Result with LRU:

12 page faults

On the same list FIFO had 15 faults. Keeping recently used pages paid off.

What to know about its cost

• It needs to remember when each frame was last used, and update that on every hit.
• It never shows Belady's anomaly. With more frames it can only fault the same or less.
• Real hardware usually uses a cheaper approximation of LRU, because tracking every use exactly is costly.

Where it works well

• Close to the best result on programs that reuse recent pages.
• No Belady's anomaly.

Where it struggles

• Needs extra bookkeeping on every memory access.
• A program that loops over more pages than there are frames can make it perform badly.

Try it yourself

Open the Page Replacement experiment, enter the request list from this post with 3 frames, choose LRU and step through it. Then switch to the other algorithms and compare the page faults.

Open the Page Replacement experiment