GATE CS 2024 Set 2 Q54 — Memory Management and Virtual Memory

To solve this problem, we first analyze the structure of the 2-level page table:

• Page Size: $4\text{ KB} = 2^{12}\text{ bytes}$ (Offset = $12$ bits).
• Page Table Entry (PTE) size: $4\text{ bytes}$.
• Entries per page: $\frac{4\text{ KB}}{4\text{ bytes}} = 1024 = 2^{10}$ entries.

Since the system uses a 2-level page table for a 32-bit address space, the virtual address is split as follows:

Thus, the outer page directory contains $1024$ entries, pointing to a maximum of $1024$ inner page tables. Each inner page table covers $1024$ pages of virtual memory.

The process accesses $2000$ unique pages. The outer page directory is always allocated ($1$ page).

1. Minimum Pages ($X$):
To minimize the number of inner page tables, the $2000$ pages should be clustered as contiguously as possible. Since each inner page table covers $1024$ pages, the minimum number of inner page tables required is: $$\left\lceil \frac{2000}{1024} \right\rceil = 2 \text{ inner page tables}$$ $$X = 1 \text{ (outer)} + 2 \text{ (inner)} = 3 \text{ pages}$$

2. Maximum Pages ($Y$):
To maximize the number of inner page tables, the $2000$ pages should be distributed across as many different inner page tables as possible. Since there are at most $1024$ inner page tables and $2000 \ge 1024$, we can distribute the pages such that every one of the $1024$ inner page tables contains at least one active page. $$Y = 1 \text{ (outer)} + 1024 \text{ (inner)} = 1025 \text{ pages}$$

Calculating $X + Y$:
$$X + Y = 3 + 1025 = 1028$$