overhead of maintaining page-table

Question

consider a system using 3-level page-table where it uses first 2 bit to index into first level page-table, 9 bit to index into second level page table , 9 bit to index into third level page-table.  processor uses 36 bit physical address and 32 bit virtual address . each page-table entry is of size 4 bytes. calculate total overhead for the page-table ?

Answer 1

Given three level page table,

 2    ||     9     ||     9   ||    12   ||

PTE size =  4B

Page Table Size = No.of entries in page in page table * entry size

PTS of 1st level page table = $2^{2}* 4B = 16B$

PTS of 2nd level page table =  $2^{9}* 4B$ and we have  $2^{2}$ 2nd level Page tables.

So PTS of 2nd level page table =  $2^{9}* 4B * 2^{2}  =  8KB$

PTS of 3rd level page table  =  $2^{9}* 4B $ and we have  $2^{2}* 2^{9}$ 3rd level page tables.

So PTS of 2nd level page table =  $2^{9}* 4B * 2^{2} * 2^{9} = 2^{20} * 4B = 4MB$

So Total overhead = 16B + 8KB + 4MB $\approx$ 4MB.  

Comments

At any given time, no. of page tables at level j is equal to the no. of entries in the level j−1, right ?

So, how many total 3rd level page tables are there ?

---

2^11 entries in 2nd level PT so no of page tables at level 3 = 2^11 ..

---

@Prabhanjan. If there are 2 bits at 1st level then should we assume that only 2 bits are used to offset into the page table? Its possible that only 2² entries are  present into the first level page table of size 2⁹ ?

Or we shouldnt assume that unless page size is specified?

---

yes 2^2 entries are there in first level page table and third level PT deals with Page size .
like first level page table points to second level , second level to third level , third level to pages....

Answer 2

check this link. https://gateoverflow.in/490/gate2008_67?show=61309#c61309

Comments

both question are different .

---

yes,but will help you.