GATE CS 2022 Q28 — Memory Management and Virtual Memory

To determine which statement is FALSE, let us analyze each option individually:

• Option A (TRUE): The Translation Lookaside Buffer (TLB) is implemented using associative memory (Content Addressable Memory or CAM). It performs a parallel, single-cycle search on all its valid entries simultaneously using the page number of the incoming virtual address.
• Option B (TRUE): A TLB hit guarantees that the page translation is valid and the corresponding page is currently resident in the main memory. If a subsequent cache miss occurs, the CPU must fetch the word from the main memory. Since the page is already in the main memory, no page fault occurs, and the word is guaranteed to be present there.
• Option C (FALSE): An inverted page table contains one entry for each physical frame. To translate a virtual address, the system typically searches the table using a hash function. Because of hash collisions, different virtual addresses may map to chains of different lengths, resulting in different search times. Even with a linear search, the time taken depends on the position of the entry in the table. Thus, the memory access time is not always the same for all incoming virtual addresses.
• Option D (TRUE): In a hashed page table, collisions are resolved using chaining (linked lists). If two distinct virtual addresses $V_1$ and $V_2$ hash to the same index, they are placed in a chain. Searching for the element deeper in the chain requires traversing more nodes, which increases the number of memory accesses. Thus, their memory access times will not be the same.

Therefore, statement C is false.