The Gateway to Computer Science Excellence
+33 votes
A computer system implements a $40-bit$ virtual address, page size of $8$ $\text{kilobytes}$, and a $128-entry$ translation look-aside buffer ($TLB$) organized into $32$ sets each having $4$ ways. Assume that the $TLB$ tag does not store any process id. The minimum length of the $TLB$ tag in bits is ____.
in Operating System by Veteran (105k points)
edited by | 5.8k views
I have a doubt whether TLB and page table are same?

Can anybody clear this.
@Manoja , Copied from Carl Hamacher 5th Edition,

"The page table information is used by the MMU for every read and write access. Ideally, the page table should be situated within the MMU. Unfortunately, the page table may be rather large. Since the MMU is normally implemented as part of the processor chip, it is impossible to include the complete table within the MMU. Instead, a copy of only a small portion of the table is accommodated within the MMU, and the complete table is kept in the main memory. The portion maintained within the MMU consists of the entries corresponding to the most recently accessed pages. They are stored in a small table, usually called the Translation Lookaside Buffer (TLB)."

Thank you  @Harish Karnam

In this question TLB consists of 128 entries ie, all the virtual addressess are mapped to physical address in TLB itself? So there is no need of page table or whole page table is copied to TLB?

please clear my understanding on this.

See TLB acts as a cache for page table and all the entries includes a copy of the information in the corresponding entry in the page table, So there is no need.

4 Answers

+50 votes
Best answer

Ans $40 - (5+13) = 22$ bits

$TLB$ maps a virtual address to the physical address of the page. (The lower bits of page address (page offset bits) are not used in $TLB$ as they are the same for virtual as well as physical addresses). Here, for $8 \hspace{0.1cm}kB$ page size we require $13$ page offset bits.

In $TLB$ we have $32$ sets and so virtual address space is divided into $32$ using $5$ set bits. (Associativity doesn't affect the set bits as they just adds extra slots in each set).

So, $\text{number of tag bits} = 40 - 5 - 13 = 22$

Following diagram shows how $TLB$ and Cache works:


by Boss (13.6k points)
edited by
Plz explain what is meant by - "VAS divided into 32 using 5 set bits"

VAS divided into 32 using 5 set bits"

means  tlc has 127 total entries which are stored into special format i.e. 

32 rows each have 4 column. so we need only 5 bits to pint any entry of tlb.

Can you share some links,pdfs or some other resources from where to learn these type of questions. I am new to this topic and is finding it increasingly hard to understand!

Thanks in advance! :)

Why to have 4 columns?

We only need 1 entry for one physical page address for one virtual address so why to store it in 4 columns instead of just one?

plz explain arent we suppose to change 8 kilobytes into bits ,then the offset would be 16 correct me if i am wrong
@Sumit that's the concept of associativity which helps in increasing the hit rate.

@Pooja Never. Because memory work at byte level - not bit level. All memory addresses are either byte address or word (a block of bytes) address.
thank you
What would be the size of TLB here...

Is it equal to no of entries x size of a page ?

size of TLB = (no of entries in TLB) * (22 tag bits + frame no bits + extra bits if any)

I have one doubt:

 Since " The lower bits of page address - offset bits- are not used in TLB as they are the same for virtual as well as physical addresses" - in this case, each TLB entry is of (Tag + Frame) bits which equals

(VA - Page offset) bits = 40 - 13 = 27 bits(Each TLB entry has 27 bits)

Among these 27 bits, 5 bits are used to identify set. But in each set, it has 4 columns, so this also should require 2 bits to identify the column. Why are these two bits not considered?

Is my understanding correct?
TLB size doesnot always requires TLB in bits * 2^block size
0 @Arjun sir so while accessing the TLB with our effective address which is the virtual address the tag of the tlb is not just the page number it contains the no of bits according to the TLB addressing scheme like here its set associative right

why 20 bit Physical page no. divided as 18+2(byte offset)? why byte offset req when we have block offset?

@Tuhin Dutta I think to identify a column within a set, each column has to be compared with the tag in the given virtual address.

What is the significance of the quote "minimum length of tag bit" here ? Can tag field go beyond 22 bits here?
I think size of TLB does not include Tag bits.Tag bits are present as part of virtual memory address.

size of TLB = (no of entries in TLB) * ( frame no bits + extra bits if any)
@Prashant Sir,

From the link you provided, I am unable to understand why we are hitting the cache with the virtual page offset in the beginning?

As per my understanding, We generate the physical address first from the TLB lookup( assuming hit) by combining the looked up frame number and the offset bits.


Once physival address is there, we can go to the caching mechanism. The physical address is split as per the cache block size and number of sets. Once cache lookeup is succesful we get the physical address; we combine with the physical offset now and get desired final address.


Please let me know if my understanding is not right
Should not physical address space be mentioned in the question??

Dividing logical address space into sets is bit confusing to understand.
+6 votes

Here is another way to look at it.

The lower bits of page address (page offset bits) are not used in TLB as they are the same for virtual as well as physical addresses.

remaining bits = 40-13=27

So total entries in a page table (let there be one in place of a TLB) = 2^27

So now, we want to map this Page Table to a TLB with 128 entries by the use of a 4-way set-associative mapping.

For mapping purpose,take the Page Table as main memory and TLB as cache memory and the size of a block as x.

So total number of bits for main memory are 27+x.

Now mapping MM 4-way set associatively to CM gives (tag-set-word) as (22-5-x).

So the number of tag bits are 22

by (395 points)
0 votes
Total virtual address size = 40

Since there are 32 sets, set offset = 5

Since page size is 8kilobytes, word offset = 13

Minimum tag size = 40 - 5- 13 = 22
by Loyal (5.8k points)
0 votes


by Junior (987 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,383 users