title: Number of page table index bits in multilevel paging
body: <p>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 :</p>
  
  <p>bits 30 - 31 are used to index into the first level page table <br>
  bits 21 - 29 are used to index into the second level page table <br>
  bits 12 - 20 are used to index into the third level page table <br>
  bits 0 - 11 are used as offset within the page <br></p>
  
  <p>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 ? <br></p>
  
  <p><i> This was a question asked in GATE 2008. </i> <br>
   <strong>My Analysis:</strong>   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. </p>
  
  <p>This analysis somehow doesn't seem right. I am very much confused. Can someone please explain the concepts ?  </p>