IAE Academy

GATE 2022 CS Q.38: solution and answer

GATE 2022 · CSQ.38 · 2 marks · MCQ

Which one of the following statements is FALSE?

  1. (A)

    The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.

  2. (B)

    If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.

  3. (C)

    The memory access time using a given inverted page table is always same for all incoming virtual addresses.

  4. (D)

    In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.

See the question in the paper
GATE 2022 CS question 38Tap to open full size

Answer and solution

ANSWER

The false statement is (C): an inverted page table's lookup time depends on the address, because of hashing and collision chains, so it is not always the same.

Official answer: CSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

  1. We need the FALSE statement, so check each one and find the one that cannot be guaranteed.

  2. (A) A TLB is associative memory. The page number of the incoming virtual address is compared with all valid entries in parallel. True.

  3. (B) A TLB hit means the page has a valid mapping to a frame, so the page is resident in main memory. If the word then misses in the cache, it is fetched from main memory, where it must be present. True.

  4. (C) An inverted page table has one entry per physical frame. The entry for a virtual address is found by a hash lookup or a search, and the number of probes depends on the address. One address may be found at the first probe while another needs several probes along a collision chain. So the access time is not always the same, and this statement is FALSE.

  5. (D) In a hashed page table, two addresses that hash to the same value share a bucket on a collision chain. One is found earlier in the chain and the other after traversing more entries, so their access times differ. True.

  6. The false statement is (C).

KEY IDEA

Search an inverted or hashed page table through a hash bucket and collision chain, so lookup time varies with the address. A TLB hit guarantees the page is resident in main memory.

WATCH OUT FOR

Assuming an inverted page table gives constant-time lookup because it has one entry per frame. Another slip is doubting (B): a cache miss after a TLB hit still means the word is in main memory.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 10 Memory management questions, with notes

More Memory management questions