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 ________
Answer
1028
Explanation
A 4 KB page holds \(2^{12} / 4 = 1024\) entries. So one inner page-table page maps 1024 pages, and the outer directory (one page, 1024 entries) can point to at most 1024 inner pages. The directory page always exists.
- Minimum: the 2000 pages fall into as few 1024-page regions as possible, \(\lceil 2000 / 1024 \rceil = 2\) inner pages, so \(X = 1 + 2 = 3\).
- Maximum: the pages are spread out so that each inner page has few valid entries. With 2000 pages and only 1024 possible inner pages, all 1024 can be in use, so \(Y = 1 + 1024 = 1025\).
Hence \(X + Y = 3 + 1025 = 1028\).
Answer: 1028