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: 1K=210 and 1M=220

• 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

We have a 4 KB direct mapped cache with a 16-byte block size, sitting in front of a 16 MB (\(2^{24}\) byte) physical memory. We need to decode the address of each variable into its tag, line index and block offset, then trace the repeating access pattern P, Q, R, S.

Step 1: Work out the field widths

Number of cache lines = 4096 / 16 = 256 lines.

Offset bits = \(\log_2 16 = 4\) bits (selects a byte inside a 16-byte block).

Index bits = \(\log_2 256 = 8\) bits (selects one of 256 lines).

Tag bits = \(24 - 8 - 4 = 12\) bits (since the address space is 16 MB = \(2^{24}\)).

Step 2: Decode each address

Because each hex digit equals exactly 4 bits, the last hex digit of a 6-digit address is the offset, the next two hex digits form the index, and the remaining three hex digits form the tag.

P = 0x845B32 gives tag = 0x845, index = 0xB3 (179 in decimal), offset = 2.

Q = 0x845B26 gives tag = 0x845, index = 0xB2 (178 in decimal), offset = 6.

R = 0x845B36 gives tag = 0x845, index = 0xB3 (179 in decimal), offset = 6.

S = 0x846B32 gives tag = 0x846, index = 0xB3 (179 in decimal), offset = 2.

Step 3: The key structural observation

P and R have the identical tag (0x845) and identical index (179), so they actually live inside the same 16-byte block, just at different byte offsets (2 and 6). Q lives alone on line 178, which no other variable ever touches. S also maps to line 179 (same index as P and R) but with a different tag (0x846), so S constantly fights with P/R for that one line.

Step 4: Trace the repeating cycle P, Q, R, S

P: In every cycle, S was the access immediately before P (from the previous cycle, or nothing before the very first P). Since S always leaves line 179 holding tag 0x846, when P arrives it never finds its own tag 0x845 there - so P reloads the line every single time. Every access to P is a miss.

R: R always comes immediately after P in the sequence. P has just loaded line 179 with tag 0x845, and R needs that exact tag and index (they are in the same block). So R always finds its data already resident. Every access to R is a hit.

Q: The very first access to Q is a compulsory miss (cache starts empty). After that, since no other variable ever maps to line 178, Q keeps finding its own block there on every later access. So Q is a miss only once, not on every access.

S: S is accessed right after R in each cycle. R access has just re-confirmed that line 179 holds tag 0x845 (P and R's block), so when S (tag 0x846) arrives, it always mismatches and misses - not just on the first access, but every time, because P immediately evicts S's block again on the next cycle.

Step 5: Evaluate the options

Option 1 (every access to P is a miss) - True.

Option 2 (every access to R is a hit) - True.

Option 3 (every access to Q is a miss) - False, only the first access misses.

Option 4 (except the first access, all S accesses hit) - False, every S access is a miss.

Final Answer: Options 1 and 2 are correct, i.e. \[\text{Every access to P is a miss, and every access to R is a hit.}\]