Core · Operating systemsLesson 4 of 6Free to read

Page replacement and LRU · Operating Systems

When memory is full, which page should go?

Why you need it

RAM holds only so many pages, and every miss means a slow trip to disk. The choice of which page to evict decides how often that happens. The same question appears in every cache: CPU caches, browser caches, Redis, CDNs. LRU is the answer you'll implement again and again.

The intuition

With 3 frames and the page requests 1 2 3 1 4 1 2:

FIFO evicts the page that arrived first, even if it's used all the time.
LRU (least recently used) evicts the page untouched for the longest. Recent use predicts future use, so LRU usually misses less.

Count page faults (misses) to compare policies. In Python, collections.OrderedDict makes LRU easy: move_to_end(key) on every use, popitem(last=False) to evict the oldest.

Definition

LRU

Least recently used: evict the item whose last use is oldest.

Hit rate

The share of requests answered from the cache. 1 − hit rate is the miss rate; every miss costs a slow fetch.

Examples

FIFO versus LRU

Try it yourself

Same requests, same 3 frames, two policies.

from collections import OrderedDict, deque

def fifo(requests, frames):
    mem, order, faults = set(), deque(), 0
    for p in requests:
        if p not in mem:
            faults += 1
            if len(mem) == frames:
                mem.discard(order.popleft())
            mem.add(p)
            order.append(p)
    return faults

def lru(requests, frames):
    mem, faults = OrderedDict(), 0
    for p in requests:
        if p in mem:
            mem.move_to_end(p)
        else:
            faults += 1
            if len(mem) == frames:
                mem.popitem(last=False)
            mem[p] = True
    return faults

reqs = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2]
print(fifo(reqs, 3), lru(reqs, 3))

Step by step

L9FIFO throws out the oldest arrival, even page 1 which is hot.
L18LRU refreshes a page every time it's used.
L22Evict the least recently used.
L27LRU misses less on this pattern.8 6

Common mistakes

Bigger cache, always fewer misses?

For FIFO, no: with some request patterns, adding a frame increases faults (Bélády's anomaly). LRU doesn't have this problem.

Forgetting to refresh on a hit

An LRU that only records insert time is FIFO in disguise. Every use must move the item to the front.

Quick quiz

1. Frames hold pages 1, 2, 3; page 1 was used most recently, page 2 least recently. Page 4 is requested. LRU evicts…

APage 2
BPage 1
CPage 3

Show the answer

Answer: A

The least recently used one.

2. What does this print?

from collections import OrderedDict
cache = OrderedDict()
for key in ["a", "b", "c", "a", "d"]:
    if key in cache:
        cache.move_to_end(key)
    else:
        if len(cache) == 3:
            cache.popitem(last=False)
        cache[key] = True
print(list(cache))

A
```
['c', 'a', 'd']
```
B
```
['b', 'c', 'd']
```
C
```
['a', 'b', 'd']
```

Show the answer

Answer: A

Using a refreshes it, so b is the oldest when d arrives.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictCount FIFO faults
Type exactly what this program prints.
ModifyTurn FIFO into LRU
LRUCache is supposed to evict the least recently used key, but get doesn't refresh a key, so it behaves like FIFO. Fix get (and put for existing keys) so every use moves the key to the end.
WriteCount LRU faults
Write lru_faults(requests, frames) that returns how many page faults LRU has for the request list with the given number of frames. Use a list or an OrderedDict.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Cache	缓存	A small fast store holding copies of data that is slow to fetch.
LRU	最近最少使用	Evict the item not used for the longest time.
Hit rate	命中率	The share of requests served from the cache.