This problem demonstrates a very important concept of how multilevel paging helps us to save page table size in the memory. The virtual address space generally contains a lot of empty pages. However, if we have a single page table, it requires us to store the page table entries for the empty pages us well. This can be avoided in multilevel paging.
The virtual address split is given as follows:
We can infer the following from this split :
- In level 1, there are $2^{10}$ page tables each having $2^{10}$ page table entries.
- In level 2, there is 1 page table having $2^{10}$ page table entries.
Now, it is given that we need to store 5 pages in the physical memory. This means that there will be only 5 useful entries (containing frame number for these 5 pages) in the level 1 page tables. Therefore, in the level 1, will keep only those page tables who have these 5 entries. The rest page tables, have all their entries invalid and need not be stored (their vacancy can be indicated by an invalid bit in outer page). This is how multilevel paging helps us to save the page table size.
Firstly, will find out where the entries corresponding to the code pages are in the level 1 page tables. The code pages begins at address 0 and are two contiguous pages. The entry for these will be the first two entries in the first page table among the level 1 page tables. Since, it has $2^{10}$ entries, the rest will be invalid but we have to store this page table. This is show in the diagram below.
Now, we need to figure out the page table having the entries for data pages. We can achieve this by finding where the starting address of first page pointed by the first entry in second page table in level 1. This can be compared to the given starting address to figure out whether the entries are in page table 1 or in some page table below. We have skipped $2^{10}$ entries of the first page table in this level. This means we have skipped $2^{10}$ pages, i.e $2^{10} * 2^{12} = 2^{22} B$ which is $0x00400000$. Therefore, the page table entries for data pages lie in the second page table of level 1. This is show in the diagram below.
The stack page is clearly pretty below and hence will require some other page table below the first two page tables in level 1 (precisely it is the last page and will require the last page table in this level). We require 3 page tables in the level 1. The outermost page table must also be stored completely. Therefore, in total we require 4 page tables. (3 in level 1 and 1 in level 2).
Also, all the page tables have the same size, i.e. $2^{10} entries * {4}\;Bytes = 4KB$
Therefore, the amount of memory required for storing the page tables of this process is
$4\;page tables * 4KB = 16KB$