So now, let's talk about how big the two-level page-table gets.
Say we have a 32-bit address space and a 4 kilobyte page.
Let's say we're using a 1024-entry outer page table and
a 1024 entry inner tables.
There can be many of them, up to 1024 of them.
And let's say that the page table entry's 8 bytes.
Assuming that our page table entry is 8 bytes and that we have a program that
uses virtual memory at the beginning of memory from addresses 0 through this,
and that the top of the memory from address this to the end,
let's look at what the flat page table size will be and what our two-level
page-table size will be, with this split between the inner and outer page-tables.
The flat page table size will have one entry for each possible page.
So we have 2 to the 32nd pages, 2 to the 12 bytes in each page.
So we have 2 to the 20th entries.
And the total size will be 8 times this, which ends up being 8 megabytes.
For the 2-level page table,
we need to figure out how many inner page tables do we have here and here.
Our address is now composed of a 12 bit offset,
to index into the 4 kilobyte page,
a 10-bit outer page number and a 10-bit inner page number.
They need to add up to 32, which they do.
So we know that we need to have the outer page table, and
it's size will be 2 to the 10th entries times 8 bytes
per entry here, which ends up being 8 kilobytes for the outer page table.
Now the question is, which of these entries need to point to actual inner
page tables and which ones can simply say that there is no inner page table?
To figure that out, we need to see which of the inner page entries do we need
to actually point of pages of memory and which ones can simply be empty.
Thus we will decompose these addresses.
This part of the address is the page offset.
The upper part is the page number and
we need to split this 20 bit page number into 10-bit groups.
So let's just write it out.
We have 0000, these are the two zeros.
Another hex digit for 0, the 1, and the 0.
This is the outer page number, this is the inner page number.
As you can see,
all of the addresses in this range have the same outer page number.
We start at 0, we end at 0.
So only the entry number 0 here needs to point to an actual inner page table.
For this address range, the page number goes from FFFF0 to FFFFF.
These page numbers also have the same outer page number.
It's all 1s.
So only the last outer page table entry
needs to point to an actual inner page table.
Note that there are a 1,024 entries here,
only 2 of which point to inner page tables.
So, there is a 1,022 entries that simply say nothing.
So we have 2 inner page table times, what's the size of one of them?
Well the size is 1024 entries times 8 bytes per entry,
which gives us a total of 16 kilobytes.
Adding the size of the outer page table, we get only 24 kilobytes.
So the size of a 2-level page table for this application is
only 24 kilobytes compared to 8 megabytes for the flat page table.
And this is why multilevel page-tables are almost exclusively using today's
processors especially when we have a 64 bit address space, because for a 64
address space, the flat page table size would be too large to fit in memory.
But the multi level table will fit mostly because the outer
most page table will have many empty entries.
So we will need very few of these inner page tables.