16 block => $2^{4}$ = 4 bits are used for the index
block size = 16 bytes => 4 bits are used for the byte offset
Memory address size = 5*4 = 20 bits
No. of Tag bits= 20-4-4 = 12 bits
Lets understand with example-
Ox80010 => $\overset{Tag}{1000 0000 0000}$ $\overset{Index}{0001}$ $\overset{Offset}{0000}$
Now consider access sequence from the question-
Ox80000, Ox80008, Ox80010, Ox80018, Ox30010
First Pass-
First Ox80000 will come and will go in index 0 with tag 800 (Compulsory Miss)
Second Ox80008 will come and will be a hit because at index 0 already 800 is present (Hit)
Third Ox80010 will come and will go in index 1 with tag 800 (Compulsory Miss)
Fourth Ox80018 will come and will be a hit. (Hit)
Fifth Ox30010 will come and will go to index 1 but at index 1 already 800 is present so 300 will replace 800 and it will be a compulsory miss because 300 is coming as first time.(Compulsory Miss)
--------------------------------------------------------------------------
Second Pass-
Ox80000 (Hit)
Ox80008 (Hit)
Ox80010, Now 800 will go to index 1 but at index 1 already 300 is present so 800 will replace 300 but 800 is not coming first time, it already came in first pass so now this will be a conflict miss (Conflict miss)
Ox80018(Hit)
Ox30010 (Conflict miss)
At the end of Second pass table will look like below. And this will now go same for further passes.
Index |
Tag |
|
0 |
800 |
Compulsory Miss |
1 |
800 300 800 300 |
Compulsory Miss , Compulsory Miss, Conflict Miss, Conflict Miss |
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
10 |
|
|
11 |
|
|
12 |
|
|
13 |
|
|
14 |
|
|
15 |
|
|
Total Misses-
Compulsory Misses- 3 (In First Pass)
Conflict Misses - 9*2 =18 (In Further 9 Passes)