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

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!