2
$\begingroup$

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?

Improve this question
$\endgroup$
5
$\begingroup$

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.)

Usenix AMD-64 page-table picture

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Actually, the size of a page table/node at each level need not be the same as the base page size. E.g., ARMv7 uses 1KiB second level "page tables" and a 128 byte to 16 KiB first level--most significant virtual address bits--table (for process-specific addresses; a different 16 KiB table is used for system-wide addresses). ARMv7 uses 4 KiB base pages. (This ignores more academic variations like guarded page tables.) $\endgroup$
    – Paul A. Clayton
    Jun 9 '13 at 23:22
  • $\begingroup$ Good point. Also x64_64 lets you set bits in the intermediate page table entries so you can use large (2M) and huge (1G) pages at the next level down. The basic rule still stands though: the number of logical address bits used by the next level of the hierarchy is the log-base-2 of the number of p.t.e.s that fit in the page. (Or log-base-2 of the page size for the leaves.) $\endgroup$
    – Wandering Logic
    Jun 10 '13 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.