Question

Consider a 32-bit system with a 4 KB page size and page table entries of size 4 bytes each. Assume \(1 \, \text{KB} = 2^{10} \, \text{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 ............

Hint:

Always calculate the number of page table entries per inner page and analyze the allocation policy for minimum and maximum scenarios.

Answer 1

Given: System address space (\(VA\)) = \(32 \, \text{bits}\) Page size (\(PS\)) = \(4 \, \text{KB}\) Total pages used by a process (\(N\)) = \(2000 \, \text{pages}\) Page table entry size (\(PTE\)) = \(4 \, \text{B}\) It is given in the question that the OS allocates a page (means single page) for the outer page directory upon process creation. 

Step 1: Calculate the total number of bits needed for the outer page table. 
The total number of bits needed to represent entries in the outer page table is: \[ \log \left(\frac{PS}{PTE}\right) = \log \left(\frac{2^{12}}{2^2}\right) = \log(2^{10}) = 10 \, \text{bits}. \] 

Step 2: Calculate the total number of bits needed for the inner page table. 
The total number of bits needed to represent entries in the inner page table is: \[ 32 \, (\text{total VA bits}) - 10 \, (\text{outer PT bits}) - 12 \, (\text{page offset bits}) = 10 \, \text{bits}. \] 

Step 3: Calculate \(X\). 
In each inner page table, we can store \(2^{10}\) entries. The minimum number of page tables (\(PT\)) needed to store \(2000\) pages will be: \[ \lceil \frac{2000}{2^{10}} \rceil = 2 \, PT. \] Thus: \[ X = 2 + 1 \, (\text{for the outer PT}) = 3. \] 

Step 4: Calculate \(Y\). 
For occupying the maximum pages in a 2-level page table, we need to place at least one \(PTE\) from \(2000\) pages in every page of the inner page table. This equates to \(2^{10}\) \(PT\). Thus: \[ Y = 2^{10} + 1 \, (\text{for the outer PT}) = 1025. \] 

Step 5: Calculate \(X + Y\). 
The value of \(X + Y\) is: \[ X + Y = 3 + 1025 = 1028. \] 


Final Answer: \[ \boxed{1028}. \]