GATE CS 2024 Set 2 Q.64: Memory Management and Virtual Memory

Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume $1\text{ 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 ________

Your answer

Official answer and solution

Official answer: 1028
From: Official GATE 2024 answer key

Solution

Determine the number of PTEs per page ( $4\text{ KB} / 4\text{ B} = 1024$ ), then find the minimum ( $2$ ) and maximum ( $1024$ ) number of inner page table pages needed for 2000 valid PTEs, plus 1 outer page directory page each.

Page table geometry:
- Page size $= 4\text{ KB} = 2^{12}$ bytes; PTE size $= 4$ bytes.
- Number of entries per page table page $= \frac{2^{12}}{4} = 2^{10} = 1024$ entries.
- In the 32-bit virtual address ( $10 + 10 + 12$ split), the outer page directory occupies 1 page and points to up to 1024 inner page table pages, each holding up to 1024 PTEs.
Minimum page table pages ( $X$ ):
- To minimize the number of inner page table pages for $2000$ unique virtual pages, pack the $2000$ valid PTEs contiguously into $\lceil 2000 / 1024 \rceil = 2$ inner page table pages.
- Including the $1$ outer page directory page: $X = 1 + 2 = 3$ .
Maximum page table pages ( $Y$ ):
- To maximize the number of inner page table pages, spread the $2000$ valid PTEs across as many inner page table pages as possible. Since there are only $1024$ possible inner page table pages in total and $2000 \ge 1024$ , all $1024$ inner page table pages can contain at least one valid PTE.
- Including the $1$ outer page directory page: $Y = 1 + 1024 = 1025$ .
Sum: $X + Y = 3 + 1025 = 1028$

Final answer

1028

Common trap

Assuming the maximum number of inner page table pages is 2000 (one per accessed page) without noticing that the outer page directory has only 1024 entries.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 64 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source