Number of page table index bits in multilevel paging

Question

A processor uses 36 bit physical addresses and 32 bit virtual addresses with a page frame size of 4 KBytes. Each page table entry size is of 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows :

bits 30 - 31 are used to index into the first level page table
bits 21 - 29 are used to index into the second level page table
bits 12 - 20 are used to index into the third level page table
bits 0 - 11 are used as offset within the page

The number of bits required for addressing the next level page table ( or page frame ) in the page table entry of the first , second and third level page tables are respectively ?

This was a question asked in GATE 2008.
My Analysis: The maximum number of page frames = (physical address size) / ( page size ) = 2^36 / 2^12 = 2^24. Thus, 24 bits will be enough to index the page numbers in the 3rd level page table. Now we have to find out how many page tables will be there in the 3rd level. Its given that 9 bits are used to index into the 3rd level page tables. So there are 2^9 page tables in level 3. That means 2^32 virtual space is contained in 2^9 page tables so entries per page table= 2^32/2^9 = 2^23. So 23 bits are required in an l2 page table entry to index the entries of a particular page table in 3rd level page table. 2^9 page tables are there in L2 from L1 page table we need to get to any one of these 2^9 page tables. So 9 bits are required in L1.

This analysis somehow doesn't seem right. I am very much confused. Can someone please explain the concepts ?

Sovran

Answer 1

At first we have physical address of 2^36, and page size is 2^12. Hence 2^24 should be the number of pages. and you figured that right.

Since given 9 bits for 3rd level page table, ie 2^9 and then 4 bytes per entry, so 2^11. Now 2^36/2^11 would give 2^25. Hence 25 bits (25 bits at second level table).

Now again given 9 bits for second level page table. so the same logic applies again 2^36/2^11, which again is 2^25.(25 bits at first level table).

hence the answer must be 25,25,24

One thing that you have to understand is, that though virtual address space is 2^32, we need to map the entire 2^36 entries and not 2^32.Also, each page can take care of 2^9 * 2^2, and you didn't consider this 2^2 as well. The same thing holds at the higher level as well

You should have a look at this question and this wikipedia entry, especially the figure.

Chef

I have found this explanation at gatementor, which is also very insightful. – Chef

Answer 2

In this question, there are 36 bits of physical memory, out of which 12 bits are designated for the offset. The offset is not going to change in any level (since it is the size of the page). Therefore in any level there will be 24 frame bits required for the page table. Since there are 36 bits of physical memory, you cannot increase the physical memory size by increasing the number of bits in the page table.

Natoshanatron