Given :
- Virtual address $\text{(VA)}= 39$ bits
- Page size $= 4 \text{KB}$
- Physical address $\text{(PA)} = 2 \text{GB}$
- Page table entry size $\text{(PTE)} = 8 \text{B}$
- Three level pages tables with address division $(9,9,9,12)$
Three level pages tables with address division $(9,9,9,12)$ means:
- $9$ most significant bits for indexing into the level-1(outer level),
- $9$ bits for the level-2 index,
- $9$ bits for the level-3 index, and
- $12$ bits for the offset within a page.
The entries of the level-1 page table are pointers to a level-$2$ page table, the entries of the level-$2$ page table are pointers to a level-$3$ page table, and the entries of the level-$3$ page table are PTEs that contain actual frame number where our desired word resides.
$9$ bits for a level means $2^9$ entries in one-page table of that level.
For our process $P :$
$P$ is using $2\;\text{GB}$ of its VM. The rest of its VM is unused.
$2\;\text{GB}$ VM will have $2\;\text{GB} / 4\;\text{KB} = 2^{19} \;\text{Pages}.$
But level $3$ page table has only $2^9$ entries. So, one-page table of level $3$ can point to $2^9$ pages of VM only, So, we need $2^{10}$ level-$3$ page tables of process $P.$
So, at level-$3,$ we have $2^{10}$ page tables, So, we need $2^{10}$ entries in Level-$2$ But level $2$ page table has only $2^9$ entries, so, one-page table of level $2$ can only point to $2^9$ page tables of level-$3$, So, we need $2$ level-$2$ page tables.
So, we need $1$ Level-$1$ page table to point to level-$2$ page tables.
So, for process $P,$ we need only $1$ Level-$1$ page table, $2$ level-$2$ page tables, and $2^{10}$ level-$3$ page tables.
Note that All the page tables, at every level, have same size which is $2^{9} \times 8\;\text{B} = 2^{12}\;\text{B} = 4\;\text{KB}$
$($Because every page table at every level has $2^9$ entries and Page table entry size at every level is $8\;\text{B})$
So, in total, we need $1+2+2^{10}$ page tables $(1$ Level-$1, 2$ Level-$2, 2^{10} $ level-$3),$ and each page table size is $4\;\text{KB}$
So, total page tables size $= 1027 \times 4\;\text{KB} = 4108\;\text{KB}$
So, the answer is $4108.$
NOTE :
In this question, in place of Multilevel paging, If we had used Single Level Page table (also known as Flat level page table OR linear page table), then size of page table would be $1\;\text{GB}.$
Single Level Page Table :
Single-Level Page Tables are single linear array of page-table entries (PTEs). Each PTE contains information about the page, such as its physical page number (“frame” number) as well as status bits, such as whether or not the page is valid, and other bits. the $ith$ entry in the array gives the frame number in which the $ith$ page is stored.
- Virtual address(VA) $= 39$ bits
- Page size $= 4\;\text{KB}$
So, number of pages in Virtual address space (VAS) of each process $ =2^{39}B / 4KB = 2^{27} $
So, we need $2^{27} $ entries in the page table. Each PTE size $= 8\;\text{B}$
So, size of page table for the process $= 2^{27} \times 8\;\text{B} = 1\;\text{GB}$
NOTE that Single level paging CANNOT take advantage of the unused space by the process. The single level page table needs one entry per page. Furthermore, since the process has a very sparse virtual address space, so, the vast majority of these PTEs would simply be marked invalid. BUT space taken by single level page table will be 1GB only. It only depends on the virtual address space, NOT depend on the used memory of process.
A Common Mistake that students make :
In this question, if in place of Multilevel paging, If we had used Single Level Page table, then what would be size of page table ??
The mistake is that some students will consider $2\;\text{GB}$ memory that the process is using, and will get answer $(2\;\text{GB} / 4\;\text{KB}) \times 8\;\text{B} = 4\;\text{MB}$ which is wrong.
Remember that the CORE reason why we use multilevel paging in place of single level paging is that we want to reduce size of page table by taking advantage of unused space of process and making most entries in the outer level page table as invalid entries.