GATE2006-62, ISRO2016-50

Question

A CPU generates $32$-bit virtual addresses. The page size is $4$ KB. The processor has a translation look-aside buffer (TLB) which can hold a total of $128$ page table entries and is $4$-way set associative. The minimum size of the TLB tag is:

• A. $\text{11 bits}$
• B. $\text{13 bits}$
• C. $\text{15 bits}$
• D. $\text{20 bits}$

Comments

I am having difficulty in solving virtual memory concepts involving the concept of associative caches. Can someone please provide a link where I can gain more knowledge about it .

---

No of entries in TLB= 2^7 4-way set

so each set has 2^7/4= 2^5 sets

2^20 pages of process PTE mapped to 2^5 sets

so each set can accomodate 2^20/2^5= 2^15. so in each set to know which page among 2^15 page table entry preseent we need 15 bits.

---

Virtual memory means address space of the process and page table corresponding to this process pages(present in main memory) is stored in TLB for faster access. 15bits will be used as tag bits to check whether the page table is of the desired process or not.

---

Doesn't virtual memory tell the size of the process ?

---

@nadeshseen Virtual memory is basically storing the code+data of a running program into main memory as well as in secondary memory(hard disk) instead of storing it fully into main memory(RAM). In this technique, the main memory remains empty so that it could be used to execute many programs simultaneously.

---

@Nitesh Singh 2 Sorry, I didn't ask the question properly. I know what VM is but in TLB each entry stores the number of bits required to address the physical memory(main memory). My question is, in the above problem instead of virtual addresses, shouldn't it be physical addresses?

Physical Address Space = Main memory Size

Logical Address Space / Virtual Address Space = Process Size

---

@nadeshseen First of all, It is not accurate to say TLB stores bits required to address main memory, it stores the page table of a process and relevant page table entry in page table says where the part of the process is stored in main memory. Now coming back to your query, since a process size or logical address space could be more than main memory size then some part of the process would be stored in secondary memory, now if we have to execute the part of the process which is not in main memory, then how would we do that?
If we call address in the form of physical address space to fulfil our need, we can never reach to the code which is in secondary memory but if we call it in the form of virtual memory(logical address space) then we can fetch that part of the process also and control unit of CPU replaces the required pages with earlier pages present in the main memory.

---

@Nitesh Singh 2 If some part of the process is not in main memory then page fault occurs. Now, you have to bring that part of the process in the main memory only then you can service it. You never store the logical address(/virtual address) in the page table, only the number of entries depends on the logical address space. Each entry tells where that frame is stored in the main memory and whether that frame is in the main memory or not using the dirty bit(/modified bit).

---

 31                               17 16                                   12  11                                              0

tag

set

offset

 

---

TLB is small, fast lookup CACHE memory 

So same concept can be applied as cache

---

why "minimum" ? why not the exact size?

Answer 1

Page size of $4KB$. So, offset bits are $12$ bits.

So, remaining bits of virtual address $32 - 12 = 20$ bits will be used for indexing...

Number of sets = 128/4 = 32 (4-way set)  => 5 bits.

So, tag bits $= 20 - 5 = 15$ bits.

So, option (C).

Comments

Can you please tell why you simply subtracted 5 from 20? Is it because Indexing in set associative memory is done via Tag+Set bits?

---

"4-way set associative means number of lines is 4 in each set." So my question does in TLB each page table entry correspond to a line?

---

yes block size in TLB just correspond to one entry, so 128 entries corresponds to 128 blocks and 32 sets.

---

Is the given data is sufficient to find the entry size of the TLB if yes? then how to find it? and is tag bits included in the entry size

---

@rajat_mahajan this is the how the virtual address will be broken up into:

4KB page defines the offset = 12 bits
32 sets in the TLB defines the set = 5 bits
Remaining 32 - 17 = 15 bits will be used to define tag bits.

---

bro can you explain organization of TLB.

---

@shaik mastan @akash.dinkar2 @magma @srestha
can anyone explain how TLB is organized when it is used as Direct mapped and set-assosiative  ?

---

Dharmendra Lodhi

here people might not notice u, u can ask as a separate question...

---

Don't we need the physical address space to calculate the tlb tag ?

Virtual address space is the process size.

---

One thing I am not sure about; How do we know PTE size is 32 bit? Anyone please help.

---

@Devasish Ghosh This concept is very similar to cache concept from Computer Organization.(Youtube)

In set associative cache we have,

No. of bits to represent a block = No. of bits in Tag + No. of bits in set number

Similarly here we have,

No. of bits to represent page number = No. of bits in Tag + No. of bits in set number

20 = No. of bits in Tag + 5