Multilevel paging

Question

The below question is from made easy test series:

Consider a 32 bit virtual address as follows:

10

8

6

8

P1

P2

P3

Offset

 

System uses 3 level paging and the bits for the respective levels are as indicated above. Then the size of page table for a process which requires 256 KB of memory statrting at address 0, _____ [Assume entry size = 2B] 

 

Ans: 4608 B

But I am getting 2560 B

My Solution:

Process size = 256KB

Page size = 2$^{8}$ B (From offset field)

 

No. of pages in the process = No. of entries in P3 = $\frac{256KB} {2^{8}} $ = 2$^{10}$ 

Size of Page table P3 = 2$^{10}$ x 2 = 2$^{11}$  B

 

No. of pages in P3 = No. of entries in P2 =  $\frac{2^{11}} {2^{8}} $ = 2$^{3}$ 

Size of Page table P2 = 2$^{3}$ x 2 = 2$^{4}$  B

 

No. pages in P2 = No. of entries in P1 = $\frac{2^{4}} {2^{8}} $ ~ 1

 

Thus P1 will require 1 page 

P2 will require 1 page 

P3 will require  2$^{3}$ pages

 

Thus total memory required for page table of P across all level= Size of page x No. of pages required for the pages tables = 2$^{8}$ x (2$^{3}$  + 1 + 1) = 2560 B

One more thing I found confusing in the question is 1 page of level 3 can point to 2$^{6}$ pages of process P but if we take into consideration page size and page table entry then each page of every level should point $\frac{2^{8}} {2} $ = 2$^{7}$ pages.

 

I don't know what I am getting wrong. Please correct me.

Comments

The mistake you are doing is the most common mistake everyone do-

Number of bits assigned for $3$^rd level Page Table is $6$. So, there can be atmost $2^6$ entries in each page table at 3^rd level i.e. Page Table size of 3rd Level is $2^7\ B$ if we consider each page entry as $2\ B$.

What you are doing is that you are considering each page table to be of size $2^8\ B$, i.e. every level Page Table  has $2^7$ entries in each table if we consider each page entry as $2\ B$.

---

But if consider $1^{st}$ level page table then the number of bits assigned is 10 so there can  be at most $2^{10} $ entries in each page table and since each page entry is of 2B then single page of level $1$ will require  $2^{11} $ byte of page size which is greater than page size i.e  $256 B$ so how can this possible

---

@Chaitanya Kale That is the interesting thing. It is possible that a page table is bigger than the page size itself. To be clear, page table size is independent of what your page size is.

But it is better that your page table size is less than your page size, otherwise, you’ll need more than one memory access to get the entire page table.

There is already a gate question of this type – https://gateoverflow.in/490/gate-cse-2008-question-67

Answer 1

From the question we can calculate the following:

1. Max number of entries in 1 page = 2^8B/2B = 2^7 entries.
2. Number of Pages of the Process = 256KB/256B = 2^10 = 1024.
3. Now each page table should fit into a single frame/page. So if we see the arrangement given for P3 we have 6 bits so we can have 2^6 entries for the page table but we just calculated that one page can hold a max of 2^7 entries, so we can observe that the arrangement given for P3 is not filling up the entire page but only 2^6 entries of the available 2^7 entries.
4. So for P3 each page is containing 2^6 entries and we have 2^10 pages so for P3 how many pages do we need: 2^10/2^6 = 2^4 = 16.
5. For P2 we have 2^4 entries which will fit into one page.
6. For P1 again we need 1 page to refer to P2’s single page.
7. So total no. of pages needed = 16 + 1 + 1 = 18 and total size of the Page table = 18 * 256B = 4608B.

Try to visualize the question, you will get a better understanding of the flow.

Comments

Since the bits used in indexing in each level of the page table are different then won't the page size required for a given level will be different?

For eg for  $P1 $ we have 10 bits so  $2^{10} $ entries for the page table but we can have only  $2^{7} $ entries so where will we store these extra entries if page size is same?

---

@Chaitanya Kale there is no such rule that the PT size have to be equal to or less than the page size so this can be a correct implementation however having PT size <= Page size helps in accessing the PT using only 1 memory reference. The given configuration is not an optimized one as the no. of memory accesses will be more than 1 for P1 and P2 given that we require to access entries beyond 2^7