How to calculate virtual address space in below question ?

Question

If we are given PAGE SIZE=4KB, PAGE TABLE ENTRY SIZE=4B OUTER PAGE TABLE SIZE=4KB and levels of Paging=3 ,so how to go about calculating the virtual address space .

Answer 1

No. of entries in outer page table = 4KB/4B = 1024, so 10 bits for this.

Now, we can't directly go to level 2, so lets go to final level.

In final level we need a page table entry for each page. Let the virtual address space be $2^p$, so no. of entries will be $\frac{2^p}{\text{page size}} = \frac{2^p}{4 \times 2^{10}} = 2^{p-12}$.

Now, these entries are spread across different tables. We are not sure how many of these entries are going to 1 third level page table. For this, lets assume a third level page table takes size of a page- 4KB. 

Now, no. of entries in a SINGLE third level page table $= 4KB/4B = 2^{10}$. So, no. of third level page tables $= \frac{2^{p-12}}{2^{10}} \\=2^{p-22}$. 

Now, we need second level PTE for each of these third level page tables. i.e., sum of PTEs in second level $=2^{p-22}$. 

Again lets assume a second level page table takes size of a page- 4KB. 

Now, no. of entries in a SINGLE second level page table $= 4KB/4B = 2^{10}$. So, no. of second level page tables $= \frac{2^{p-22}}{2^{10}} \\=2^{p-32}$. 

Now, we need an entry in first level page table for each of these second level page table and there is only 1 first level page table. We already got this is 1024 in our first step. So, 

$2^{p-32} = 2^{10} \\ \implies p-32 = 10 \implies p = 10 + 32 = 42.$

So, size of virtual address space $ = 2^{42}$ bytes. 

But don't forget the size of page tables we assumed during calculation - this might be different in other questions. 

Comments

Sir , I guess the logic which I have stated is correct .

---

We need two assumptions to solve the question. Now, assume 3rd level/2nd level page table size is 2KB or 8KB and solve. We will get a different answer.

Answer 2

Let LA  = p bits

As we know Page Table size = Number of entry * Page table entry Size

1.Level 3 PTS = 2^p/2¹² * 4 =   A

2.Level 2  PTS= A/2¹²*4 = B

3.Level 1 PTS = B/2¹²*4 = 2¹²

therefore B = 2²²
Now put the value of B in equation 2  A = 2³²
Now put the value of A in equation 1  2^P = 2⁴²

LA = P bits = 42


 

 

Answer 3

No of entries in outer page table =Page size/Page table size =k (2^10Bytes)

Now these entries will point to pages in which the inner page table2 is actually divided therefore no of entries in outer page table implies the no of pages in which we divide the inner page table2 and it is equal to K.

Now in each page of inner page table2 , we will have same 2^10 entries ,therefore in total we will have K*K entries coming out from inner page table 2 and these many entries are actually the no of pages in which we have divided the innermost page table 3, and therefore no of pages in which innermost page table 3 is paged is K*K , now in each page I shall have again K entries therefore total K*K*K entries would be coming out from innermost page table 3 and it is actually equal to no of pages in which my process would be divided therefore no of pages in virtual address space is K*K*K and each page is of size 4KB therefore virtual address space =2^30*2^12 Bytes =2^42 Bytes hence no of bits in virtual address =42 bits