An Intel 64 bit CPU uses a four-level hierarchical page table. Each of the four levels of the page table can contain 512 entries, and the page table size is 4KB. You should be able to see that it cannot actually address 2^64 bytes of virtual memory. If a process on the system used 12MB of text, 5MB of heap and 7MB of stack, calculate the page table size, the number of page table entries required and the number of second level page tables.
Disclaimer: This question is not from an academic assessment. It is a past paper question in preparation for an examination.
If the page table size is 4096 bytes then $\log_2(4096) = 12$. Thus, the offset is 12 bits. Since there are 4 levels in this page table and each level can support 512 entries, the index into each entry is $\log_2(512) = 9$. Thus, you have 4x 9 bit indexes in the virtual address and a 12 bit offset.
One question arises: $9 * 4 + 12 = 48$ bits. But we have 64 bit virtual addresses? What happens to the other 16 bits? I would assume these are zeroed as the 16 most significant bits. Is that correct?
If this is true, does that mean this paging system can address 2^36 pages of virtual and physical memory, and therefore, it can address at most 2^48 bytes of virtual and physical memory. Is that correct?
Under the assumption outlined above: 12MB of text requires 3072 pages, 5MB of heap requires 1280 pages and 7MB of stack requires 1792 pages.
We know that the address space looks like this:
|----------| 2^36
| Stack | (Stack expands down)
| |
| |
| |
| Heap | (Heap expands up)
| Text |
|----------| 0x0
Since the stack is at the top of the address space, it must have it's own second level page table. However, the program text and heap are at the bottom of the address space. Since each second level page table can address 512GB of memory (512^3 * 4096) the program text and heap can share a second level page table. Then, since each third level page table can address 1GB (512^2 * 4096) the program text and heap can share a third level page table too. Thus, we have 18 page table entries. Since this is a 64 bit architecture, each page table consumes 64 bits, and therefore the size of the page table is $18 * 512 * {64 \over 8} = 72KB$.
4th level can address $512 \times 4096$ bytes,
3rd level can address $512^2 \times 4096$ bytes,
2nd level can address $512^3 \times 4096$ bytes,
1st level can address $512^4 \times 4096$ bytes.
L1 L2 L3 L4
2^32 |---|--->[---]--->[---]--->[---] }
|---| --->[---] } 7MB STACK
|---| --->[---] }
|---| --->[---] }
|---|
|---|
|---|
|---|
|---| L4
|---| |->[---] }
|---| |->[---] } 5MB HEAP
|---| L2 L3 |->[---] }
0 |---|--->[---]--->[---]--->|
|->[---] }
|->[---] }
|->[---] } 12MB TEXT
|->[---] }
|->[---] }
|->[---] }
Key [---] Level in Page Table
---> Pointer to Lower Level Page Table
