Lesson 5 · Memory management

LRU Page Replacement: Recency as a Proxy

Evict the page unused for the longest. Betting that the recent past predicts the near future is the closest any implementable policy gets to optimal.

What the LRU Page Replacement Algorithm Is

The LRU page replacement algorithm — least recently used — evicts the resident page that has gone unreferenced for the longest time. Where OPT looks forward and FIFO looks at arrival order, LRU page replacement looks backward at actual use.

Track, for every resident page, the time of its most recent reference.
On a hit, update that page's timestamp to now the hit is not free, it is the bookkeeping.
On a fault with a free frame, load the page and stamp it with the current time.
On a fault with no free frame, find the resident page with the oldest timestamp and evict it.
Load the faulting page into the freed frame and stamp it as most recently used.

The justification is temporal locality: a page touched recently is likely to be touched again soon, and one untouched for a long stretch probably belongs to a phase the program has left. Real programs — loops, working sets, call stacks — exhibit this strongly enough that LRU lands close to optimal on most workloads.

Read another way, LRU is OPT with the time axis reversed. OPT evicts the page whose next use is furthest ahead; LRU evicts the page whose last use is furthest behind. It uses the observed past as an estimate of the unobservable future, which is the only move available to an implementable algorithm.

Unlike FIFO, every hit updates the ordering. Referencing a resident page makes it the most recently used and moves it to the back of the eviction queue — which is exactly the information FIFO discards.

Decision rule: evict the page with the oldest last-use time
Every reference, hit or fault, updates the ordering
Bets on temporal locality holding
A stack algorithm — more frames never means more faults

LRU Page Replacement Algorithm Example

This lru page replacement algorithm example runs 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 through three frames. At each fault, the victim is whichever resident page was referenced longest ago.

The first three references fault into empty frames: [7, 0, 1], last used at times 1, 2, 3 respectively.

Reference 2 — fault. Last-use times are 7→1, 0→2, 1→3. The oldest is 7, evicted. Frames [2, 0, 1]. Reference 0 — hit, and 0's timestamp refreshes to now. This is the step FIFO ignores and LRU records.

Reference 3 — fault. Last-use: 2→4, 0→5, 1→3. The oldest is 1, so LRU evicts 1 and keeps 0. FIFO evicted 0 here and immediately faulted on it; LRU's extra bookkeeping buys that fault back.

Reference 0 — hit, because LRU kept it. The run continues: 4 evicts 2, 2 evicts 3, 3 evicts 0, 0 evicts 4, and the final references 3 and 2 are hits.

Total: 9 faults, 4 hits. FIFO takes 10 and OPT takes 7. LRU recovers one of the three faults separating FIFO from perfect information.

LRU on 7,0,1,2,0,3,0,4,2,3,0,3,2 with 3 frames — victim chosen by oldest last use
Ref	Frames after	Event	Why this victim
7	7 – –	fault	empty frame
0	7 0 –	fault	empty frame
1	7 0 1	fault	empty frame
2	2 0 1	evict 7	unused since ref 1 — the oldest
0	2 0 1	hit	0 becomes most recently used
3	2 0 3	evict 1	1 unused since ref 3; 0 was just used
0	2 0 3	hit	kept because LRU spared it — FIFO faults here
4	4 0 3	evict 2	2 unused since ref 4
2	4 0 2	evict 3	3 unused since ref 6
3	4 3 2	evict 0	0 unused since ref 7
0	0 3 2	evict 4	4 unused since ref 8
3	0 3 2	hit	—
2	0 3 2	hit	—
Total	—	9 faults	FIFO 10 · OPT 7

9 faults, 4 hits — one better than FIFO, two off the OPT floor
The decisive step is reference 5: LRU evicts 1, FIFO evicts 0
Every hit reorders the recency list
Same eviction as OPT on four of the six decisions

Key reference

Terms, operations, and practical uses

The rule

DecisionEvict the page whose last reference is furthest in the past.
BetTemporal locality — recently used pages get used again.
Hits matterEvery reference updates the recency ordering.
Mirror of OPTOPT reads forward; LRU reads the same axis backward.

Implementing it

CountersTimestamp per page-table entry; O(frames) scan for the victim.
StackDoubly linked list; O(1) victim, but heavy pointer traffic.
The blockerBoth pay on every memory access, not just on faults.
ApproximationClock gets nearly the same result using one free hardware bit.

Where it breaks

9 faultsOn the standard string — one better than FIFO, two off OPT.
Sequential scanA large one-pass read evicts the real working set.
Cyclic accessA loop just larger than memory faults on every reference.
Real fixesLinux active/inactive lists; LRU-K and ARC track more history.

Implementation

LRU on the standard reference string

from collections import OrderedDict


def lru(refs, frames):
    """LRU page replacement. Returns (faults, hits).

    An OrderedDict gives O(1) reordering: move_to_end on a hit, popitem(last=False)
    to drop the least recently used page. That is the stack method, and the cost
    it hides is that the reorder happens on every single reference.
    """
    resident = OrderedDict()
    faults = hits = 0

    for page in refs:
        if page in resident:
            hits += 1
            resident.move_to_end(page)  # the bookkeeping FIFO refuses to do
            continue

        faults += 1
        if len(resident) == frames:
            resident.popitem(last=False)  # least recently used

        resident[page] = True

    return faults, hits


refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print(lru(refs, 3))  # (9, 4)

#include <iostream>
#include <list>
#include <unordered_map>
#include <vector>
// LRU page replacement using the stack method: a list in recency order plus a
// map from page to its list position, so both the hit and the eviction are O(1).
int lru(const std::vector<int>& refs, int frames, int& hits) {
    std::list<int> recency; // front = most recent, back = least recent
    std::unordered_map<int, std::list<int>::iterator> where;
    int faults = 0;
    hits = 0;
    for (int page : refs) {
        auto found = where.find(page);
        if (found != where.end()) {
            ++hits;
            recency.splice(recency.begin(), recency, found->second);
            continue;
        }
        ++faults;
        if (static_cast<int>(recency.size()) == frames) {
            where.erase(recency.back());
            recency.pop_back();
        }
        recency.push_front(page);
        where[page] = recency.begin();
    }
    return faults;
}
int main() {
    std::vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
    int hits = 0;
    std::cout << lru(refs, 3, hits) << " faults, " << hits << " hits\n";
    return 0;
}

import java.util.LinkedHashMap;
import java.util.Map;
public class LruPageReplacement {
    /**
    * LRU page replacement. A LinkedHashMap in access order is the stack method:
    * the eldest entry is always the least recently used page.
    */
    static int[] lru(int[] refs, int frames) {
        // Access order (the third constructor argument) makes get() move a key
        // to the most-recent end, so the eldest key is the LRU victim.
        Map<Integer, Boolean> resident = new LinkedHashMap<>(frames, 0.75f, true);
        int faults = 0;
        int hits = 0;
        for (int page : refs) {
            if (resident.get(page) != null) {   // get(), not containsKey(): it reorders
                hits++;
                continue;
            }
            faults++;
            if (resident.size() == frames) {
                int eldest = resident.keySet().iterator().next();
                resident.remove(eldest);
            }
            resident.put(page, Boolean.TRUE);
        }
        return new int[] {faults, hits};
    }
    public static void main(String[] args) {
        int[] refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
        int[] result = lru(refs, 3);
        System.out.println(result[0] + " faults, " + result[1] + " hits");
    }
}

Watch it run

Step through it

Running on refs 7,0,1,2,0,3,0,4,2,3,0,3,2 · 3 frames

Output

Implementing LRU: Counters and Stacks

There are two textbook implementations, and the reason real hardware ships neither is the same in both cases: the cost falls on every memory access, not just on faults.

Counter method. The CPU keeps a logical clock incremented on every reference, and each page-table entry stores the clock value at its last use. Choosing a victim means scanning every entry for the minimum. The write happens on every access, and the scan is linear in the number of frames.

Stack method. Keep page numbers in a doubly linked list; on every reference, unlink the page and move it to the top. The least recently used page is always at the bottom, so the victim is found in constant time — but each reference costs up to six pointer updates.

Both are fatal in hardware. A memory access takes on the order of 100 nanoseconds; adding a timestamp write or six pointer updates to every load and store would cost more than the page faults it prevents. The bookkeeping has to happen at reference time, and reference time is where there is no budget.

So real systems approximate. Clock uses a single hardware reference bit the MMU sets for free, and gets within a fault or two of exact LRU — on the string above it matches LRU exactly at 9 faults.

The two exact implementations and what each costs
Method	Cost per reference	Cost per fault	Verdict
Counters	One timestamp write	O(frames) scan for the minimum	Write on every access is too costly
Stack (linked list)	Up to six pointer updates	O(1) — victim is at the bottom	Pointer churn on every access is too costly
Clock	Nothing — the MMU sets the bit	O(frames) sweep, usually far less	What real kernels actually use

Counter method: timestamp per entry, linear scan to find the victim
Stack method: O(1) victim, but heavy pointer traffic per reference
The cost lands on every access, which is why neither ships
Approximations get most of the benefit for almost none of the cost

Where LRU Breaks Down

LRU's bet fails whenever recency stops predicting reuse, and the classic case is a sequential scan larger than memory. Reading a huge file touches each block once; every block looks freshly used, so LRU evicts the genuinely hot working set to make room for data it will never read again. A single grep over a large file can flush a database's cache this way.

The other standard failure is cyclic access with a loop slightly larger than memory. Pages 1 to 5 referenced repeatedly in four frames means the page needed next is always the one just evicted, and LRU takes a fault on every single reference — the worst possible outcome, where FIFO would do no better but random replacement would do considerably better.

Real kernels patch this rather than abandoning LRU. Linux keeps two lists, active and inactive: a newly read page enters the inactive list and is only promoted to active on a second reference. A one-pass scan therefore cycles through the inactive list without ever displacing the active working set. Database buffer pools use LRU-K or ARC for the same reason, tracking the last K references instead of just the last one so a single touch cannot mark a page hot.

A large sequential scan evicts the working set — the classic pathology
Cyclic access just over memory size can fault on every reference
Linux's active/inactive lists require two references before promotion
LRU-K and ARC track more history to resist one-off touches