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. 6
• B. 4
• C. 7
• D. 5

Answer 1

The correct option is D 5

Fully associate cache with 8 block i.e. 1 set with 8 cache blocks.

Set

4

3

25

8

19

6

25

16

$B_0$ $B_1$ $B_2$ $B_3$ $B_4$ $B_5$ $B_6$ $B_7$

Since set contain 8 blocks so, request for 45 replacement is needed. When 45 comes then

${}^{45}$4

3

25

8

19

6

25

16

$B_0$ $B_1$ $B_2$ $B_3$ $B_4$ $B_5$ $B_6$ $B_7$

For request 22 :

45

${}^{22}$3

25

8

19

6

25

16

$B_0$ $B_1$ $B_2$ $B_3$ $B_4$ $B_5$ $B_6$ $B_7$

For request 8. Since already present, so no replacement.

For request 3:

45

22

25

8

${}^3$19

6

25

16

$B_0$ $B_1$ $B_2$ $B_3$ $B_4$ $B_5$ $B_6$ $B_7$

For request 16: since already present, so no replacement.
For request 25; since already present, so no replacement.
For request 7:

4

3

25

8

19

${}^7$6

25

16

$B_0$ $B_1$ $B_2$ $B_3$ $B_4$ $B_5$ $B_6$ $B_7$

So block 5 i.e. $B_5$ contain memory block 7.