GATE CSE 2022 | Question: 28

Question

Which one of the following statements is $\text{FALSE}?$

• A. The $\text{TLB}$ performs an associative search in parallel on all its valid entries using page number of incoming virtual address.
• B. If the virtual address of a word given by $\text{CPU}$ has a $\text{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.
• C. The memory access time using a given inverted page table is always same for all incoming virtual addresses.
• D. In a system that uses hashed page tables, if two distinct virtual addresses $\text{V1}$ and $\text{V2}$ map to the same value while hashing, then the memory access time of these addresses will not be the same.

Comments

inverted paging for option c :

---

An easy question made super easy simply because it was not MSQ

---

Statement A is true because the translation lookaside buffer uses special associative hardware memory to check all entries at the same time using the virtual page number.

Statement B is true because a hit in the translation lookaside buffer guarantees that the virtual page has a valid mapping in the main memory, so a subsequent cache miss will still find the data in main memory without causing a page fault.

Statement C is false because an inverted page table relies on a hash table structure where entries are searched using a hash function, and because different virtual addresses can map to different chain lengths during collisions, the lookup time is not always the same.

Statement D is true because when two distinct virtual addresses V1 and V2 hash to the same value, a collision occurs and they are stored in a chained list, causing the address located further down the chain to take more time to access.

Therefore, the false statement is C.

Answer 1

Ans: Option C

• A. According to Galvin, “The TLB is associative, high-speed memory. Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the item is found, the corresponding value field is returned.” Hence option A is TRUE. 

 

• A. The TLB contains only a few of the page-table entries. If the virtual address of a word given by CPU has a TLB hit it means the the page number is found, so its frame number is immediately available and is used to access memory. Therefore even if the subsequent search for the word results in a cache miss, it does not matter. Its just not in cache memory but the word will always be present in the main memory as we already know the frame number due to the TLB Hit. Hence option B is also TRUE. 

 

• A. An Inverted Page Table has frame numbers as indexes unlike a Page Table where page number is used as index to it. Therefore for any given virtual address we need to search the exact $<page no., process no.>$ in the frames of MM. In worst case we might have to search all the frames of the MM inorder to get the exact $<page no., process number>$. (This is because we may find the required $pg. no.$, but it might be of a different process. So Bad Luck!) This increases main memory access time. This is the reason why the Inverted Page table uses less space but searching time is more. Therefore, the memory access time using a given inverted page table is not always same for all incoming virtual addresses. Hence option C is FALSE and is the ans. 

 

• A. In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, it means they will be present as a linked list of items having same hashed values. Then the memory access time of these addresses will not be the same as in a Linked List the best case T.C = Omega(1) for the first element and worst case T.C. = O(N) for the last element in chained LL. Hence option D is also TRUE. 

Comments

@sk91 the cache can also be VIPT no? we get the tag from TLB and index from page offset

---

Since TLB's are a type of Cache memory, while they are associatve the claim that it compares a given Virtual address wih all the entries in it simultaneously is over generalised. We can have set associative or direct mapped TLB where we only check the Tag bit in the entry which is mapped to the page no. Or in set associatve we search in parallel only within the set that the VA is mapped to

---

That table is showing TLB miss and hit related to page table entry

That will bw correct bcoz tlb will pe contain page table entries just like cache for mm but it asked about page in mm. Any other reference

Answer 2

$\underline{\textbf{Answer: C }}$

$\underline{\textbf{Explanation: }}$

$\textbf{Option (A):}$

TLB is like a Fully Associative Cache. We know that in the fully associative cache, the search is made on the basis of $\color {red}{\textbf{Content}}$ rather than the $\color {red}{\textbf{Address}}$. It matches all the Tags parallelly and at once. Therefore, Option (A) looks TRUE as well.

$\textbf{Option (B):}$ This option is TRUE as well.

$\underline{\textbf{Control Flow:}}$ 

1. First, we go to Cache Memory, and if there is a cache hit, then no problem.
2. In case there is a cache miss, we go to the next step.
3. In this step we will go to the TLB, if there is TLB Hit. Then, we will go to the physical memory using the physical address.
4. In case there is a TLB Miss, then we will access the “page table”, in order to obtain the frame number.
5. If the page is not found, then it means that there is a “page fault”. At this juncture, we will use one of the page replacement algorithms, in order to obtain the page from secondary memory to physical memory.

https://en.wikipedia.org/wiki/Translation_lookaside_buffer#:~:text=The%20TLB%20is,data%20address%20TLBs.

$\textbf{Option (C):}$

An inverted Page Table is nothing but a Hash Map. So, with the same logic as D option C looks False.

$\textbf{Option (D):}$
This is true as when two values are mapped to the same address, then the values are added in form of a linked list. In the best case for the first element of the linked list, time complexity will be $\mathbf{O(1)}$, and for the last element of the chained linked list, time complexity will be $\mathbf{O(n)}$.

$\textbf{ Good Links:}$

https://stackoverflow.com/questions/37825859/cache-miss-a-tlb-miss-and-page-fault

https://cs.stackexchange.com/questions/66698/difference-between-page-table-and-inverted-page-table

Comments

Hashed PageTables Tutorial-21 - YouTube
This video will be helpful for option D.

---

In control flow, i think we first go to TLB to get Physical address from Logical Address. when we get Physical address then we go to cache memory  to see if it exist, if not then go to Main memory.

We can't directly go to Cache first since CPU generates logical address and not actual physical address.
Correct me if i am wrong.

---

Maybe he's talking about "VIPT" cache 

Such type of caches are virtually indexed and physically tagged

Answer 3

Created with the help of the useful Answer for better visualization

Answer 4

a) it is true that TLB performs an associativity search in parallel when one VA coming from a CPU

b) one word TLB + Cache then TLB hit --> cache miss --> but if the VA valid then it can be present in Main memory

c) inverted paging telling every fames searching it needs same time but this is false because in inverted paging we use hashed function so this function caused collision in some frames it does not guuraanety that every pages taken same time .

d) in hashing the page table of distinct VA map to the same hash table value  then  mm is not same ... take of  chaining hash you can understand.

Answer 5

Answer: C

A. True:
TLB stores the mapping between virtual page numbers and physical frame numbers. When a virtual address is generated, the TLB searches for the page number using associative search, so multiple valid entries can be compared in parallel.

B. True:
If there is a TLB hit, the physical address of the required page is known. If there is a cache miss, the processor can access the main memory using this physical address. Hence, the required word will be present in main memory.

C. False:
In an inverted page table, there is one entry for each physical frame. The time required to find the required entry can vary depending on the virtual address and the search/hash result. Therefore, memory access time is not always the same for all virtual addresses.

D. True:
In a hashed page table, two different virtual addresses can produce the same hash value. This is called a collision. In such a case, the system may have to search through the entries in that hash bucket. Therefore, the access time can be different for different addresses.

Hence, the false statement is C.