Consider a three-level page table to translate a 39-bit virtual address to a…
2021
Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below:
The page size is 4 KB = (1KB = 210 bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2 GB (1 GB = 230 bytes) virtual memory which OS mapped to 2 GB of physical memory. The minimum amount of memory required for the page table of P across all levels is _________ KB
Attempted by 78 students.
Show answer & explanation
Correct answer: 4108
Key idea: use only the page-table pages that are required to map the 2 GB of used virtual memory. Address bits split and sizes determine entries per table.
Virtual address split: 9 | 9 | 9 | 12 (three index levels and a 12-bit page offset).
Page size = 4 KB (2^12 bytes); PTE size = 8 bytes. Entries per page table = 4096 / 8 = 512 entries.
Process uses 2 GB = 2^31 bytes. Number of pages = 2^31 / 2^12 = 2^19 = 524,288 pages.
Compute required page-table pages from the leaf upward (minimum allocation assumes only those page-table pages that map used pages are present).
Level-3 (leaf) tables: each Level-3 table maps 512 pages, so number of Level-3 tables = 524,288 / 512 = 1,024. Memory = 1,024 × 4 KB = 4,096 KB.
Level-2 tables: each Level-2 table has 512 entries (can point to 512 Level-3 tables). Number needed = ceil(1,024 / 512) = 2; memory = 2 × 4 KB = 8 KB.
Level-1 table: has 512 entries and needs to point to 2 Level-2 tables, so a single Level-1 table suffices. Memory = 1 × 4 KB = 4 KB.
Total minimum page-table memory = 4,096 KB + 8 KB + 4 KB = 4,108 KB.
Answer: 4,108 KB.
A video solution is available for this question — log in and enroll to watch it.