Question

Consider a system that has a cache memory unit and a memory management unit
(MMU). The address input to the cache memory is a physical address. The MMU
has a translation lookaside buffer (TLB). Assume that when a page is evicted from
the main memory, the corresponding blocks in the cache are marked as invalid.
For a given memory reference, which of the following sequences of events can
NEVER happen?

• A. TLB miss, Page table hit, Cache hit
• B. TLB hit, Page table miss, Cache hit
• C. TLB miss, Page table miss, Cache hit
• D. TLB miss, Page table miss, Cache miss

Hint:

Remember that a TLB entry can be valid only if its page table entry is also valid, and that cache blocks are invalidated whenever their backing page is evicted from memory. Use these two facts to spot the contradictory or impossible option pairs.

Answer 1

The Correct Option is B, C

Think of this problem as a consistency check between three layers of the memory hierarchy: the TLB (fast translation cache), the page table (full translation record), and the cache (which only understands physical addresses).

The key invariant to apply is: a TLB entry is valid only if the page it maps is currently present in main memory. This is because the operating system invalidates TLB entries the moment a page is swapped out or evicted, and the cache blocks tied to that physical frame are invalidated at the same time.

Using this invariant, check each combination logically rather than mechanically:

• If TLB says 'hit', the page MUST be in memory, so the page table cannot simultaneously say 'miss'. Any option claiming TLB hit + page table miss is self-contradictory and impossible - this rules out option B.
• If the page table says 'miss', the page is not in memory at all, meaning the physical frame that would service this address is not currently backing this page. Since evicted pages force cache invalidation, there is nothing valid for the cache to hit on. So page table miss + cache hit is also impossible - this rules out option C.
• TLB miss + page table hit + cache hit is fine: the translation simply was not cached recently in the TLB, but the physical address is still valid and its data may genuinely still be sitting in the cache.
• TLB miss + page table miss + cache miss is the textbook full page-fault case, and is completely consistent.

So the impossible sequences, matching the given key, are \(\text{Option B}\) and \(\text{Option C}\).

Final answer: B and C (options 2 and 3).