test book test

Question

46 bit Virtual addressing system uses 3 level paging. The page table entry is 32 bits. Size of Page Table is equal to 1 page. The processor uses 1 MB, 16 way set associative cache with 64 block. What is the size of Page Table?

a) 2KB

b) 4KB

c) 8KB

d) 16KB

Comments

I think option (C) is correct and data given for cache is of no use to solve question.

---

is it c?

i'm not getting the relation b/w cache and va.

---

yep the answer is c...can u explain ?? thanks :)

Answer 1

Let Page size $= 2^x$B

Number of pages in innermost page table $ = \frac{2^{46}}{2^x} = 2^{46-x}$

Size of innermost page table $ = 2^{46-x}*4 = 2^{48-x}$ (PTE = 32bit)

No. of pages in second level page table $ = \frac{2^{48-x}}{2^x} = 2^{48-2x}$

Size of $2^{nd}$ level page table $ = 2^{48-2x}*4 = 2^{50-2x}$

No. of pages in outermost page table $ = \frac{2^{50-2x}}{2^x} = 2^{50-3x}$

Size of outermost page table $= 2^{50-3x}*4 = 2^{52-3x}$

Question says Size of Page Table is equal to 1 page.

$\Rightarrow 2^{52-3x} = 2^x$

$\Rightarrow x = 13$

So, Page size $ = 2^{13} = 8KB$

Comments

Got my mistake.

---

@see sushant ..don't get it wrong ! ..if you think something is not 100% right in your mind in a particular confusion..you take time and think ..and the solution will come automatically. Like in this case, you yourself found the mistake. The time you spent in writing these above comments could have been utilized in realizing the mistake itself.

But that does not mean that one should not post comments regarding doubts. Doubts are always appreciated unless they are trivially wrong.

---

@Debashish. Sometimes we assume things that we dont realize arent right at that time. Even after giving time, I wasnt really able to distingusih between block size and frame size.

Anyways, thanks :) I admit my mistake.

Answer 2

Required Information to Evaluate Page table size in question : Virtual Address = 46-bits, 3-level paging Architecture, Page table entry size= 32-bits i.e.(4 Bytes), page size = First level page table size.

Solution :

Let the size of the page is x bytes.

Page table size = (Number of entries in Page table) ∗ (Page table entry size)

First Time paging :

$\frac{2^{46}}{x}\times 4 = \frac{2^{48}}{x}$ 

This is the 3rd level page table size.

Second Time paging :

$\frac{2^{48}/x}{x}\times 4 = \frac{2^{50}}{x^{2}}$

This is the 2nd level page table size.

Third Time paging :

$\frac{2^{50}/x^{2}}{x}\times 4 = \frac{2^{52}}{x^{3}}$

This is the First level page table size.

Since, First level page table size = page size

Therefore, 

$\frac{2^{52}}{x^{3}}=x$

$x^{4}=2^{52}$

$x^{4}=\left (2 ^{13} \right )^{4}$

$x=2^{13}$ bytes

x = 8 KB

Page table size = 8 KB

Answer 3

Let page size = PS = 2^x

VA = 46 bit

No of pages = size of va / size of page = 2⁴⁶/2^x = 2^46-x;

Page Table Size = PTS1 = No of pages × Page Table Entry (PTE)= 2^46-x × 32 bit = 2^46-x × 4 Bytes = 2^48-x;

PTS₁ cannot fit in 1 page; so we divide PTS₁ into pages;

PTS₂ = (PTS₁ / PS) × PTE = (2^48-x / 2^x ) × 4 = 2^50-2x;

PTS2 cannot fit in 1 page; so we divide PTS2 into pages;

PTS₃ = (PTS₂ / PS) × PTE = (2^50-2x / 2^x ) × 4 = 2^52-3x;

PTS_³ = PS  (it is given is question)

=>  2^52-3x = 2^x => x=13

So, PS = 2¹³ = 8 KB

Comments

Thank you :)

Answer 4

Let us assume its byte addressable memory..
Let Page size = 2^p Bytes.

As entry size = 32 bits= 4B.

So No of entries in a page = 2^p/4 = 2^(p-2)

So Each page table level index bits = p-2

As no of level = 3, so total no of bits for 3 levels = 3(p-2).

and p bits for page offset.

so, 3(p-2)+p = 46 ===>p = 13

So page table size = 2^13 = 8KB