Question

Consider a system with a processor and a 4 KB direct mapped cache with block size
of 16 bytes. The system has a 16 MB physical memory. Four words P, Q, R, and S
are accessed by the processor in the same order 10 times. That is, there are a total
of 40 memory references in the sequence P, Q, R, S, P, Q, R, S,…
Assume that the cache memory is initially empty. The physical addresses of the
words are given below (1 word =1 byte).
P: 0x845B32, Q: 0x845B26, R: 0x845B36, S: 0x846B32
Which of the following statements is/are true?
Note: \(1\mathrm{K}=2^{10}\) and \(1\mathrm{M}=2^{20}\)

• A. Every access to P results in a cache miss
• B. Every access to R results in a cache hit
• C. Every access to Q results in a cache miss
• D. Except the first access to S, all subsequent accesses to S result in cache hits

Hint:

Work out (tag, index, offset) for each address using 4 offset bits, 8 index bits, 12 tag bits. Notice P and R share the same tag and index (same block), while S shares only the index with them (different tag), causing repeated conflicts with P.

Answer 1

The Correct Option is A, B

Instead of jumping straight to tag/index/offset formulas, let us reason about this cache problem the way you would during the exam - by spotting collisions between addresses.

Setting up the cache geometry: cache size = 4 KB, block size = 16 B, so number of lines = 4096/16 = 256. That needs 8 bits for the line index and 4 bits for the byte offset within a block. Since the memory is 16 MB = \(2^{24}\) bytes, addresses are 24 bits wide, leaving \(24 - 12 = 12\) bits for the tag.

A shortcut using hex digits: because 4 bits = 1 hex digit exactly, for any 6-digit hex address, digit 6 (rightmost) is the offset, digits 4-5 (from the right) form the index, and digits 1-3 form the tag. Applying this:

P = 845B32 to tag 845, index B3, offset 2.

Q = 845B26 to tag 845, index B2, offset 6.

R = 845B36 to tag 845, index B3, offset 6.

S = 846B32 to tag 846, index B3, offset 2.

Spotting the collisions: notice P and R share both tag 845 and index B3 - so they are literally two bytes inside the very same cache block. Q sits on a completely private line (B2) that nobody else ever disturbs. S shares the same line (B3) as P/R but carries a different tag (846), so S and the P/R pair are rivals fighting over one line slot.

Walking through repeated rounds of P-Q-R-S: whenever P is accessed, the line B3 currently holds S's data (tag 846) because S was the last thing to touch that line in the previous round - so P always misses and reloads line B3 with tag 845. Right after that, R is accessed, and since R needs exactly the block P just loaded (same tag, same index), R always hits. Q, meanwhile, only ever misses on its very first access (cold start); afterward its private line B2 is untouched by P, R, or S, so all later Q accesses are hits. Finally S arrives right after R, finds line B3 loaded with tag 845 (not its own tag 846), and therefore misses every single round, not just the first.

Matching to the options: P is always a miss - correct. R is always a hit - correct. Q is not always a miss (only the first time) - incorrect. S does not hit after the first access (it misses every time) - incorrect.

So the true statements are: every access to P is a miss, and every access to R is a hit.