How to calculate page table size?

Question

Given : 64 bit virtual byte address, 16 KB pages, 32-bit physical byte address.

What is the total size of page table on this machine, assuming that the valid, protection, dirty and use bits take a total of 4 bits and all virtual pages are in use.

So far I know the total number of page table entries : 2^64 / 2^14 = 2^50, but am not able to understand how to find the size of each entry.

Each entry does contain 4 bits as said in the question, but can the size rest of the entry be found from the physical byte address? I'm confused in this part.

Thanks.

Answer 1

You have a 16 KB page size = 2^14, therefore you need 14 bits for the page offset. Out of the 64 bit virtual address, if you take out this offset, you'll be left with 50 bits. This implies that you have 2^50 entries in your page table.

Further, since your physical address is 32 bits, and the offset makes up 14 bits out of this 32 bits, you are left with the 18 bits that has to come from the page table.

Out of these 18 bits, 4 bits are your valid, use, etc.

Anyway, the per entry, the bits used = 18

Total memory for the page table (this is per process, so you'd have to multiply it by the number of processes if that's specified) = 2^50 * 18 bits

Answer 2

See below one method of calculating page table size:

1. First get page offset by calculating log2(page size in bytes). In your example, page size is 16 KBytes, so log2(16*2^10) is 14; that is, page offset is 14 bits.

2. Then, calculate Physical Page Number (PPN) size by subtracting page offset from total number of bits allocated for physical address. Since in your example, physical address is 32-bit, PPN = 32 - 14, or 18 bits.

3. Now you can calculate Page Table Entry (PTE) size by adding valid bit, protection bit, etc. to the calculated PPN. This value will be the total number of bits required per page entry. In our example, PTE will be 22 bits.

4. One last piece of information we need is the number of page entries in the page table. We can get this by subtracting page offset from the total number of bits we have for the virtual page number; that is, 64 - 14 = 50 i.e. we need 2^50 entries to represent the full range of the virtual addresses.

So the total page table size comes up to 2^50 * 22 bits, which comes around to be 2.75PB. Since this is a lot to keep in memory, and will probably be expensive and slow, modern processors use Translation Lookaside Buffer (TLB) as a cache for recently used page entries.

Hope this helps!