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:

A TLB hit always skips the page table walk entirely; and a page table miss means the page is not in memory, so by the eviction-invalidates-cache rule no cache hit is possible then.

Answer 1

The Correct Option is B, C

Step 1: Concept.
Because the cache is fed a PHYSICAL address, the physical address must be resolved before the cache can be looked up at all. Resolution first tries the TLB; only on a TLB miss is the page table consulted. If the TLB hits, the page table is never touched at all for that reference - the whole point of a TLB is to skip the page table walk. If the page table itself misses, the page is not currently resident in main memory (a page fault), so its data does not exist in memory yet. We are also told that evicting a page from memory invalidates its cached blocks, which means a cache hit can only occur for data belonging to a page that is currently resident in memory.

Step 2: Test option (A): TLB miss, Page table hit, Cache hit.
TLB miss triggers a page table walk; the page table hits, so the page is resident and its physical address is obtained. The physical address then indexes the cache, which can perfectly well already hold a valid, previously-cached block for that resident page (e.g. this exact line was accessed earlier and its TLB entry has since been evicted, but the page and its cache block are still resident and valid). This sequence is entirely consistent and CAN happen.

Step 3: Test option (B): TLB hit, Page table miss, Cache hit.
A TLB hit means the physical address was obtained directly from the TLB, and by design the page table is not consulted at all in that case - there is no such event as "the page table missing" once the TLB has already supplied the translation. Having both "TLB hit" and "page table miss" reported for the same reference is a logical contradiction, since the second step never executes. This sequence can NEVER happen.

Step 4: Test option (C): TLB miss, Page table miss, Cache hit.
TLB miss triggers a page table walk, which also misses - a page fault, meaning the requested page is NOT currently resident in main memory (it must be fetched from disk first). Per the rule given in the problem, whenever a page is evicted from memory its cache blocks are invalidated, so no valid cached block can exist for a page that is not currently in memory (if it were cached from a previous residency, that block was invalidated on eviction). Since the page is definitively absent from memory at this moment, a valid, hit-able cache entry for it cannot exist. So reporting a Cache hit here is impossible. This sequence can NEVER happen.

Step 5: Test option (D): TLB miss, Page table miss, Cache miss.
This is the classic full page-fault path: translation fails in both the TLB and the page table, the operating system brings the page in from disk, the physical address is finally obtained, and since the page was not resident a moment ago there is naturally no cached block for it yet, so the cache reports a miss too. Fully consistent, and CAN happen.

Step 6: Conclusion.
(A) and (D) are ordinary, achievable sequences. (B) is impossible because a TLB hit bypasses the page table entirely, so it can never also report a page table miss. (C) is impossible because a page table miss means the page is not resident in memory, and the given invalidate-on-eviction rule guarantees no valid cache hit can exist for non-resident data.

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