in CO and Architecture edited by
11,790 views
32 votes
32 votes

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$?

  1. $4$
  2. $5$
  3. $6$
  4. $7$
in CO and Architecture edited by
11.8k views

4 Comments

Is your definition of compulsory miss correct?
0
0
edited by

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

 

5
5

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

 

0
0

3 Answers

34 votes
34 votes
Best answer

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).

edited by
by

4 Comments

@srestha m blocks and m-way set associativity. So, the number of sets = 1. So, we always divide by the number of sets.
8
8
Is it right that "mod method works only in direct and set associative manner " ??
0
0
edited by

@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

0
0
16 votes
16 votes

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)

1 comment

Perfect Method. Thank You!
3
3
1 vote
1 vote

Ans: B

Answer:

Related questions