Why using hierarchical page tables?

Question

I'm learning the Linux kernel and reading the book The Linux Kernel.

Can anybody explain why can't we just use the table which maps directly between logical and physical memory instead of the tree-like multilevel structure?

Added:

The total number of entries needed is fixed, so I assume that it's more space wasting to store a complicated structure than a simple one.

Solution 1

You will appreciate the space optimization of multi-level page tables when we go into the 64-bit address space.

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

16 petabytes per process is a very very huge amount of memory.

Now, if we page the pagetable too, ie if we use multi level page tables we can magically bring down the memory required to as low a single page. ie just 4 KB.

Now, we shall calculate how many levels are required to squeeze the page table into just 4 KB. 4 KB page / 4 bytes per page table entry = 1024 entries. 10 bits of address space required. i.e 52/10 ceiled is 6. ie 6 levels of page table can bring down the page table size to just 4KB.

6 level accesses are definitely slower. But I wanted to illustrate the space savings out of multi level page tables.

Solution 2

http://en.wikipedia.org/wiki/Page_table#Multilevel_page_table is to overcome the Inverted page table's pitfalls.

Comments

[Determinant]

Could u plz explain the detail on the space cost of paging?

[Pavan Manjunath]

@ymfoi I've completely rephrased my answer to explain you clearly the space optimizations.

[IcyFlame]

Hello, @PavanManjunath. I am studying an operating systems course and this obviously came up in class. I am still confused about the advantage that multi level paging offers. Please explain this: 1. Is there an underlying assumption that the physical memory also uses a 64 bit address space? 2. Can you do the calculation for two level paging so that the gradual improvement is visible? Thanks for the above answer! 😁

[hailstone]

I think using multilevel paging does not save the potentially large memory space used by the page table if the program actually uses all the 2^64 virtual address space. Instead, it removes the need to allocate a huge page table contiguously upfront, and also allows the possibility to lazily create the mappings when needed.