MIT HOMEWORK QUESTION | MULTILEVEL PAGING |OPERATING SYSTEM

Question

A three-level hierarchical page table is used for a system with a 44-bit virtual address divided as follows:

Field	Bits
1st-level index	VA[43:33] (11 bits)
2nd-level index	VA[32:22] (11 bits)
3rd-level index	VA[21:12] (10 bits)
Page offset	VA[11:0] (12 bits)

 

The system uses 64-bit page table entries (PTEs). A complete page table page is allocated even if only one PTE is used. Assume a sufficiently large physical memory and no paging to disk.

Which of the following options correctly gives the minimum and maximum possible page table overhead, respectively?

---

Options

A. 40 KB and 32 MB
B. 40 KB and 32 GB
C. 48 KB and 16 GB
D. 64 KB and 64 GB

Comments

Total overhead = total space alloted to all the pages and PTs - Total size of entries in all page tables (Not considering page size as it is mentioned that complete Page table or page is allocated even if only 1 PTE used)
= 2^44 - [(2^10)*(2^11)*(2^11) + (2^11)*(2^11) + (2^11)]*8 bytes (64 bits)
= 2^44 - 2^35 - 2^25 - 2^14
= 2^44

---

why it is duplicated?

---

I want to remove the other one becuase that one is way to complicated to understand

---

if so, you can edit the question instead of posting a new one.

---

I dont know i can edit questions also . I am new to this thing

---

Ohk. Try now by clicking "Edit" button available on the earlier question. Then I will delete this question.

We don't agree to post duplicate questions.

---

can you delete this one https://gateoverflow.in/506720/mit-homework-problem-m4-4-c-multilevel-paging-operating-system

because i have send this question in our friends group

Answer 1

Given:
Virtual address = 44 bits
Split: 11 bits (L1), 11 bits (L2), 10 bits (L3), 12-bit offset
Page size = 4 KB
PTE size = 64 bits = 8 bytes
A full page table page is allocated even if only one entry is used.

First compute page table sizes.

Level-1 page table:
Number of entries = 2¹¹ = 2048
Size = 2048 × 8 = 16384 bytes = 16 KB = 4 pages

Level-2 page table:
Same as level-1
Size = 16 KB = 4 pages

Level-3 page table:
Number of entries = 2¹⁰ = 1024
Size = 1024 × 8 = 8192 bytes = 8 KB = 2 pages

Minimum page table overhead:
If only one virtual page is mapped, still one page table at each level is required.

Level-1: 16 KB
Level-2: 16 KB
Level-3: 8 KB

Total minimum = 16 + 16 + 8 = 40 KB

Maximum page table overhead:
When the entire virtual address space is mapped.

Level-1:
Only one table = 16 KB

Level-2:
One table for each level-1 entry
Number of tables = 2¹¹ = 2048
Total size = 2048 × 16 KB = 32 MB

Level-3:
One table for each level-2 entry
Number of tables = 2¹¹ × 2¹¹ = 2²²
Each table = 8 KB
Total size = 2²² × 8 KB = 32 GB

Maximum overhead is dominated by level-3 tables, so it is 32 GB.

Correct answer:
40 KB and 32 GB (Option B)