Memory overhead in Multilevel paging with TLB

Question

Consider a computer system using 2-level paging with TLB.The logical address supported is 32 bits.The page table is divided into 512 pages each of size 1K.The memory access time is 100ns and the TLB access time 15ns .Page table entry size at 1st level is 2 Bytes and that at second level us 4 Bytes each.

What is the memory overhead of storing the top level page table along with the page of the second level page table for a process?

A)6KB

B)4KB

C)5KB

D)12KB

Comments

pages of PT(p1)	page Size of PT(p2)	page size
512	1K	232-(10+9)
29	210	213

now ,

overhead means extra space we need to access any page. 

PTE of level 1 = 2B

level 1 PTsize = 512*2B = 1KB.

PTE of level 2 = 4B

level 2 PTsize = 1K*4B = 4KB

therefore total overhead = 4KB+1KB = 5KB answer..

 

---

@arvin u took 2nd level page table 10 bits

how u took it?

It is given page size is 10 bit

isnot it?

---

the memory overhead of storing the top level page table along with the page of the second level page table for a process

normally, for addressing a word in the page, we have to atleast fully loaded the outer page table and one page of inner page table and one page of memory ( which the word is present ).

therefore as per question, top level page table means it is outer level and second level page table means inner page table.

 

here, it is saying that page table ( inner level ) itself divided into 512 pages with each page size = 1 K

∴ no.of entries in that page table = $\frac{512*1K}{4}$ = 128 K entries ===> VA = 128 K * 1 K ( for each page ) = 2²⁷.

But in the question it said that, VA is 32 bits ===> contradicting ===> question is wrong.

∴ For going forward, i am assuming that, VA = 27 bits and Page size = 1K

 

No.of entries in the outer level paging = ( no.of pages in the first level page table ) = 512

 ===> size of outer level page table = 512 * 2 B = 1 K

∴ Total overhead = 512 K ( inner level page table ) + 1 K ( for outer level page table ) = 513 K

 

But in the question, they want only, top level page along with the page of the second level page table for a process = 1 K + 1 K ( atleast one page of second level is associated ) = 2 K

Answer 1

 <------------------LA=32------------->

9 bits (first level)

10 bits (Second level)

13bits (offset)

First level Page Table Size = 2^9 * 2B(page table entry size)  = 1KB

Second level Page Table Size = 2^10 *4B(page table entry size)  = 4KB

Total = 5KB

Comments

question said that page table is divided into 512 page means that no of entries in the page table that means it has 512 pages

---

Here outer level page table contain 512 pages

And each entry of outer page table is 4B

So  total size of outer page table = 2^9*4B = 2^13B

And we stop for dividing page table if a page table can be fit into one page or frame so, page size =2^13 B

So block offset = 13bits

And VA = index at 1st level + index at 2nd level + block offset

So 32= 9+ 2nd level + 13

So 2nd level index = 10 bits

---

I am confused with this question, in question page size is given as 1K and here, it has been calculated as 2^13B , ???

Answer 2

p1	p2	d
9	10	13

P1= number of pages in 2nd level page table

P2=number of bits required to represent page size of page table

d= bits required for frame offset

total size =2^9 *2 +2^10 *4 =1KB+4KB=  5KB

Comments

i think it should be like this:-

   P1       P2        P.O

   9         8          15

??           

---

refer my comment above