Computer system uses fully associative cache that contains cache lines.
Duration: 11 min
Q. A computer system uses a fully associative cache that contains 40 cache lines.
The cache employs the ,Optimal replacement policy, and the cache is initially empty.
A program generates the following sequence of page references:
1,2,3,…,200, 1,2,3,…,200, 1,2,3,…,200,
That is, the sequence of page references from 1 to 200 repeats three times in total.
Which of the following statements are true?
- A.
Total number of compulsory misses per pass = 200
- B.
Total number of misses after 3 passes = 520
- C.
Total number of conflict misses = 23
- D.
All misses are capacity misses, since the cache is fully associative.
Attempted by 25 students.
Show answer & explanation
Correct answer: B
Answer: Total number of misses after 3 passes = 520
Key ideas:
There are 200 distinct pages referenced (1 through 200).
First pass: the cache starts empty, so every reference to a new page misses. That yields 200 misses in pass 1 (these are the compulsory misses).
Subsequent passes: with an optimal replacement policy and a fully associative cache of size 40, at most 40 pages can be kept so that they hit in the next pass. Therefore each later pass must miss for the remaining pages, i.e. 200 - 40 = 160 misses per pass.
Total after 3 passes: 200 (first pass) + 2 * 160 (two later passes) = 200 + 320 = 520.
Additional notes:
Total compulsory misses over the whole execution = 200 (only the first reference to each distinct page).
Conflict misses = 0 because the cache is fully associative (no mapping conflicts).
Capacity (replacement) misses = total misses - compulsory misses = 520 - 200 = 320 (these are the misses on the later passes).
A video solution is available for this question — log in and enroll to watch it.