GATE CS 2026 Set 1 Q44 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To determine which sequences of events can NEVER happen, let us analyze the relationship between the Translation Lookaside Buffer (TLB), the Page Table, and the physically addressed Cache.

1. Analyzing Option B: TLB hit, Page table miss, Cache hit

• A TLB hit occurs when the virtual-to-physical address translation is found in the TLB. Since the TLB only stores translations for pages currently residing in main memory, a TLB hit guarantees that the page is present in the main memory.
• A Page table miss (page fault) indicates that the requested page is not present in the main memory.
• These two conditions are contradictory: we cannot have a TLB hit for a page that is not present in main memory.

Therefore, the sequence in Option B can NEVER happen.

2. Analyzing Option C: TLB miss, Page table miss, Cache hit

• A Page table miss means the requested page is not present in the main memory.
• The problem states: "when a page is evicted from the main memory, the corresponding blocks in the cache are marked as invalid."
• Since the page is not in main memory, any cache blocks belonging to this page must be invalid. Thus, a Cache hit is impossible.

Therefore, the sequence in Option C can NEVER happen.

3. Verifying Options A and D:

• Option A (TLB miss, Page table hit, Cache hit): This is a standard scenario. The translation is not in the TLB (TLB miss), but the page is in main memory (Page table hit), and the specific block is already cached (Cache hit). This can happen.
• Option D (TLB miss, Page table miss, Cache miss): This occurs when a page is not in main memory. The translation is not in the TLB (TLB miss), the page is not in main memory (Page table miss), and consequently, the block is not in the cache (Cache miss). This can happen.

Thus, the sequences that can never happen are B and C.