How does multi-level page table save memory space?

Question

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 ?

Fann

All page table entries don't have to be present in memory at the same time. Just the top-level dictionary, the rest can be swapped out to the disk and loaded and used when needed (if ever). So the saving is (in my opinion) in the fact that the page map occupies modest amount of memory – Endpaper

Why 10/8 is done during the calculation of size of first-level page table? – Mccullum

Answer 1

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 .

Siret

Well explained. I was wondering what will be the content of page table at level 2. I understand, in level 1 the contents are frame number and some bits (dirty, modified, etc). – Cargian

Can you tell me why offset is being considered as 12 here? Isn't the offset supposed to be 16 bits given 64K size. Therefore it would have only 16 bits for page number allocation. If we divided them equally among two pages. Then size of first page would be 2^8 * 4 bytes and the same for second page. The total would then be 2* (2^8 * 4) = 2048 bytes which is way less compared to 2^16 * 4 bytes. – Latta

@Latta page size = 4KB, 12-bits offset is used to access a specific address inside the 4KB range of addresses. 4KB = 2^12, so we need only 12-bits for the offset – Inverson

@IbrahimAmer But the author of the questions pointed out that page size is 64KB in his case. Why did we change it to 4KB? – Colchicine

Answer 2

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.

Gouda

I was wondering what will be the content of page table at level 2. I understand, in level 1 the contents are frame number and some bits (dirty, modified, etc). – Cargian

Answer 3

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.

Scifi

Answer 4

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.

Phrase

Why 10/8 is done during the calculation of size of first-level page table? – Mccullum