Question 54

1. The access sequence has total length $N$ and contains $n$ unique block addresses.

2. Every block address must be brought into the cache on its very first access. These initial accesses are compulsory (cold) misses. Since there are $n$ distinct block addresses, there are exactly $n$ compulsory misses.

3. Now consider any re-access to an already-accessed block address $B$:

   • The problem states that the number of unique block addresses accessed between two consecutive accesses to $B$ is at most $k$.
   • Under the Least-Recently-Used (LRU) policy, a block is only evicted if at least $A$ other unique blocks are accessed after it, where $A$ is the associativity.
   • Since $A \ge k$, the number of intervening distinct blocks is strictly less than or equal to the cache associativity, so block $B$ can never be evicted before its subsequent access.
   • Therefore, every subsequent access to any block is guaranteed to be a cache HIT.

4. Consequently, no capacity or conflict misses can occur. The total number of misses across all $N$ accesses is exactly $n$.

5. The miss ratio is:

   $$\text{Miss Ratio} = \frac{\text{Total Misses}}{\text{Total Accesses}} = \frac{n}{N}$$

This matches option A.