Question

Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown. The page size is 4KB and page table entry size at every level is 8 bytes. A process \( P \) is currently using 2GB virtual memory mapped to 2GB physical memory. The minimum amount of memory required for the page table of \( P \) across all levels is \(\underline{\hspace{2cm}}\) KB.

Hint:

In multi-level paging, only required page tables are allocated, minimizing memory usage.

Answer 1

Correct Answer: 4108

Step 1: Determine page size and number of pages.
Page size \( = 4 \text{KB} = 2^{12} \) bytes.
Virtual memory used \( = 2 \text{GB} = 2^{31} \) bytes.
\[ \text{Number of pages} = \frac{2^{31}}{2^{12}} = 2^{19} \]

Step 2: Entries per page table.
Each page table entry \( = 8 \) bytes.
Entries per page table:
\[ \frac{2^{12}}{8} = 2^9 = 512 \]

Step 3: Level-wise page table calculation.
Level 3 (Leaf):
Each level-3 table maps \( 512 \) pages.
\[ \frac{2^{19}}{2^9} = 2^{10} = 1024 \text{ tables} \] Memory used:
\[ 1024 \times 4 \text{KB} = 4096 \text{KB} \] Level 2:
Each level-2 table points to \( 512 \) level-3 tables.
\[ \frac{1024}{512} = 2 \text{ tables} \] Memory used:
\[ 2 \times 4 \text{KB} = 8 \text{KB} \] Level 1:
Only one level-1 table is required.
Memory used:
\[ 1 \times 4 \text{KB} = 4 \text{KB} \]

Step 4: Total page table memory.
\[ 4096 + 8 + 4 = 4108 \text{KB} \] % Final Answer

Final Answer: \[ \boxed{4108} \]