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

This question tests the relationship between the TLB, the page table, and a physically indexed and physically tagged cache. Since the cache is addressed using the physical address, a cache lookup can only proceed once a valid physical address has been produced by either the TLB or the page table walk.

Step 1: Understand the roles. The TLB stores recently used virtual-to-physical translations, essentially caching a subset of page table entries. A TLB hit means the page is definitely resident in main memory (a valid frame number exists). A TLB miss simply means the CPU must now consult the page table, which may itself result in a page table hit (page present in memory, frame number found) or a page table miss (page not present, i.e. a page fault).

Step 2: Evaluate Option A - TLB miss, Page table hit, Cache hit. Here the TLB does not have the translation cached, but the page table walk finds the page resident in memory, giving a valid physical address. Since the cache holds data based on physical addresses and is independent of the TLB, it is entirely possible that this physical address' data is already sitting in the cache from an earlier access (perhaps loaded when a different process or thread referenced it). So this sequence CAN happen.

Step 3: Evaluate Option B - TLB hit, Page table miss, Cache hit. A TLB hit is only possible if a valid translation exists in the TLB, and a TLB entry can only be valid if the corresponding page table entry is currently marked present in memory. If the page table entry were invalid (a miss/page fault), the TLB entry for that page would have been invalidated as well (this is exactly why TLB shootdown/invalidation happens on page eviction). Hence 'TLB hit' and 'Page table miss' for the same reference are logically contradictory. This sequence can NEVER happen.

Step 4: Evaluate Option C - TLB miss, Page table miss, Cache hit. A page table miss means the referenced page is currently NOT resident in main memory (page fault). The problem statement explicitly says that when a page is evicted from main memory, the corresponding cache blocks are marked invalid. Since the page is absent from memory, there is no valid physical frame backing this data, so any previously cached physical address for this page's frame must already have been invalidated. Therefore a cache hit is impossible in this state. This sequence can NEVER happen.

Step 5: Evaluate Option D - TLB miss, Page table miss, Cache miss. This is the standard full page-fault scenario: translation not in TLB, page not in memory, so naturally no data can be cached either. This is fully consistent and CAN happen.

Therefore, the sequences that can never occur are exactly Option B and Option C.

\[ \boxed{\text{Answer: (B) and (C)}} \]