Search code examples
operating-systempagingvirtual-memorypage-tables

Hierarchical paging with 2 levels

Consider a paging system with the page table being stored in memory. The logical address space used is 32 bit and the page size is 8KB. This will result in a very large page table(s) and therefore the system uses hierarchical paging with two levels. The number of entries in the outer page table is 256.

Specify the number of bits in each of the three fields composing the logical address namely, the outer page, the inner page, and the offset.

I found some information on finding the page offset, Page offset = log2(page size in bytes), so for this case, it would be 13, but I haven't found much information on how to find the number of bits for the outer page and inner page. Can anyone shine some light on this problem for me? Thank you.

Solution

  • I might not be entirely correct, but since VPN to PPN translation is one of my favorite parts from OS, I decided to share my understanding. Maybe this picture can help to understand how is virtual address translated in the physical address. enter image description here In this example page directory contains 1024 entries, so you will need 10 bits, to be able to define which entry you need. This entry contains address of the inner table. Then, as the inner page table also contains 1024 entries, once you know the address of it, similarly you still need to find the index of its entry which holds the physical page address. So next 10 bits are used for calculating that index. Finally, when the page table entry gives you the physical address of the page, offset gives the exact physical address. If this is not very clear I can go into more details.

    In your case, as you have 8KB pages, as you said last 13 bits will be used to calculate the offset. If the outermost page table contains 256 entries then you will need 8 bits (log2(256)) to be able to determine the index of its entry. Then it depends on the number of the entries of the inner table. Or if the size of the entry is defined, the number of entries can be calculated from it. If we assume that left 11 bits are entirely used for the inner table, than it would have to contain 2048 entries, as based on my understanding one instance of page table fits and fills one physical page.