How does multi-level page table save memory space?

I am trying to understand how multi-level page table saves memory. As per my understanding, Multi-level page table in total consumes more memory than single-level page table.

Example : Consider a memory system with page size 64KB and 32-bit processor. Each entry in the page table is 4 Bytes.

Single-level Page Table : 16 (2^16 = 64KB) bits are required to represent page offset. So rest 16-bits are used to index into page table. So

Size of page table = 2^16(# of pages) * 4 Bytes(Size of each page table entry) = 2^18 Bytes

Multi-level Page Table : In case of two-level page table, lets use first 10-most significant bits to index into first level page table. Next 10-bits to index into second level page table, which has the page number to frame number mappings. Rest 12-bits represents the page offset.

Size of a second-level page table = 2^10 (# of entries) * 4 bytes(size of each entry) = 4 KB

Total size of all the second-level page tables = 2^10 (# of second-level page tables) * 4KB (Size of each second-level page table) = 4 MB

Size of first-level page table = 2^10(# of entries) * (10/8) Bytes (Size of each entry) = 1.25 KB

Total memory required to store first and second level page tables = 4 MB + 1.25 KB

So we need more memory to store multi-level page tables.

If this is the case, How does multi-level page tables save memory space ?

1. In singlelevel pagetable you need the whole table to access even a small amount of data(less memory references). i.e 2^20 pages each PTE occupying 4bytes as you assumed.

Space required to access any data is 2^20 * 4bytes = 4MB

2. Paging pages is multi-level paging.In multilevel paging it is more specific, you can with the help of multi-level organization decide which specific page among the 2^20 pages your data exists, and select it . So here you need only that specific page to be in the memory while you run the process.

In the 2 level case that you discussed you need 1st level pagetable and then 1 of the 2^10 pagetables in second level. So, 1st level size = 2^10 * 4bytes = 4KB 2nd level we need only 1 among the 2^10 pagetables = so size is 2^10 * 4bytes = 4KB

Total size required is now : 4KB + 4KB = 8KB.

Final comparision is 4MB vs 8KB .

Here is a primary advantage of multilevel page tables:

> First, chop up the page table into page-sized units; then, if an entire page of page-table entries (PTEs) is invalid, don’t allocate that page of the page table at all.

Source. (Section 20.3)

Thus the amount of memory needed for the page table is not dictated by the size of the address space, but by the amount of memory that the process is using.

In addition, the page of page table entries can itself be paged if physical memory gets full - only the page directory needs be always present in memory.

To add to Sai's answer, there really one idea that must be stressed here: you don't need the entire page table loaded into main memory - only the part that gets you where you want to go. This compensates your correct intuition that a multi-level page table needs at least as much capacity as a single-level page table (after all, you need to store a mapping for all virtual addresses, regardless of the table style).

It's also good to note that multi-level paging actually emerges from wanting to apply the above principle (instead of the reverse, i.e. applying the principle because you want to use multi-level paging). The entries of a single-level table are stored in pages themselves, and in a single-level model, those pages could fill up one big chunk of memory; that way, you only need the base address to index your table. However, now try to pull out the pages of entries you don't need: as a natural consequence, we'll need a way to still be able to refer to all the pages of entries, even though they're no longer present as one big chunk. Hence, a top-level page table appears, and we have multi-level paging.

Now simply write the pages we pulled out to disk, and only retrieve them for later use. That way, if the program really only needs one final-level page table entry, we store the entire 4 MB in entries to disk, except for the 4 kB + 4 kB we actually need. That's a lot of RAM saved.

Multi-level tables are primarily needed because of the memory structure in Intel-land.

Let's suppose you have a 32-bit system and you divide the address space so that the top half is reserved to the system and the lower half is for user addresses.

With such a division, you would need 2GB worth of contiguous page table entries in every user page table to reach the system addresses.

The old VAX to a simple approach to this. It divided the 4GB address space into 4 regions (2 user, 1 system, one unusable). The three usable areas had their own page table.

Each region had its own page table. Because there was a dedicated system address space, the user page tables could be virtual addresses so they would not require contiguous memory.

The first phase of address translation was to look at the 2 high order address bits to select the page table to use.

Instead of having separate page tables, Intel-land breaks the page table up. That lessens the problems of (1) needing contiguous memory for the table; (2) requiring the page table to span the full address space; (3) allows the definition of a kernel addresses that can be shared by all processes.