GATE CSE 2025 | Set 2 | Question: 48

Question

A computer system supports a logical address space of $2^{32}$ bytes. It uses two-level hierarchical paging with a page size of $4096$ bytes. A logical address is divided into a $b$-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size.

The value of $b$ is _________. (Answer in integer)

Comments

Here the outermost page table has 2^11 entries -> size of that page table = 2^11 * 2^3 = 2^14B which again we can't store in Frame of physical memory right? In practical this won't happen right?

---

@mo7ammedfarooqI think you did not clearly understood the question. 
In the question they mentioned clearly that "Each entry of the inner page table uses eight bytes." . The outer page table entry may be different.(may be 2 bytes so that entire outer page table can fot into one page table) .

Is my approach correct ?    Can it be possible that different size of PTE for each level ? 

---

Thinking OS design wise it can very well be possible. Maybe the inner page contains frame data plus way more control bits than outer PT so thats why maybe.

---

I also thought the same as you @raghu_46

Answer 1

Logical Address Space $= 2^{32}$ Bytes
Page Size $= 4096$ Bytes $= 2^{12}$ Bytes
Page Table Entry Size $($at inner page table$)$ $= 8$ Bytes $= 2^{3}$ Bytes

It is given that there is two-level hierarchical paging, with $b-$bit index to the outer page table.

Now, as given all pages in the system have the same size. So, $1$ Page Table should fit in $1$ Page.
Therefore, Page Table Size $=$ Page Size.

Page Table Size $= 2^{12}$ Bytes
Page Table Size $=$ No. of Entries $\times$ Page Table Entry Size

So, 
No. of Entries $\times$ Page Table Entry Size $= 2^{12}$ Bytes

No. of Entries at inner level$= \frac{2^{12}}{2^{3}} = 2^{9} $

As, no. of entries are $2^{9}$ at inner level, $9$ bits would be required for index at that level.
So, $x=9$

$b+x+12 = 32$
$b=32-12-9$
$b=11$

Answer : Value of $\mathbf{b}$ is $\mathbf{11}$  

Comments

watch it

@Abhishek_Soni 1

https://youtu.be/8kBPRrHOTwg?si=b6LQ8H6M-NoFM2Ir

---

Entries per page = Page Size / Entry Size
Inner index bits = log₂(Entries per page)

4096 / 8 = 512 = 2⁹ entries per page → inner index = 9 bits.

The inner page table is itself stored within one page (that's how hierarchical paging works)

So the inner page table has space for 2⁹ entries. 

32-bit address = [ b (outer) | 9 (inner) | 12 (offset) ]

b = 11

 

---

@Abhishek_Soni 1

There's no specific rule like that but it is usually satisfied because in most of the questions the page table entry size is common. So outer page table size <= page size (inner page table size).

Answer 2

Answer - 11

Comments

can't we say interchange? like 9 outer page & 11 inner level?

Answer 3

Detailed Solution With All Possible Question That Can Be Asked Around It

---

Comments

Thanku for this <3

Answer 4

Given here Logical Address space size is $32$ bit.
Page table size = $4096$ bytes=2^12 bytes. 

Given it is a $2-level$ page table , so we have it will be look like this,

 

So we need to find $x$ only.
Inner page table entry size is =$8$ bits.
So number of entries inner page table can store is =$2^{12}/8=2^{9}$.
So $x=9$ bits.
So, $b=(32-9-12)=11$ bits.

So correct answer is 11 bits.

Comments

how 2^12 come? how can we conclude that inner level page table size is one page?

in question they told all pages are same size, does this implies that every page table has one page size?

Answer 5

We are given the following parameters:

• Logical address space: 2³² bytes
• Page size = 4096 bytes = 2¹² bytes means Page offset = 12 bits
• Inner page table entry size = 8 bytes = 2³ bytes
• Number of entries per page (inner page table): 4096 / 8 = 512 = 2⁹ so Inner page table index = 9 bits

 

The 32-bit logical address is divided as follows:

• Outer page table index: b bits
• Inner page table index: 9 bits
• Page offset: 12 bits

Therefore:

b + 9 + 12 = 32

b = 32 - 21 = 11

Answer: The value of b is 11.

Answer 6

Inner Page Table size= No.of pages * e
                                   = [(2^32)/2^12]*2^3
                                   = 2^23

Now, we will apply paging on this page table
So, number of pages in the outer page table= (2^23)/2^12= 2^11
so the value of b which acts as a page number= log(No. of pages)= log(2^11)=11

Comments

@Neeraj_Chaudhary outermost page table entry offset bits (b)=11

Then innermost page table offset should be 9 bits right ?!

But according to your solution how many bits assingned for innermost page table (say x) ?

could you please explain? :-)

---

the number of bits assigned are 9 only
logical address is 32 bits 12 bits are for the offset that will combine with the frame and will form the phsical address
now, 11 bits for the outer x for the inner and 12 for the final offset equals 32
11+x+12=32
x=9 bits