Multi-level paging doubt

Question

Consider a computer system using 2-level paging with TLB. The logical address supported is 32 bits. The page table is divided into 512 pages each of size 1KB. Page table entry size at 1st level is 2Bytes and that at the second level is 4 Bytes each.

What is the memory overhead of storing the page tables of this process?

My Analysis:

Since the page table is divided into 512 pages each of size 1KB, means the page size is 1KB and hence offset bits are 10.

So, total page bits are 22(32-10).

Since at second level each page table size is equal to the size of a page=1KB, the number of entries that can come in 1-page table at second level=$\frac{1KB}{4B}=2^8$ entries

That means at the second level I need 8 offset bits to index into a second level page table.

And hence my address structure would be like below

14($P_1)$

8($P_2$)

10$(offset)$

Now, since the process's page table is divided into 512 pages each of size 1K, that means at the second level I have only 512-page tables each of size 1K. My outer page table can contain a maximum of $2^{14}$ entries each of which can point to a $2^8$ entry second level page table for total $2^{22}$ pages that can be addressed by this computer.

So, for this process, at first level page table, first $2^9$ entries will be valid and they will point to a second level page table each of which is 1KB in size. Remaining, $2^{14}-2^9$ entries of the first level page table would be marked invalid and they won't point to anything.

So, all in all, this given process takes full 1st level page table(containing $2^{14}$ entries of which only $2^9$ are valid) plus 512 second level page tables each of size 1K.

So page table size of this process comes to be

$2^{14}*2B$(For first level PT)+$512*1KB$(At second level)=$544KB$

Is my analysis correct?

Below is the visualisation what I see is happening.

Comments

Your analysis seems to be correct but I am confused about one thing.

It is given that the page table is divided into 512 pages and page size=1KB=2¹⁰B.

Logical address= page no. + page offset (later page no. can be divided into parts for multilevel paging)

So, page no. = 32-10=22. There are 2²² page table entries required. Since accommodating them into one single "page" is impossible so we divide the page table into pages.

Given that size of 2nd level page table entry is 4B.

Then no. of pages into which this large page table can be divided into is : (2²² x 2²)/2¹⁰

[ (No. of page table entries * size of each entry)/ size of a page] which comes out to be 2¹⁴. But given that there are 512 pages. Does this mean that 512 pages contains the actual content of the process but there are actually 2¹⁴ pages in the 2nd level..?

If so then in your diagram, in the 1st level from entry no. 512 to (2¹⁴-1) there will be pointers to 2nd level pages but those pages will be empty.

Correct me if you find this wrong.

 

---

Just think if at the first level page table we have 2$^{14}$ entries of 2B each then can we accommodate one page table in one page?

---

Tesla!

Yes you have got a point.. Thanks :)

---

@MINIPanda

but where has it been written that 1st level page table should be accomodated in a single page? as far as the questions i've come across, there has been an explicit mentioning of 1st level page table going into a single page.

---

@aambazinga

When the question mentions about more than 1-level paging which means multi-level paging then that is enough to indicate that the outer most page should be fitted in one page. That is the concept behind multilevel paging..keep on breaking the page table into pages until it fits into a single one page..

---

"keep on breaking" when we have not been given constraint about the number of page table levels. when it has explictly been given that 2-level page tables are there, then in no way can correct we break the logical address space of 32 bits to accomodate top level into 1 page, for this question.

and btw it is not a written concept and neither a hard and fast rule to put the top level into a single page. if the question is wanting to ask something else, we have to act accordingly.

---

@aambazinga

You are saying that the outer page table might be more than 1 page?

---

@MINIPanda

i'm saying that it's not compulsory that outer page table should be a page itself, let alone single page or more than 1 page.