Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = $2^{10}$ bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry. An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let $X$ denote the minimum and $Y$ denote the maximum number of pages across the two levels of the page table of the process. The value of $X+Y$ is _______

### Step 1: Determine the page table structure

• Virtual Address Size:$32\text{ bits}$

• Page Size: $4\text{ KB} = 2^{12}\text{ bytes} \implies 12\text{ bits for page offset}$.

• Page Table Entry (PTE) Size: $4\text{ bytes} = 2^2\text{ bytes}$.

• Number of entries per inner page table page:

  $$\frac{\text{Page Size}}{\text{PTE Size}} = \frac{4\text{ KB}}{4\text{ B}} = \frac{2^{12}}{2^2} = 2^{10} = 1024\text{ entries}$$

• Therefore, the inner page table requires $10\text{ bits}$, leaving $32 - 12 - 10 = 10\text{ bits}$ for the outer page directory.

• The outer page directory contains $2^{10} = 1024$ entries and occupies exactly $1\text{ page}$.

### Step 2: Compute the minimum number of pages ($X$)

• The outer page directory is always allocated: $1\text{ page}$.

• The process accesses $2000$ unique pages.

• To minimize the number of inner page table pages, these $2000$ entries should be packed into as few inner page table pages as possible.

• Since each inner page table page can store up to $1024$ entries:

  $$\text{Minimum inner page table pages} = \left\lceil \frac{2000}{1024} \right\rceil = 2\text{ pages}$$

• Total minimum pages across both levels:

  $$X = 1\text{ (outer)} + 2\text{ (inner)} = 3$$

### Step 3: Compute the maximum number of pages ($Y$)

• To maximize the number of inner page table pages, the $2000$ accessed pages should be distributed across as many distinct outer page directory entries as possible.

• The outer page directory has at most $1024$ entries, meaning there can be at most $1024$ inner page table pages.

• Since $2000 \ge 1024$, all $1024$ inner page table pages can be allocated (each having at least $1$ entry).

• Total maximum pages across both levels:

  $$Y = 1\text{ (outer)} + 1024\text{ (inner)} = 1025$$

### Step 4: Calculate $X + Y$