GATE CS 2003 Q79 — Memory Management and Virtual Memory

To find the total memory required for the page tables, we first determine the size of each page table level and identify how many tables of each level are needed.

1. Size of a Page Table:

• The first-level page table is indexed by the 10 most significant bits (MSB), meaning it contains $2^{10} = 1024$ entries. Since each entry is $4$ bytes, its size is $1024 \times 4\text{ bytes} = 4\text{ KB}$.
• Each second-level page table is also indexed by 10 bits, containing $2^{10} = 1024$ entries. Its size is similarly $1024 \times 4\text{ bytes} = 4\text{ KB}$.

2. Number of Second-Level Page Tables Required:

We analyze the 10 MSBs of the virtual addresses for the given pages to see which entries of the first-level table are active:

• Code pages: Starting at $0x00000000$ and $0x00001000$.
  The 10 MSBs for these addresses are $0000000000_2 = 0$. Both pages share the first-level entry at index $0$, requiring 1 second-level page table.
• Data pages: Starting at $0x00400000$ and $0x00401000$.
  The 10 MSBs for these addresses are $0000000001_2 = 1$. Both pages share the first-level entry at index $1$, requiring 1 second-level page table.
• Stack page: Starting at $0xFFFFF000$.
  The 10 MSBs for this address are $1111111111_2 = 1023$. This requires the first-level entry at index $1023$, requiring 1 second-level page table.

3. Total Memory Calculation:

• We need $1$ first-level page table and $3$ second-level page tables.
• Total page tables = $1 + 3 = 4$.
• Total memory required = $4 \times 4\text{ KB} = 16\text{ KB}$.