How does multilevel paging save memory?

Question

I am confused with the concept of the multilevel paging scheme.

Let a 32-bit virtual address and one page is of 4 KiB then I will have 2²⁰ pages/page table entries.
Let one page table entry be of size 4 bytes, so the page table's size is 2²⁰ * 4 bytes.

If I divide the virtual address into 10 | 10 | 12, then what I understood is:

I have a page table directory, which is indexed by the most significant 10 bits of the virtual address, so it has 2¹⁰ entries and points to 2¹⁰ different page tables (that is, on the 2^nd level).
Each 2^nd level table again can be indexed by (the middle) 10 bits and the corresponding entry will hold the actual page frame number.

My questions are:

• Is this correct at all?
• Are the sizes of the page directory and the page table/s the same?
• How does the multilevel paging scheme save memory?

Answer 1

Yep, it's all correct. With only one level of page tables and 4 bytes per entry, the page table would have

4 GiB (maximal physical address space) / 4 KiB (size of one page frame) * 4 Bytes = 4 MiB

and accessing a physical address would be like

(page table entry)->(offset)

To lower the size of this big page table, a multilevel pagin scheme is employed, reducing the size to

2^10 Bytes * 4 + 2^10 Bytes * 4 = 8 KiB

and changing the resolution of a virtual address to a physical address to

(page directory entry)->(page table entry)->(offset)

This saves some bytes (4 MiB - 8 KiB) but has one drawback: one additional memory reference is required to convert a virtual to a physical address. Here, the TLB (Translation Lookaside Buffer) comes into play. It is a (compared to the L1 cache) small cache and stores the association of a virtual address to a physical address in hardware. Special hardware is used here, comparable to a hashtable (std::unordered_map in the C++ standard library), with the difference that it's implemented in hardware and therefore faster.

This is the default 32-bit Paging scheme employed in the x86 architecture. x86-64, PSE, PAE, somewhat change the mechanism with more levels of page tables, bigger page sizes (2 MiB, 4 MiB, and even 1 GiB), and a bigger physical address space (at most 64 GiB with PAE), leading to more levels of page tables. The x86-64's virtual addresses are 48 bits in size, leading to a huge address space per process (several TiB).

---

Note the difference between a page and a page frame. A page is the data, a page frame is the area in physical memory where pages are mapped at. There are systems where page's size = x * page frame's size, where x > 1.