GATE 2024 CS2 Q.64: solution and answer

GATE 2024 · CS2Q.64 · 2 marks · NAT

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 ________

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$X + Y = 3 + 1025 = 1028$

Official answer: 1028Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

Page size is $4 KB = 2^{12}$ bytes, so the offset is 12 bits. The virtual page number is $32 - 12 = 20$ bits.
One page-table page holds $4096/4 = 1024 = 2^{10}$ entries. The 20-bit page number therefore splits into 10 bits for the outer directory and 10 bits for the inner table.
The outer directory is one page, allocated at process creation. It has 1024 entries, so it can point to at most 1024 inner-table pages. Every inner-table page covers 1024 virtual pages.
Minimum: one inner-table page can hold valid entries for at most 1024 accessed pages. Since $⌈ 2000/1024 ⌉ = 2$ , at least 2 inner pages are needed. Two suffice if the 2000 pages are consecutive and lie within two inner tables. So $X = 1 + 2 = 3$ .
Maximum: an inner page is allocated only if it holds at least one valid entry, and there are 1024 outer entries, so there can be at most 1024 inner pages. This is reachable because $2000 \geq 1024$ : place one accessed page under each outer entry, and the remaining $2000 - 1024 = 976$ pages under any of those inner pages. So $Y = 1 + 1024 = 1025$ .
$X + Y = 3 + 1025 = 1028$ .

KEY IDEA

With 4 KB pages and 4-byte entries, each page-table page holds 1024 entries. The minimum comes from packing the accessed pages into as few inner tables as possible, and the maximum from spreading them over as many inner tables as the outer directory can point to. The outer directory is always exactly one page.

WATCH OUT FOR

Taking the maximum as 2000 inner pages. The outer directory has only 1024 entries, so at most 1024 inner pages can exist. Another slip is forgetting to count the one outer-directory page in both X and Y.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 10 Memory management questions, with notes

GATE 2024 CS2 Q.64: solution and answer

Answer and solution

More Memory management questions