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: Model the memory reference as a strict pipeline of gated stages: Stage 1 (TLB lookup) always runs first. Stage 2 (page table walk) runs ONLY if Stage 1 reports a miss - it is skipped entirely on a TLB hit. Stage 3 (cache lookup) always runs last, but only once a physical address has actually been produced by either Stage 1 or Stage 2, and its outcome is further constrained by the physical residency of the referenced page (a cache hit needs a currently-valid block, which needs the page to currently be in memory).

Step 2: Because Stage 2 is gated behind a Stage 1 miss, any option beginning with "TLB hit" can only be logically followed by "page table skipped", never by "page table hit" or "page table miss" - both would imply Stage 2 ran despite Stage 1 succeeding, which contradicts the whole purpose of a TLB (avoiding the page table walk on a hit). Option (B), "TLB hit, Page table miss, Cache hit", asserts Stage 2 ran and missed after Stage 1 already succeeded - a direct contradiction of the gating rule. Impossible.

Step 3: For entries that DO reach Stage 2 (TLB miss cases), Stage 2's outcome tells us about residency: a page table hit means the page is currently in main memory (with a valid physical frame); a page table miss means it is not (page fault, must be fetched from disk).

Step 4: Cache validity is explicitly tied to residency in this problem: "when a page is evicted from main memory, the corresponding blocks in the cache are marked as invalid". Turn this around: a cache block can be VALID (hit-able) only while its page remains resident; the instant the page leaves memory, any of its blocks are forced invalid. So at the moment of a page table miss (page currently absent from memory), no valid cache block tied to that page can exist - it would have already been invalidated the moment the page was last evicted (or it was simply never brought in to begin with). Therefore "Page table miss" logically forces "Cache miss" as the only possible outcome for Stage 3 whenever Stage 2 misses. Option (C), "TLB miss, Page table miss, Cache hit", violates this forced implication. Impossible.

Step 5: Options (A) "TLB miss, Page table hit, Cache hit" and (D) "TLB miss, Page table miss, Cache miss" both respect every gate and every implication derived above: (A) has Stage 2 succeed (page resident) followed by a legitimate cache hit on already-resident, previously-accessed data; (D) has Stage 2 fail (page absent) correctly forcing the cache miss required by Step 4. Both are achievable and ordinary in practice (a stale TLB entry evicted while the page/cache-line remain resident gives (A); a genuine page fault gives (D)).

Step 6: Only the two sequences that break a hard gating/implication rule - (B) breaking the TLB-hit-skips-page-table gate, and (C) breaking the residency-implies-cache-validity rule - can never occur.

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