Consider a 32-bit system with 4 KB page size and page table entries of size 4…
2024
Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = 210 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 ________
Attempted by 52 students.
Show answer & explanation
Correct answer: 1028
Key facts: 32-bit virtual addresses, 4 KB page size = 2^12 bytes, PTE size = 4 bytes = 2^2 bytes.
Entries per page = page size / PTE size = 2^12 / 2^2 = 2^10 = 1024 entries per page.
Two-level split: offset = 12 bits, remaining VPN bits = 20. With 1024 entries per inner page (10 bits), outer index is also 10 bits, so the outer page directory has 1024 entries and fits in one page (which the OS allocates at process creation).
Minimum number of inner page-table pages: pack valid PTEs densely, so need ceil(2000 / 1024) = 2 inner pages. Total minimum pages = 1 (outer) + 2 = 3.
Maximum number of inner page-table pages: to maximize, spread the 2000 accessed pages across as many different inner pages as possible. The number of distinct inner pages is limited by the outer directory entries (1024), so maximum inner pages = min(2000, 1024) = 1024. Total maximum pages = 1 (outer) + 1024 = 1025.
Therefore X (minimum) = 3 and Y (maximum) = 1025, so X + Y = 3 + 1025 = 1028.
A video solution is available for this question — log in and enroll to watch it.