Question:medium
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,\ldots\)
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=2^{10}\) and \(1M=2^{20}\)
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,\ldots\)
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=2^{10}\) and \(1M=2^{20}\)
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=2^{10}\) and \(1M=2^{20}\)
Show Hint
Work out the tag and index for each address and see which of P, Q, R, S share a cache line and which stay isolated on their own line.
Updated On: Jul 22, 2026
- Every access to \(P\) results in a cache miss
- Every access to \(R\) results in a cache hit
- Every access to \(Q\) results in a cache miss
- Except the first access to \(S\), all subsequent accesses to \(S\) result in cache hits
Show Solution
The Correct Option is A, B
Solution and Explanation
Step 1: Get the index and offset widths from the cache size.
Cache size is $4$ KB and block size is $16$ bytes, so there are $4096/16=256$ lines, needing $8$ bits for the index. A $16$ byte block needs $4$ bits for the offset. So the lowest $4$ bits of an address pick the byte inside a block, and the next $8$ bits above that pick the cache line.
Step 2: Convert the addresses using only their low bits.
We only need the lowest $12$ bits of each address, the same as the lowest $3$ hex digits.
$P$: last three hex digits $B32$, offset $=2$, index byte $=B3$.
$Q$: last three hex digits $B26$, offset $=6$, index byte $=B2$.
$R$: last three hex digits $B36$, offset $=6$, index byte $=B3$.
$S$: last three hex digits $B32$, offset $=2$, index byte $=B3$.
The tag is everything above these $12$ bits, which is $845$ for $P,Q,R$ and $846$ for $S$.
Step 3: Draw the conflict picture.
Line $B2$ is used only by $Q$, so once it is loaded it is never disturbed again; every access after the first is a hit there. Line $B3$ is shared by three different accesses per round: $P$ and $R$ belong to the same block, tag $845$, while $S$ belongs to a different block, tag $846$, that maps to the same line. Since a direct mapped cache allows only one block per line, the $P/R$ block and the $S$ block constantly kick each other out of line $B3$.
Step 4: Follow one full round once the pattern has settled.
Suppose line $B3$ holds $S$'s block, tag $846$, at the start of a round, left over from the previous round's last access. Then: $P$ needs tag $845$, finds $846$, MISS, reloads $845$. $Q$ needs line $B2$, untouched, HIT. $R$ needs tag $845$ at line $B3$, which $P$ just loaded, HIT. $S$ needs tag $846$ at line $B3$, which currently holds $845$, MISS, reloads $846$. This leaves line $B3$ holding $846$ again at the end of the round, exactly the condition assumed at the start, so the same four outcomes, miss, hit, hit, miss, repeat identically in every later round.
Step 5: Handle the very first round separately.
On the first round the cache starts empty rather than holding $846$, but the outcome is the same: $P$ misses, empty line, $Q$ misses, empty line, but this is its only miss ever, $R$ hits, block just loaded by $P$, $S$ misses, different tag at line $B3$.
Step 6: Read off which statements always hold.
$P$: miss in every one of the $10$ rounds, so every access to $P$ is a miss is true. $R$: hit in every one of the $10$ rounds, so every access to $R$ is a hit is true. $Q$: misses only in round $1$, so every access to $Q$ is a miss is false. $S$: misses in every round, not just the first, so all accesses after the first being hits is false.
Step 7: Conclude.
\[ \boxed{\text{Statements (A) and (B) are correct}} \]
Cache size is $4$ KB and block size is $16$ bytes, so there are $4096/16=256$ lines, needing $8$ bits for the index. A $16$ byte block needs $4$ bits for the offset. So the lowest $4$ bits of an address pick the byte inside a block, and the next $8$ bits above that pick the cache line.
Step 2: Convert the addresses using only their low bits.
We only need the lowest $12$ bits of each address, the same as the lowest $3$ hex digits.
$P$: last three hex digits $B32$, offset $=2$, index byte $=B3$.
$Q$: last three hex digits $B26$, offset $=6$, index byte $=B2$.
$R$: last three hex digits $B36$, offset $=6$, index byte $=B3$.
$S$: last three hex digits $B32$, offset $=2$, index byte $=B3$.
The tag is everything above these $12$ bits, which is $845$ for $P,Q,R$ and $846$ for $S$.
Step 3: Draw the conflict picture.
Line $B2$ is used only by $Q$, so once it is loaded it is never disturbed again; every access after the first is a hit there. Line $B3$ is shared by three different accesses per round: $P$ and $R$ belong to the same block, tag $845$, while $S$ belongs to a different block, tag $846$, that maps to the same line. Since a direct mapped cache allows only one block per line, the $P/R$ block and the $S$ block constantly kick each other out of line $B3$.
Step 4: Follow one full round once the pattern has settled.
Suppose line $B3$ holds $S$'s block, tag $846$, at the start of a round, left over from the previous round's last access. Then: $P$ needs tag $845$, finds $846$, MISS, reloads $845$. $Q$ needs line $B2$, untouched, HIT. $R$ needs tag $845$ at line $B3$, which $P$ just loaded, HIT. $S$ needs tag $846$ at line $B3$, which currently holds $845$, MISS, reloads $846$. This leaves line $B3$ holding $846$ again at the end of the round, exactly the condition assumed at the start, so the same four outcomes, miss, hit, hit, miss, repeat identically in every later round.
Step 5: Handle the very first round separately.
On the first round the cache starts empty rather than holding $846$, but the outcome is the same: $P$ misses, empty line, $Q$ misses, empty line, but this is its only miss ever, $R$ hits, block just loaded by $P$, $S$ misses, different tag at line $B3$.
Step 6: Read off which statements always hold.
$P$: miss in every one of the $10$ rounds, so every access to $P$ is a miss is true. $R$: hit in every one of the $10$ rounds, so every access to $R$ is a hit is true. $Q$: misses only in round $1$, so every access to $Q$ is a miss is false. $S$: misses in every round, not just the first, so all accesses after the first being hits is false.
Step 7: Conclude.
\[ \boxed{\text{Statements (A) and (B) are correct}} \]
Was this answer helpful?
0
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems