We will examine how replacement policies impact miss rate. Assume a following 2-

Question

We will examine how replacement policies impact miss rate. Assume a following 2-way set associative cache.

Consider the following block address sequence: 0, 1, 5, 2, 4, 8, 12, 16, 20, 24, 28 , 0

0 address will fill left side of set0.

1 address will fill left side of set1.

5 address will fill right side of set1.

2 address will fill left side of set2.

a. Assuming an LRU (least recently used) replacement policy, how many hits does this address sequence exhibit?

b. Assuming an MRU (most recently used) replacement policy, how many hits does this address sequence exhibit?

Explanation / Answer

Answer :

Using LRU Method:

The no. of frames used are---->4

The total no of pages------------>12

The page numbers given are as below
0
1
5
2
4
8
12
16
20
24
28
0
frame :
0 -1 -1 -1
frame :
0 1 -1 -1
frame :
0 1 5 -1
frame :
0 1 5 2
frame :
4 1 5 2
frame :
4 8 5 2
frame :
4 8 12 2
frame :
4 8 12 16
frame :
20 8 12 16
frame :
20 24 12 16
frame :
20 24 28 16
frame :
20 24 28 0
Page fault:12

Using MRU Method:

The no. of frames used are---->4

The total no of pages------------>12

The page numbers given are as below:
0
1
5
2
4
8
12
16
20
24
28
0
frame :0 -1 -1 -1
frame :0 1 -1 -1
frame :0 1 5 -1
frame :0 1 5 2
frame :4 1 5 2
frame :4 8 5 2
frame :4 8 12 2
frame :4 8 12 16
frame :20 8 12 16
frame :20 24 12 16
frame :20 24 28 16
frame :20 24 28 0
Page fault:12

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.