GATE CS 2021 Set 2 Q48 — Memory Management and Virtual Memory

To find the minimum memory required, we break down the virtual address and assume the process's virtual memory is allocated contiguously to minimize the number of higher-level page tables.

1. Address Translation Breakdown:

• Page Size = $4 \text{ KB} = 2^{12} \text{ bytes} \implies \text{Offset} = 12 \text{ bits}$
• Page Table Entry (PTE) size = $8 \text{ bytes}$
• Number of entries per page table page = $\frac{4 \text{ KB}}{8 \text{ B}} = 512 = 2^9 \implies 9 \text{ bits}$ per level
• This matches the 3-level page table structure: $9 \text{ bits (L1)} + 9 \text{ bits (L2)} + 9 \text{ bits (L3)} + 12 \text{ bits (Offset)} = 39 \text{ bits}$

2. Number of Pages to Map:

$$\text{Total Pages} = \frac{2 \text{ GB}}{4 \text{ KB}} = \frac{2^{31} \text{ B}}{2^{12} \text{ B}} = 2^{19} \text{ pages}$$

3. Minimum Page Tables Required (Contiguous Allocation):

• Level 3: Each L3 page table maps $2^9 = 512$ pages. $$\text{L3 tables} = \frac{2^{19}}{2^9} = 2^{10} = 1024$$
• Level 2: Each L2 page table maps $2^9 = 512$ L3 tables. $$\text{L2 tables} = \left\lceil \frac{1024}{512} \right\rceil = 2$$
• Level 1: Always $1$ root page table.

4. Total Memory Calculation:

$$\text{Total Page Tables} = 1 \text{ (L1)} + 2 \text{ (L2)} + 1024 \text{ (L3)} = 1027 \text{ tables}$$

$$\text{Total Memory} = 1027 \times 4 \text{ KB} = 4108 \text{ KB}$$