Hierarchical Paging

Question

Suppose I have a system with 32-bit logical and 16-bit physical address spaces, and the page size is 512 bytes. For simplicity, ignore the valid/invalid bits in the page table.

How many sections will the logical address be divided and how many bits will each section have? The logical address will be divided into three sections, one section for the outer page, one for the inner page, and one for the offset. The outer page section contains 13 bits. The inner page contains 10 bits. The offset section will contain 9 bits. Is this right?

Will the structure of the page table have 2 levels? How would I convert a logical address into a physical address?

Answer 1

I think you need more than 2 page table levels. Here's what the page tables on AMD-64 (x86_64) look like. (This picture is from an article by Frank van der Linden about porting NetBSD to AMD-64.)

Each page is 4K-byte and the system is byte-addressable so you need the bottom 12 bits of the virtual (logical) address to index into the physical page. The number of bits needed for each level above that is calculated as follows:

The size of the pages is 4K-byte, and the page table entries are 8 bytes on AMD-64, so you can fit 512 page-table entries per page, so you need 9 bits of logical address for each level of the table.

Walking the tree works like this. There is a register with a pointer to the top of the PML4 page. At each level you take the pointer to the top of the page, take 9 bits of logical address, multiply by 8, and use that as the byte offset into the page. You read out the 8-byte page table entry, which gives you the pointer to the top of the page 4K-byte page table at the next level deep in the tree.

In your case, each page table entry (p.t.e.) needs to have space to store a physical pointer to a 512-byte aligned page. Your physical addresses are 16 bits and you know that the bottom 9 bits are 0s (because your pages are 512-byte aligned), so each page table entry needs to be at least 7 bits, even leaving a bit for valid/invalid. And the problem even told you to not worry about control bits. So I think you can get away with a 512-byte page table containing 512-entries. It might be more realistic to assume that you would need room for expansion (either to increase the number of control bits or to increase the size of the physical address space) so you might want each p.t.e. to be 2 bytes, and then each page table could contain only 256 entries.

It is the number of p.t.e.s per page that determines the number of logical address bits you will use to access the inner pages. So 9 bits from the calculation we just did. (If you are assuming that each page table entry requires 2 bytes instead of 1 byte, then you could only fit 256 entries in a page table, and you would take 8 bits of logical address.)

So in your case you have 9 bits of offset at the bottom, and then multiple levels with 9 (or 8 depending on your choices) bits each. So 2 levels of table (+ the offset) only covers 27 (or 25) bits of your logical address. I think you need one more level. The top level page will not be full because you only have 5 (or 7) bits left at the top of the logical address.