Project ForgeAn access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A ≥ k exercising least-recently-used replacement policy?
- n/N
- B1/N
- C1/A
- Dk/n
Explanation
Since associativity A is at least as large as the maximum reuse distance k, LRU never evicts a block before it's reused — so every access to a block that was already seen is guaranteed to be a HIT. Misses occur only on the very first access to each of the n unique addresses. Miss ratio = n/N.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.