GATE CS 2014 Set 1 Q44 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To find the miss ratio, let us analyze the behavior of the Least-Recently-Used (LRU) replacement policy under the given conditions:

1. Total Accesses and Unique Blocks: The total number of accesses in the sequence is $N$, and there are $n$ unique block addresses.
2. LRU Cache Behavior: Under the LRU policy, a block is evicted from a cache of associativity (or capacity) $A$ only if at least $A$ other unique blocks are accessed after its most recent access.
3. No Capacity/Conflict Misses: We are given that the number of unique block addresses accessed between any two consecutive accesses to the same block is bounded above by $k$. Since the cache associativity is $A \geq k$, the block will never be evicted from the cache before it is accessed again. Thus, every subsequent access to an already-loaded block is guaranteed to be a cache hit.
4. Compulsory Misses: Since no block is ever evicted once loaded, the only misses that occur are the very first accesses to each of the $n$ unique blocks. These are called compulsory (or cold) misses. Therefore, the total number of cache misses is exactly $n$.

The miss ratio is defined as:

Hence, the correct option is A.