GATE CSE 2024 | Set 2 | Question: 54

Question

Consider a $32$-bit system with $4 \mathrm{~KB}$ page size and page table entries of size $4$ bytes each. Assume $1 \mathrm{~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 $\text{OS}$ allocates a page for the outer page directory upon process creation. The $\text{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 $\text{X}$ denote the minimum and $\text{Y}$ denote the maximum number of pages across the two levels of the page table of the process.

The value of $\text{X+Y}$ is ___________.

Comments

@Suraj Reddy as in question division of VA is not mentioned we can divide it variabley.you can refer the below link for reference

https://courses.cs.washington.edu/courses/cse451/03wi/section/2_13_section.htm

---

Even in similar paging gate pya it is never mentioned to take equally divided ka for page table bit yet we take them equal. I think by default if not mentioned then we have to take it equal

---

@Arjun @Sachin Mittal 1sir please help in this so that  we can know it can be challenged or not??????

Answer 1

Given:

• System address space $(VA)=32\:bits$
• Page size $(PS)=4KB$
• Total pages used by a process $(N)=2000\: pages$
• Page table entry size $(PTE)=4B$

It is given in the question that OS allocates a page(means single page) for the outer page directory upon process creation. 

So, total number of bits needed to represent entries in outer page table $= log(PS/PTE) = log(2^{12}/2^2) = 10\:bits$

And total number of bits needed to represent entries in inner page table $=32-10-12 = 10\: bits$

For $X:$

In each inner page table we can store $2^{10}$ entries. So, minimum number of page tables$(PT)$ needed to store $2000$ pages will be $\lceil 2000/2^{10}\rceil = 2\: PT$

$\therefore X=2 + 1(for \:outer\: PT) = 3$

For $Y$:

For occupying maximum pages in 2-level page table, we need to place atleast one $PTE$ from $2000$ pages in every page of the inner page table equating to $2^{10}\: PT$.

$\therefore Y=2^{10} + 1(for \:outer\: PT) = 1025$

The value of $X+Y= 1028$

Comments

Thanks, I was confused about Y, after I got it after sometime.

Answer 2

X=3
Y=1025
Hence ans =1028