Cache misses come in three kinds, the 3C model. A compulsory miss is the first ever reference to a block, so no policy can avoid it. A conflict miss happens when two blocks fight over the same line or the same set while other lines sit unused. A capacity miss happens when the working set is simply larger than the cache, and no amount of remapping helps.
Replacement policy decides only which resident block leaves. It moves conflict and capacity misses around and never removes a compulsory one. LRU evicts the block unused for longest, and Optimal evicts the block whose next use is furthest ahead. Almost every trace question below reduces to three steps: count the sets, compute block address mod sets, then update the recency order inside that one set. Write the set index and the LRU order down before you check an answer.
Cache miss types MCQs: compulsory, conflict, and capacity
Diagnose in that order. Ask first whether the block has ever been referenced, then whether a free line existed elsewhere at the moment of eviction, and only then blame capacity. Getting the order wrong is what turns a conflict miss into a wrong answer.
Distinguish cache misses from page faults using the Virtual Memory and Demand Paging MCQs.
Question 1
Conflict miss occurs in:
A. K way mapping
B. Direct mapping
C. both
D. none of the above
Answer: C, both. Direct mapping allows one line; K-way mapping allows one set. Both permit collisions. Fully associative placement removes that restriction, so the miss is not conflict.
Cache Replacement Policies & Miss Types PYQ hub
Question 2
Which of the following misses can be reduced without changing the cache size? i. Conflict miss ii. Capacity miss iii. Compulsory miss
A. i and ii
B. i and iii
C. i, ii and iii
D. none of the above
Answer: B, i and iii. Associativity reduces conflict without adding capacity. Larger blocks can reduce compulsory misses in sequential access through spatial locality. Remapping cannot fix a working set larger than the cache, so capacity remains.
Question 3
Consider the following statements about the limitations of a direct-mapped cache. Which of the following statements are correct?
A. Conflict misses are increased
B. Compulsory misses are increased
C. Thrashing may occur
D. Capacity misses are eliminated
Answer: A and C. Blocks mapped to one line can evict each other while other lines sit unused, causing conflict thrashing. Mapping neither changes a first reference nor eliminates an oversized working set.
Question 4
Which of the following is/are correct:
A. Increase in block size can reduce Compulsory miss.
B. Increasing disc size can reduce Conflict miss.
C. Increasing set lines can reduce Capacity miss
D. Reducing block size can impact spatial locality
Answer: A and D. Larger blocks fetch neighbouring words on first fill; smaller blocks reduce that spatial coverage. Disc size is not cache placement, and more ways primarily reduce conflict, not capacity, misses.
Cache miss-rate and locality MCQs with actual counts
Use elements per block = block words / words per element, count blocks, and divide misses by accesses.
Question 5
Consider an array A[120] and each element occupies 2-words. A 256-word cache is used and divided into 16-word blocks. What is the miss rate in % for the following code segment: for(int i=0; i<120; i++) A[i] = A[i]*6;
A. 5
B. 6
C. 6.25
D. 7.5
Answer: C, 6.25. A block holds 16 / 2 = 8 elements, giving 120 / 8 = 15 fills. Each iteration reads A[i] and writes it back, so 120 reads + 120 writes = 240 accesses, and every store hits the block its own load has just brought in. Therefore 15 / 240 × 100 = 6.25%.
Question 6
Which of the following statements is/are true:
A. Cache replacements (LRU, MRU, FIFO, etc. ) policy are used to improve Temporal locality of cache.
B. Cache replacements (LRU, MRU, FIFO, etc. ) policy are used to improve Spatial locality of cache.
C. While accessing a large array, a cache with improved spatial locality will perform better as compared to improved temporal locality
D. While executing a loop, a cache with improved spatial locality will perform better as compared to improved temporal locality
Answer: A and C. Replacement retains blocks for likely reuse, acting on temporal locality. Sequential arrays benefit from neighbouring words in a block; loops depend on repeated instructions and data. Thus B and D do not follow.
LRU replacement MCQs in 2-way set-associative caches
Compute set = block address mod sets; update each set's LRU order on hits and fills.
Question 7
Consider a small 2-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently (LRU) scheme. The number of cache misses for the following sequence of block addresses is 8, 12, 0, 12, 8
A. 2
B. 3
C. 4
D. 5
Answer: C, 4. Four blocks at two ways give two sets; every address maps to set 0. Trace 8 M, 12 M, 0 M evicting 8, 12 H refreshing 12, then 8 M evicting 0: four misses.
Question 8
Consider a 2-way set associative cache memory with 4 sets and total 8 cache blocks (0-7) and a main memory with 128 blocks (0-127). What memory blocks will be present in the cache after the following sequence of memory block references if LRU policy is used for cache block replacement. Assuming that initially the cache did not have any memory block from the current job? 0 5 3 9 7 0 16 55
A. 0 3 5 7 16 55
B. 0 3 5 7 9 16 55
C. 0 5 7 9 16 55
D. 3 5 7 9 16 55
Answer: C, 0 5 7 9 16 55. Set 0 receives 0, a hit on 0, then 16, ending {0,16}; set 1 ends {5,9}. In set 3, 55 evicts 3 from {3,7}, leaving {7,55}. The sorted union is 0, 5, 7, 9, 16, 55.
GATE 2005 2-way cache question
Direct-mapped cache MCQ: compute the final eight lines
Use index = block mod 8; each request overwrites its line.
Question 9
Consider a Direct Mapped Cache with 8 cache blocks (numbered 0-7). If the memory block requests are in the following order 3, 5, 2, 8, 0, 63, 9,16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82,17, 24. Which of the following memory blocks will not be in the cache at the end of the sequence ?
A. 3
B. 18
C. 20
D. 30
Answer: B, 18. Applying the overwrite rule gives this final cache:
Cache index | Final memory block |
|---|---|
0 | 24 |
1 | 17 |
2 | 82 |
3 | 3 |
4 | 20 |
5 | 5 |
6 | 30 |
7 | 63 |
At index 2, block 2 and then 82 replace 18. Blocks 3, 20, and 30 remain.
GATE 2007 direct-mapped cache question
Fully associative cache MCQs: LRU line identity and Optimal misses
Fully associative placement removes conflict misses, but replacements retain physical line identity.
Question 10
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. 4
B. 5
C. 6
D. 7
Answer: B, cache block 5. Initially, line 0=4, 1=3, 2=25, 3=8, 4=19, 5=6, 6=16, 7=35. Then 45 replaces line 0, 22 line 1, and 3 line 4. Hits on 8, 16, and 25 leave block 6 least recent, so 7 enters physical line 5.
GATE 2004 fully associative LRU question
Question 11
A computer system uses a fully associative cache that contains 40 cache lines.
The cache employs the Optimal replacement policy and 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.
Answer: B, Total number of misses after 3 passes = 520. Pass 1 gives 200 first-time misses. Optimal keeps the 40 blocks whose next use comes soonest, so each later pass hits 40 times and misses 200 - 40 = 160 times: 200 + 160 + 160 = 520. A compulsory miss is counted once per block and not once per pass, so A fails; a fully associative cache has no placement restriction and therefore no conflict misses, so C fails; and the 200 misses of pass 1 are compulsory rather than capacity, so D fails.
Compare Page Replacement Algorithms MCQs: FIFO, LRU, Optimal while keeping pages and cache blocks distinct.
Four-way set-associative LRU MCQ: isolate the contested set
With 16 / 4 = 4 sets, reduce addresses modulo 4 and trace set 0.
Question 12
Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order: 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155. Which one of the following memory block will NOT be in cache if LRU replacement policy is used?
A. 3
B. 8
C. 129
D. 216
Answer: D, 216. Set 0 sees 0, 4, 8, 216, 8, 48, 32, 92. Four fills come first; the 8 hit refreshes it. Then 48 evicts 0, 32 evicts 4, and 92 evicts 216. Final set: {8,48,32,92}; blocks 3 and 129 remain elsewhere.
GATE 2009 four-way LRU question
Cache replacement MCQs: the short revision method and next step
Identify the mapping.
Calculate the number of sets.
Compute
block mod sets.Mark compulsory misses before classifying conflict or capacity misses.
Update LRU on every hit and fill.
Examiners set this topic in two shapes. One is a trace that asks which block survives, or how many misses a reference string costs. The other is a one-line concept check on which miss type a given change removes. The traces are where marks leak, because one hit recorded as a miss shifts every eviction that follows it.
For rapid revision, the answers are: 1-C, 2-B, 3-A+C, 4-A+D, 5-C, 6-A+C, 7-C, 8-C, 9-B, 10-B, 11-B, 12-D.
For paging review, revisit Virtual Memory and Demand Paging MCQs and Page Replacement Algorithms MCQs. Continue with GATE Guidance by Sanchit Sir or the GATE CS preparation category.
