How to calculate page table size?

18
votes

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.

3
virtualvirtual-memory
what have you tried already? where are you stuck? SO is not a "solve my homework"-page. – Femaref
@Femaref: I have updated my question. – Jake
@sarnold: I have updated my question. – Jake
@sarnold: do you know how to solve this question ? – Jake
Sorry, not well enough to give an answer. I can suggest that you consider two, three, or four layers of pagetables to try to minimize the amount of overhead to actual storage ratios... – sarnold

3 Answers

33
votes

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!

10
votes

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

0
votes

A little bit of clarification for those who might wonder, since I did not find the clear definition in CSAPP and came confusing when I was studying. Physical Page Number (PPN) refers to which page this PA is in. If PPN = 0, then this PA is in the 0th page table, if PPN=11, then the PA is in the 3rd table. One trick is that number of bits of an offset determines the size of that location. If page offset is 14 bits then the size of a page is 2^14 unit of that location(here is per PTE). Correct me if I'm wrong.