Intuition The one core ideaA cache is a tiny shelf that can hold only a few things, so when it fills up and something new arrives, you must throw one item out. A replacement policy is just a rule for choosing that victim — and the whole topic is comparing four such rules.
Before you can compare LRU, LFU, FIFO, and Random, you must be fluent in the words and symbols the parent note throws at you without pausing . This page builds every one of them from zero. Read top to bottom; each idea uses only the ones above it.
A cache is a small, fast box of memory that sits between the fast processor and the slow main memory. It holds copies of a few blocks of data so they can be fetched quickly instead of going all the way to slow memory.
Picture a desk with only a few slots. The library (main memory) is huge but far away; the desk (cache) is tiny but right in front of you.
The word slot (also called a line , way , or frame ) is one place on the desk that can hold exactly one block. The parent note says "capacity = 3" — that means three slots .
Recall Why a cache exists at allBecause main memory is ~100× slower to reach. Keeping likely-reused data close saves that trip. See Cache Memory Fundamentals and AMAT and Memory Hierarchy .
A block is one chunk of data the cache stores and moves as a unit. In examples we give blocks names — the letters A B C D labels for four different blocks , nothing mathematical.
Definition Access sequenceAn access sequence is the list, in time order, of which block the program asks for next. The parent writes
A , B , C , A , D , B A B B
The picture: a conveyor belt of requests marching at the cache. Each arrival forces the cache to answer "do I have you already, or must I load you?"
A hit = the requested block is already in the cache . Fast, no eviction.
A miss = the requested block is not in the cache . You must load it from slow memory, and if the cache is full, evict someone to make room.
Picture two coloured lamps over the desk: green = hit (item already here), red = miss (fetch trip needed).
Intuition Why we care about thecount of each
Every miss costs a slow trip. The entire point of a replacement policy is to make the future hold more green lamps and fewer red ones . Counting hits and misses is how we grade a policy.
Definition Evict / victimTo evict a block is to remove it from the cache to free a slot. The block chosen for removal is the victim . The replacement policy is exactly the rule that names the victim .
Picture: the desk is full, a new book arrives, your hand hovers over the three books deciding which one to shelve away. That hovering hand is the policy.
Definition Two kinds of locality
Temporal locality : a block used recently is likely to be used again soon .Spatial locality : blocks near a used block are likely to be used soon .
These aren't laws — they are observed tendencies of real programs (loops re-touch the same variables; arrays are walked in order). Prerequisite: Temporal and Spatial Locality .
Intuition Why the topic keeps saying "proxy for the future"We would love to evict the block we won't need for the longest time — but we can't see the future. Locality lets us guess : "recently used ⇒ probably useful again." Each policy is one guess dressed as a rule.
The four policies differ only in which property of a block they measure . Three different rulers:
Ruler
Plain meaning
Picture
Recency how long since this block was last touched
a stopwatch that resets every time you use the block
Frequency how many times this block has been touched ever
a tally counter that only goes up
Age how long since this block was first loaded
a stopwatch that starts on arrival and never resets
Common mistake Confusing recency with ageWhy it feels the same: both sound like "old." Why they differ: touching a block resets its recency stopwatch but not its age stopwatch. Fix: recency = since last use ; age = since first load . This one distinction is the whole gap between LRU and FIFO.
Now the parent's four rules read plainly:
LRU evicts the block with the largest recency (untouched longest).LFU evicts the block with the smallest frequency (touched fewest times).FIFO evicts the block with the largest age (loaded first).Random ignores all rulers and picks uniformly.
The parent writes
AMAT = T hit + m × T penalty
Definition The AMAT symbols
AMAT Average Memory Access Time : the average time one memory request takes.T hit T penalty extra time a miss adds (the slow trip to memory).h hit rate : fraction of requests that hit, a number between 0 1 m miss rate : fraction that miss. Since every request either hits or misses, h + m = 1 m = 1 − h
m 10 100 m = 100 10 = 0.10 h = 0.90 0.05 5%
The parent writes C n ⊆ C n + 1
⊆ X ⊆ Y every element of X Y " — X fits inside Y C n n C n ⊆ C n + 1 everything a smaller cache keeps, the bigger cache also keeps .
Picture two nested boxes: the small cache's contents always sit inside the big cache's contents. When that nesting always holds, adding slots can only help — misses never rise. That is the stack property , and it's why LRU/LFU can't suffer Belady 's anomaly. See Set-Associative Mapping for what a "set" of slots is.
Definition Factorial and log, from zero
n ! n n × ( n − 1 ) × ⋯ × 1 order n ordering of all n n ! log 2 ( k ) k log 2 ( k ) k
Putting them together: storing one of n ! log 2 ( n !) 16 16 ! ≈ 2 × 1 0 13 45 per set — costly. That is why real hardware uses Pseudo-LRU and Tree-PLRU with only ∼ n − 1
Worked example Tiny checkFor n = 4 4 ! = 24 log 2 24 ≈ 4.585 5
Cache = tiny fast box of slots
Block = one data chunk labelled A B C
Access sequence = requests in time order
Full cache forces Eviction of a Victim
Locality = recent stays useful
Which ruler? Recency Frequency Age
The four policies LRU LFU FIFO Random
Count misses gives miss rate m
AMAT formula grades a policy
Subset symbol and stack property
Factorial and log2 = LRU cost
Every arrow says "you need the left idea before the right one makes sense."
Cover the right side and answer each before moving on.
What is a cache slot (line / way / frame)? One place in the cache that holds exactly one block.
What do the letters A , B , C , D Just labels for four distinct data blocks — not numbers.
Difference between a hit and a miss? Hit = block already in cache; miss = not present, must load (and maybe evict).
What is a victim? The block the policy chooses to evict to free a slot.
Recency vs frequency vs age in one line each? Recency = since last use; frequency = total times used; age = since first loaded.
Why is temporal locality the "bet" behind LRU? Recently used blocks are likely used again soon, so keep them.
In AMAT, what are T hit m T penalty Cache-probe time, miss rate (fraction of misses), extra time a miss adds.
Why does h + m = 1 Every request either hits or misses, so the two fractions cover everything.
What does C n ⊆ C n + 1 Smaller cache's blocks are all in the bigger cache — the stack property banning Belady's anomaly.
Why does exact LRU need log 2 ( n !) It must remember the full recency ordering of n n !
