Question bank — Replacement policies — LRU, LFU, FIFO, Random

False. With Set-Associative Mapping a block maps to exactly one set; the policy picks a victim only among that set's ways. Direct-mapped is the extreme: one candidate, so no policy is needed.

True. A direct-mapped cache has one way per set, so there is only ever one possible victim. The "policy" has no choice to make, so all four collapse to the same behaviour.

True. LRU resets that block's recency to "most recent" on every touch; FIFO's insertion-order queue is untouched by a hit. This single asymmetry is the whole difference between them.

False. They only agreed on that trace. A policy is defined by its rule for all possible traces; you can always construct a trace where LRU and FIFO diverge (any trace with a hit to a non-newest block).

True. OPT evicts the block whose next use is farthest away, which is provably miss-optimal. It is unimplementable because it needs future knowledge, but it is the yardstick every real policy is measured against — see Belady's Optimal Algorithm.

False. LRU is a stack algorithm: a size-$n$ cache's contents are always a subset of size-$(n+1)$'s, so misses are monotonically non-increasing in size. No trace can make more cache hurt LRU.

False. This is exactly Belady's anomaly — the classic trace 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 misses at 3 frames but 10 at 4. FIFO's queue changes shape with size, breaking the subset property.

False. Because Random ignores all history, an adversary has no lever to pull; there is no input that reliably forces bad evictions. This lack of a worst case is precisely why Random is respected despite zero metadata.

False. This ignores stale popularity: a block accessed 1000× in the distant past keeps a huge count and refuses to leave even after it is dead. Real LFU needs aging (periodic count decay) to fix this pollution.

False. A miss still probes the cache first and fails, then goes to memory — so it pays $T_{hit}+T_{penalty}$. Algebra collapses to $\text{AMAT}=T_{hit}+m{T}_{penalty}$, keeping $T_{hit}$ always. See AMAT and Memory Hierarchy.

False. Tree-PLRU uses only ~$n-1$ bits and tracks an approximate order, so it can occasionally pick a different victim. It is "good enough" and far cheaper than the ${\log }_2(n!)$ bits true LRU needs — see Pseudo-LRU and Tree-PLRU.

False for stack algorithms (LRU/LFU): more size never increases misses. True only for FIFO/non-stack policies, which is the anomaly. Be precise about which policy before answering.

The error is confusing recency with insertion age. LRU evicts the least-recently-used block; a very old block that was just touched is safe. The stated rule is actually FIFO.

FIFO never reorders on a hit — that is its defining property. Promoting on access would turn it into (approximately) LRU. FIFO's queue only changes when a block is inserted or evicted.

Backwards — having no metadata makes it the cheapest to implement (often just a free-running counter or LFSR). Zero bookkeeping is an advantage, not a blocker.

For FIFO, a bigger cache is exactly what can trigger the anomaly, so this can backfire. The real fix is to use a stack algorithm (LRU/LFU), which is anomaly-proof at any size.

LFU is a stack algorithm — a smaller LFU cache's contents remain a subset of the larger one for the same trace. Changing counts don't violate the subset relation; the ordering by frequency is size-independent, just like LRU's ordering by recency.

The policy directly controls the miss rate $m$, and $m{T}_{penalty}$ dominates when $T_{penalty}\gg T_{hit}$. A better policy that lowers $m$ is often the biggest AMAT lever available.

Because OPT requires knowing each block's next use time in the future, which hardware does not have at eviction time. It is a theoretical benchmark, not a buildable policy.

Because the choice of victim decides your future hit rate. Locality means the right victim (unlikely to be reused) preserves data you'll actually need soon; a wrong choice causes thrashing.

Exact LRU must store a full ordering of the ways, costing ${\log }_2(n!)$ bits per set (painful at 16-way). Tree-PLRU approximates it with only ~$n-1$ bits, trading a little accuracy for a lot of area savings.

Temporal locality says recently-used data tends to be reused soon. LRU's proxy — "keep the recently-touched, evict the stale" — is a direct bet on that pattern, which is why it usually beats FIFO.

It needs only one pointer into a queue (cheap), but it ignores usage entirely, so it can evict a hot block just because it entered early — mediocre prediction and vulnerable to Belady's anomaly.

With $T_{hit}=1$ and $T_{penalty}=100$, the term $m\times 100$ dwarfs the constant $1$. So AMAT $\approx m\times 100$, and halving $m$ nearly halves the total — the penalty is the leverage point.

Because a policy only chooses among the ways of one set (Set-Associative Mapping). Two blocks in different sets never compete for eviction, so global "which is oldest" intuition is misleading.

It simply loads the new block into a free slot — no eviction happens because there is room. Policies only differ once every slot in the relevant set is occupied.

For both, the queue/order is effectively unchanged (LRU re-marks it most-recent, which it already was). The policies only visibly diverge when the hit lands on a non-newest block.

No. One way per set means a single forced victim; every policy makes the same "choice", so LRU/LFU/FIFO/Random are indistinguishable there.

The rule is under-specified, so a tie-breaker is needed — commonly evict the least-recently-used among the tied blocks (LFU-with-LRU-tiebreak) or the oldest. Without a stated tie-break, the answer is ambiguous.

After the first (compulsory) miss loads it, every later access is a hit for all policies, because the block is never evicted while it's the only one being used. Miss rate approaches 0 regardless of policy.

Every access is a compulsory miss for all of them, so miss counts are equal. Replacement policy only creates differences when there is reuse to reward or punish.

Standard LFU resets the counter to a fresh value on re-insertion, since the block's metadata left with it. This is actually protective: it prevents an evicted-then-returned block from instantly reclaiming stale high popularity.

No guarantee — Random can, on any single decision, evict the soon-needed block. Its strength is statistical: over many decisions no adversary can force this consistently, so average behaviour stays close to LRU.