Another Simple Policy: Random … Workload Examples

FIFO showed that ignoring history costs hits. Before reaching for history, one more baseline — and then the policy that uses the past properly.

22.4 Another Simple Policy: Random

Pick a victim at random: as simple as FIFO, equally unintelligent, and occasionally lucky:

Figure 22.3, live: Random on the canonical stream — re-roll the dice and watch the hit count wander

Access	Hit/Miss?	Evict	Resulting Cache State
▶ step through the trace, or run it all

How Random does depends entirely on the luck of the draw: some seeds match optimal's 6 hits, some manage 2. Roll a few and watch the same stream produce different fates.

How lucky, on average? Run the experiment ten thousand times:

Figure 22.4, computed: Random's hit count on the stream, over 10,000 seeds

Just over 40% of trials do as well as optimal (6 hits); a thin tail does much worse. No intelligence, no systematic bias — a coin flip with a decent average.

22.5 Using History: LRU

As with scheduling (remember MLFQ), the future is best guessed from the past. Two historical signals offer themselves: frequency — a much-accessed page is probably valuable ( least-frequently-used , LFU, evicts the least) — and recency: a recently-touched page will likely be touched again. Both bets ride on the principle of locality: programs hammer certain code sequences and data structures, so history reveals which pages matter. The recency bet is least-recently-used (LRU) — a name so honest you know the algorithm the moment you hear it:

Figure 22.5, live: LRU on the same stream — history, used well

Access	Hit/Miss?	Evict	Resulting Cache State
▶ step through the trace, or run it all

LRU evicts 2 (pages 0 and 1 were touched more recently), then 0 — and both bets pay off: 6 hits, matching optimal. (The book cheerfully admits the example is cooked. But sometimes cooking is necessary to prove a point.) Note the state column: the LRU→ order reshuffles on every HIT, which is exactly the bookkeeping that will make perfect LRU expensive to implement.

(The opposites — Most-Frequently-Used, Most-Recently-Used — exist, and mostly lose: they ignore the locality most programs exhibit instead of embracing it.)

Aside: Types Of Locality

Spatial : touch page P, and P−1 or P+1 likely follow. Temporal : recently-touched pages get touched again. Hardware cache hierarchies are built on both — but locality is a heuristic about typical programs, not a law all programs obey. Some access streams are simply random, and no history helps. Keep it in mind as a designer; don’t mistake it for a guarantee.

22.6 Workload Examples

Small traces flatter and deceive; run real workloads across every cache size. (These charts are computed in your browser from seeded workloads — the same simulator as the tables above, swept from cache size 1 to 100.)

Figure 22.6, computed live: the no-locality workload (10,000 refs, 100 pages, uniformly random)

computed live: 10,000 refs over 100 pages (no locality), seeded — not a scanned figure

Three lessons. With no locality, the realistic policies collapse onto one line — hit rate is purely cache size. When the cache fits the whole working set (100), everyone converges to ~100%. And OPT floats above throughout: seeing the future beats any amount of cleverness about the past.

Figure 22.7, computed live: the 80-20 workload — 80% of references go to 20% of pages

computed live: 10,000 refs over 100 pages (80/20 hot-cold), seeded — not a scanned figure

Locality separates the field: LRU pulls ahead of FIFO and Random by holding the hot pages, while OPT shows how much room remains. Does LRU's edge matter? It depends on the price of a miss — at 10ms apiece, a few percentage points are a fortune.

Figure 22.8, computed live: the looping-sequential workload — 50 pages, accessed in a cycle

computed live: 10,000 refs over 50 pages (looping sequential), seeded — not a scanned figure

The worst case for LRU and FIFO: both evict the oldest page, which the loop needs NEXT — 0% hits even with a 49-page cache. Random, immune to rhythm, does respectably. Databases know this pattern well, which is why they distrust general-purpose caching (and why "scan resistance" became a modern design goal).

Three workloads, three verdicts: without locality, policy is irrelevant; with hot/cold structure, history (LRU) earns real points; and against a loop one page too big, LRU and FIFO collapse to zero while a coin flip survives. Every policy has a workload that loves it and one that breaks it — which is why the next question is not “which policy is best” but “how do we implement the good ones affordably.”

Check yourself

1.Over 10,000 seeds on the canonical stream, Random matches optimal's 6 hits in roughly 40% of trials — and scores ≤2 in others. What's the takeaway?

2.LRU matches optimal's 6 hits on the example stream. What information is it exploiting, and via which principle?

3.In the no-locality workload, LRU, FIFO, and Random produce IDENTICAL curves. Why does cleverness stop mattering?

4.The 80-20 workload finally separates the field. Who wins among the implementable policies, and does the edge matter?

5.Looping-sequential: 50 pages accessed in a cycle, cache of 49. LRU and FIFO score exactly 0%. Explain the massacre — and the survivor.

5 questions