GATE IT 2004 | Question: 48

Question

Consider a fully associative cache with $8$ cache blocks (numbered $0-7$) and the following sequence of memory block requests:

$4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7$
If LRU replacement policy is used, which cache block will have memory block $7$?

• A. $4$
• B. $5$
• C. $6$
• D. $7$

Comments

Is your definition of compulsory miss correct?

---

  Source: "Computer Organization and Design book by D. A. Patterson and J. L. Hennessy 5th Edn"

 

---

@Tuhin Dutta thanks for the new technique, its effective for LRU, saves space and revising is also easy.

 

Answer 1

When $45$ comes, the cache contents are:
$4$ $3$ $25$ $8$ $19$ $6$ $16$ $35$

LRU array (first element being least recently used)

$[4$ $3$ $19$ $6$ $25$ $8$ $16$ $35]$.  

So, $45$ replaces $4$.

4$5$ $3$ $25$ $8$ $19$ $6$ $16$ $35$ $[3$ $19$ $6$ $25$ $8$ $16$ $35$ $45]$

Similarly, $22$ replaces $3$ to give:

$45$ $22$ $25$ $8$ $19$ $6$ $16$ $35$ $[19$ $6$ $25$ $8$ $16$ $35$ $45$ $22]$

$8$ hits in cache.

$45$ $22$ $25$ $8$ $19$ $6$ $16$ $35$ $[19$ $6$ $25$ $16$ $35$ $45$ $22$ $8$]

$3$ replaces $19$

$45$ $22$ $25$ $8$ $3$ $6$ $16$ $35$ $[6$ $25$ $16$ $35$ $45$ $22$ $8$ $3]$

$16$ and $25$ hits in cache.

$45$ $22$ $25$ $8$ $3$ $6$ $16$ $35$ $[6$ $35$ $45$ $22$ $8$ $3$ $16$ $25]$

Finally, $7$ replaces $6$, which is in block $5$.

So, answer is (B).

Comments

@srestha m blocks and m-way set associativity. So, the number of sets = 1. So, we always divide by the number of sets.

---

Is it right that "mod method works only in direct and set associative manner " ??

---

@Asim Siddiqui 4 ...yes

simply remember whenever fully associativity mapping apply direct algorithm.......like what we do in OS .

Frame size = no. of cache blocks

Answer 2

Although many people have given correct answer but mentioning another approach to reduce error probability.

In the following image X axis is representing cache block and Y axis is representing Time. 

So answer is Option (B)

Comments

Perfect Method. Thank You!

Answer 3

Ans: B