mutli level page table

Question

There is 4 level page table and has following information

64 bit virtual address space

64 kb page size

8 byte page table entry size

program uses only addresses 0...4GB

if page number split equally 4 level page tables uses ......KB?

Comments

it is clearly written there what i m asking.

here kb=kilobyte

---

sorry, but small b denote bit not byte..

---

k dude here it is byte ..

Answer 1

Program uses 4Gb= $2^{32}$

Offset= 16 bit and for page number we can use 48 bits

Now pages number is split equally so we have 12|12|12|12

Page size is 64 KB so number of pages a program can have is $\frac{2^{32}}{2^{16}}=2^{16}$

Number of 4th level page table = $\frac{2^{16}}{2^{12}}=2^{4}$

1 single 3rd level page table

1 single 2nd level page table and

1 single 1st level page table

so total space = $2^{15}+2^{15}+2^{15}+2^{4}*2^{15}=19*2^{15}$

approximate value is 608KB

and if you are asking size of single page table then = 32 Kb

BONUS

if we use single level paging then total size= $2^{48}*2^{3}=2^{51}$ huge overhead

if we use 2 level paging of equal page no 24|24 then total size=$2^{27}+2^{27}=2^{28}$=256MB

3 level paging of 16|16|16 total size = $2^{19}+2^{19}+2^{19}=2^{21}$=2MB

hence 4 level paging is useful

Comments

your answer is near to right ones..

Number of 4th level page table . what does it means?

And which is 4th level ...msb side or before offset?

 

(if possible give reference to learn and solve these types of questions)

---

12|12|12|12|16

1st level|2nd level|3rd level|4th level|offset

Number of 4th level page table . what does it means?

one page table can have maximum $2^{12}$ entries (because we divided page number in equal pages)

and question says that maximum process size can be 4 GB and page size is 64KB

so each process is divided into pages of 64KB each hence of 4GB process, number of pages =$\frac{2^{32}}{2^{16}}=2^{16}$ pages

since one page table can hold only $2^{12}$ so we need 2$2^{4}$ page tables at 4th level

I strongly recommend to study Multilevel paging from Galvin and then try to solve following question

http://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html