Skip to content
GATETECH
Official PYQ · 2004Q65Memory Hierarchy: Cache, Main Memory and Secondary StorageMCQ1 mark

GATE CS 2004 Q65 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is:

8,12,0,12,88, 12, 0, 12, 8.

Choose one option
View worked solution

Answer: C

To find the number of cache misses, we first determine the cache configuration:

  • Total number of blocks: 44
  • Set associativity: 22-way
  • Number of sets: Sets=Total BlocksAssociativity=42=2\text{Sets} = \frac{\text{Total Blocks}}{\text{Associativity}} = \frac{4}{2} = 2 (Set 0 and Set 1)

A block with address BB maps to set index: Set Index=B(mod2)\text{Set Index} = B \pmod 2

All block addresses in the given sequence (8,12,0,12,88, 12, 0, 12, 8) are even numbers. Therefore, all of them map to Set 0. Since each set can hold at most 22 blocks, the problem simplifies to managing a cache of size 22 using the Least Recently Used (LRU) replacement policy.

Let's trace the state of Set 0 step-by-step (ordered from Most Recently Used (MRU) to Least Recently Used (LRU)):

Step Block Address Set 0 Contents (MRU → LRU) Result
1 88 [8][8] Miss
2 1212 [12,8][12, 8] Miss
3 00 [0,12][0, 12]
(8 is replaced as it is LRU)		 Miss
4 1212 [12,0][12, 0]
(12 becomes MRU)		 Hit
5 88 [8,12][8, 12]
(0 is replaced as it is LRU)		 Miss

Counting the misses from the trace, we get a total of 44 cache misses.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Memory Hierarchy: Cache, Main Memory and Secondary Storage questions