GATE CS 2024 Set 2 — Question 64

NAT+2 / -0HardMultilevel & Inverted Page TablesMemory ManagementOperating SystemDemand Paging

Operating System → Memory Management → Demand Paging

Last updated 20 August 2026

Question

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 ________

Correct answer

1028 to 1028

Solution

1.System Parameters:

Logical Address (LA) space = 32 bits.
Page Size (PS) = 4 KB = $2^{12}$ bytes.
Page Table Entry (PTE) size = 4 bytes.
Number of entries per page = $\frac{\text{Page Size}}{\text{PTE Size}} = \frac{2^{12}}{2^2} = 2^{10} = 1024$ entries.

2. 2-Level Page Table Structure:

Total pages in LA space = $\frac{2^{32}}{2^{12}} = 2^{20}$ pages.
The Inner Page Table (IPT) needs to map $2^{20}$ pages. Since each IPT page holds 1024 entries, the total number of IPT pages is $\frac{2^{20}}{1024} = 1024$ pages.
The Outer Page Directory (OPD) must have one entry for each of the 1024 IPT pages. Thus, the OPD has 1024 entries.
Size of OPD = $1024 \times 4$ bytes = 4 KB, which fits exactly in 1 page.

3. Calculating $X$ (Minimum number of pages):

1 page is always allocated for the OPD upon process creation.
To minimize the number of IPT pages for 2000 unique pages, we assume they are contiguous in the logical address space.
Number of IPT pages = $\lceil \frac{2000}{1024} \rceil = 2$ pages.
$X = 1 \text{ (OPD)} + 2 \text{ (IPT)} = 3$ .

4. Calculating $Y$ (Maximum number of pages):

1 page is always allocated for the OPD.
To maximize the number of IPT pages, we spread the 2000 unique pages across as many IPT pages as possible.
Since there are only 1024 IPT pages in total, and the process accesses $2000$ unique pages (where $2000 > 1024$ ), it is possible to have at least one entry in every single IPT page.
$Y = 1 \text{ (OPD)} + 1024 \text{ (IPT)} = 1025$ .

5. Final Value:

$X + Y = 3 + 1025 = 1028$ .

GATE CS 2024 Set 2 — Question 64

Question

Correct answer

Solution

More questions on Memory Management