1,929 views
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 ?

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.

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 22 entries are  present into the first level page table of size 29 ?

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....

both question are different .