GATE CS 2026 Set 2 — Question 52
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+2 / -0HardDirect-Mapped CacheMemory Hierarchy & CacheComputer Organization & ArchitectureCache Numericals
Computer Organization & Architecture → Memory Hierarchy & Cache → Cache Numericals
Last updated
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: 0x846B32Which of the following statements is/are true?Note: and
Correct answer
(A) Every access to P results in a cache miss; (B) Every access to R results in a cache hit
Solution
Cache Configuration:
We look at the last 3 hex digits (12 bits) to determine the Set Index (middle 8 bits) and Offset (last 4 bits).
- Cache Size = 4 KB = bytes
- Block Size = 16 bytes = bytes
- Number of Lines = lines
- Address Mapping: Block Offset = 4 bits, Line Index = 8 bits, Tag = Remaining bits.
We look at the last 3 hex digits (12 bits) to determine the Set Index (middle 8 bits) and Offset (last 4 bits).
1.P: 0x845B32
- Last 12 bits: 0xB32 = 1011 0011 0010
- Offset: 0010 (2)
- Index: 1011 0011 = 0xB3
- Tag: 0x845
- Last 12 bits: 0xB26 = 1011 0010 0110
- Offset: 0110 (6)
- Index: 1011 0010 = 0xB2
- Tag: 0x845
- Last 12 bits: 0xB36 = 1011 0011 0110
- Offset: 0110 (6)
- Index: 1011 0011 = 0xB3
- Tag: 0x845
- Last 12 bits: 0xB32 = 1011 0011 0010
- Offset: 0010 (2)
- Index: 1011 0011 = 0xB3
- Tag: 0x846
- Line 0xB2: Accessed only by Q. Tag 0x845.
- 1st access: Miss (Cold). Block loaded.
- Subsequent accesses: Hit.
- Line 0xB3: Accessed by P, R, S in sequence P R S.
- Sequence: P (Tag 845) R (Tag 845) S (Tag 846) P (Tag 845) ...
- Step 1 (P): Tag 845. Cache Empty/Different. Miss. Install Tag 845.
- Step 2 (R): Tag 845. Cache has 845. Hit.
- Step 3 (S): Tag 846. Cache has 845. Miss. Replace with Tag 846.
- Step 4 (P): Tag 845. Cache has 846. Miss. Replace with Tag 845.
- Step 5 (R): Tag 845. Cache has 845. Hit.
- This cycle repeats.
- P is always a Miss (evicted by S).
- R is always a Hit (brought in by P).
- Q is a Miss once, then Hits.
- S is always a Miss (evicted by P).
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Memory Hierarchy & Cache
2026 Set 1 Q14Match each addressing mode in List I with a data element or an element of a data structure (in…2026 Set 1 Q15Consider a processor P whose instruction set architecture is the load-store architecture. The…2026 Set 1 Q16Which one of the following dependencies among the register operands of different instructions can…2026 Set 2 Q18Consider the following two statements about interrupt handling mechanisms in a CPU. S1: In…2026 Set 1 Q38The size of the physical address space of a processor is bytes. The capacity of a cache…