Is it possible that the page-table is larger than the physical memory? If so where is the table stored?

Question

Assume you have a 64-bit computer ( which means 64 bit virtual address space ), which has 4KB pages and 4 GB of physical memory. If we have a single level page table as you suggest, then it should contain one entry per virtual page per process.

One entry per virtual page – 2⁶⁴ addressable bytes / 2¹² bytes per page = 2⁵² page table entries

One page table entry contains: Access control bits ( Bits like Page present, RW etc ) + Physical page number

4 GB of Physical Memory = 2³² bytes.

2³² bytes of memory/2¹² bytes per page = 2²⁰ physical pages

20 bits required for physical page number.

So each page table entry is approx 4 bytes. ( 20 bits physical page number is approx 3 bytes and access control contributes 1 byte )

Now, Page table Size = 2⁵² page table entries * 4 bytes = 2⁵⁴ bytes ( 16 petabytes ) !

which is more than the physical memory, so how and where we can store the page table?

thank you!

Answer 1

It is possible to have a page table larger than the physical memory. What you would have to do is to page part of the table to secondary storage.

Some processors actually can do that. They avoid the apparent chicken and egg problem by having separate system and user page tables. The system page tables are mapped to physical page frames while the user page tables map to logical addresses in the system space.

There are probably other ways to implement page tables larger than the physical memory than the one I described.

Answer 2

I have not checked your math, but lets step back and ask a slightly different question, why would you want map the entire possible physical address space?

On a typical CPU with a MMU that supports paging, only a small fraction of the physical addresses that exist address either RAM or MMIO. The rest of the physical address spaced is unused. Typically you would get some sort of exception if you did map those physical addresses not addressing a device to virtual addresses and then try to access them.

Thus in practice the practical size of a page table is constrained by the amount of RAM and MMIO space that can be addressed. If you have small amounts of RAM you don't need a massive page table described in the example. Most of the entries would be invalid.

Conversely, if your system did have a large amount of RAM that consumed most of the physical address space, you'd have more RAM to store the page tables in.

A different way page tables could consume all of RAM is by having multiple page tables or tables that had many virtual addresses mapping to the same physical address, but this question did not concern that scenario.

Answer 3

I'm kind of late to this game, but a few comments and clarifications.

First, the question is slightly (but not terribly) exaggerated for the moment. The reason is that, while most 64-bit architectures allow for future expansion to a 64-bit virtual-address space, there are none that I know of supporting the full 64 bits today (Dec 2018). For example, Xeon servers currently support 48 bits. However, even a 48-bit VA space is sufficient to raise the issue.

The second answer given (by VxWizard), which talks about holes in the physical-address space, seems to me to be missing the point. Since one main point of virtual addressing is to have more VA space than PA, holes in the PA space are irrelevant to the size of the page tables.

Now back to the original problem. Clearly the size of the page tables can be larger than all of physical memory, and clearly that implies that parts of the page table can be paged out. But then how can a TLB miss ever be handled? It might seem that a TLB miss would imply fetching from the page table -- and if the page table is paged out, then you must fetch it from disk. But the pointer that says where in disk to fetch is kept... in the page table, which is on disk!

The reason that this is not infinite recursion is because not the entire page table can be paged out. Part of it -- specifically, the part that tells where the page table itself is -- cannot be paged out. As long as that portion stays resident in physical memory, you're fine.

There are numerous ways of accomplishing this. Multilevel page tables can help, as can separating user and kernel spaces. But the main thing that all of them must satisfy is that you must have enough of the page tables in physical memory so as to be able to find the rest of the page tables on disk.