Calculate the number of levels of outer page required

Question

In a paged virtual memory organization with 32 bit virtual address and 1 KB page size PTE is 32 bits. The number of levels of paging required to limit the outer page  table fit in one page frame is ________

Answer 1

Page size is 1KB.

So, no. of pages $ = \frac{2^{32}}{2^{10}} = 2^{22}$.

Each page entry requires 32 bits = 4 bytes as given in question.

Now, the outer page table must fit in a page frame - its size must be $\leq$ 1KB.

So, no. of entries in outer page table $\leq \frac{2^{10}}{2^2} = 256$.

So, we use 8 VA bits for indexing into page table 1.

It is not mentioned in question if the second level page table must also fit in a page frame, but assuming this, we need another 8 bits maximum for second level and only 32 - 10 - 8 - 8 = 6 bits remain for third level meaning it can easily fit in a page frame.

Comments

32 bit = 4 Bytes
To match neumerator and denominator

---

@pc don't know. Both are fine rt?

---

@Arjun. Yes, you are right. Both will do because these bits just serve as displacement into the page or portion of the page table. So, they dont have to do anything with the actual address.

Answer 2

Virtual address 32 bit

page size 2¹⁰ B

No of pages (32-10)=22 bits

PTE 32 bit=4 B=2²B

So, -ve factor i.e. 1st level page will be 2 bit less than page size

So, 1st level page will be 8 bits, 2nd level 8 bits

3rd level remaining 6 bits

So, answer will be 3

Answer 3

ans is c(3)

If the size of the page table>=Page Size we go for multilevel paging , Paging is Applied on the Pages of page table until first level page table size<==Page size.

in the question there is a misprint, INSTEAD OF PTE{page table entry} size  ptr size is given.

Page Table Size=#of Pages*Page Table Entry Size

#of Pages=LAS/Page Size

PTE=4B

--->1st time paging{last level page table}

Page table Size=(2^32/2^10)*2^2B

Still page table size ==2^24>>page size(2^10)

--->2nd time paging{second last page table}

Page Table Size=(2^24/2^10)*2^2

2^16>>2^10

--->3rd time paging 

Page Table Size=(2^16/2^10)*2^2B

Now page Table Size=2^8==256Bytes <Page Size

So 

3 level page table is required ,so that outer page table fit in one page frame.

Answer 4

First of all , its PTE and not PTR. And the page size can be given by...

2^(32-10n+5n) = 2^10             ----------- Given Condition      (n=levels)

n=22/5

Precisely answer should be 5, to make OPT smaller enough to fit. But as per options, closest answer can be 4.

-------------------------------------------------------------------------------

The condition that must be satisfied when you want to fit entire OPT in 1 page frame is...

2^(x-ny+nk) = 2^k

where... x = VAS bits;   y = Page size(in bits)            k = PTE (in bits)

-------------------------------------------------------------------------------