7k views

A computer uses 46-bit virtual address, 32-bit physical address, and a three–level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16 way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.

What is the size of a page in KB in this computer?

1. 2
2. 4
3. 8
4. 16
edited | 7k views

Nothing is given so in this question it is assumed that page of page table are page aligned.

Notice difference with respect to https://gateoverflow.in/490/gate2008-67

Also notice in last page table number of entries will be $\frac{2^{46}}{x}$ not $\frac{2^{32}}{x}$. In this way we running process gets illusion that more amount of memory is present but reality is something else :)

Let the page size be $x$.

Since virtual address is 46 bits, we have total number of pages $= \frac{2^{46}}{x}$

We should have an entry for each page in last level page table which here is T3. So,

number of entries in T3 (sum of entries across all possible T3 tables) $= \frac{2^{46}}{x}$

Each entry takes 32 bits = 4 bytes. So, total size of T3 tables $= \frac{2^{46}}{x} \times 4 = \frac{2^{48}}{x}$ bytes

Now, no. of T3 tables will be Total size of T3 tables/page table size  and for each of these page tables, we must have a T2 entry. Taking T3 size as page size, no. of entries across all T2 tables
$= \frac{\frac{2^{48}}{x}}{x} = \frac{2^{48}}{x^2}$

Now, no. of T2 tables (assuming T2 size as pagesize) = $\frac{2^{48}}{x^2} \times 4$ bytes = $\frac{\frac{2^{50}}{x^2}} {x} = \frac{2^{50}}{x^3}$.

Now, for each of these page table, we must have an entry in T1. So, number of entries in T1

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

And size of T1 $=\frac{2^{50}}{x^3} \times 4 =\frac{2^{52}}{x^3}$

Given in question, size of T1 is page size which we took as $x$. So,

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

$x^4 =2^{52}$

$x = 2^{13}$

$= 8KB$
edited by

sushmita  don't make assumption and go for sachin's solution..

that question is answered and selected by same person....it should not be..

Which question? And Sachin's answer also has the same assumption.
I'm not an idiot to do that FYI.

Prove it if you can @suvasish pal

i can not remember the question..next time when i again see i will inform u then and there :)
Are you an RBR student to behave like him? If you cannot prove what you accuse others of, you wont be continuing here any longer.
@suvashish,you do not pay any one here to get the explanation .
yes u may right sourav.

I already put it as comment, in case if one skipped it.

One other method to find page size-

We know that all levels page tables must be completely full except outermost, the outermost page table may occupy whole page or less. But in question, it is given that Outermost page table occupies whole page.

Now let page size is 2Bytes.

Given that PTE = 32 bits = 4 Bytes = 2Bytes.

Number of entries in any page of any pagetable =page size/PTE = 2p/22 = 2p-2.

 p-2 p-2 p-2 p

logical address space is 46bits given. Hence equation becomes,

(p-2)+(p-2)+(p-2)+p = 46

⇒p=13.

Therefore page size is 213 Bytes =8KB

@Sachin solution is right,

Actually page table contains many number of PTEs. And each each PTE contains different pages .
I did not get u, U r saying this solution is right and then u are explaining something.
What exactly u mean ? :P
means in a 3 level page table

in each 3rd level of page table  need to address by 2nd level of page table entry and each 2nd level of page table address by 1st level page table. rt?

and outer most page table here is the 1st level of page table.Which holds reference for all other level of page table.
Thanks. I always do it by this method only. Easy and Fast. :)
I've a doubt.

In question its given that only first level page table T1 occupies exactly one page but why we assumed second level page table T2 and inner most page table T3 to be of page size too? Please reply.
Where is it given that all page tables occupy one page?
Good solution @sachin.
Hello sachin

Thanks for your time and contribution.

I feel this is simpler approach,

(C)

Let size of the page be x.

Total number of entries in T1 = x/4.

Total number of entries in T2 = x/4 * x/4

Total number of entries in T3 = x/4 * x/4 * x/4 which is also total number of pages

Total virtual address space = (x/4 * x/4 * x/4) * x = 2^46

∴ x4/2^6 = 2^46

∴ x = 2^13 bytes = 8Kb

edited
Total virtual address space = (x/4 * x/4 * x/4) * x/4 = 246

∴ x4/26 = 246

explain

let page size is P bytes. Page table entry size  = 4byte.

PA = 32 bits   VA = 46 bits

it is given that outermost page table is completly full.

∴ no. of entries in outer page table = (P/4).

∴ total no. of entries in 2nd level page table = (P/4)*(P/4)

∴ total no. of entries in  3rd level page table = (P/4)*(P/4)*(P/4)

virtual address space = total pages * size of each pge

= (P/4)*(P/4)*(P/4) * P

= P4 /64

246 = P4 /64

P  = 213 B

= 8KB

@arjun sir is this a correct solution?

We know from the question that a page table can retain in a single page.

Assume size of page is 2.

No. of entries that can be cotained in a page is 2x/4 that is 2x-2. So at a particular level no. of entries can be addressable in x-2 bits.

So,

We can consider bit distribution of virutal address as bit required for 1st level + 2nd level + 3rd level + page

That is                       x-2 + x-2 + x-2 + x = 46

Solving this we get x = 13

That is       213 byte size of a page.

Let page size  = 2p   bytes (p is page offset )

now, number of page entries in 1st level = 2p / 4 = 2p-2 bytes (as it uses 32 bit = 4 byte Physical address)

Similarly in 2nd level -> 22(p-2) and considering 3rd level it would be 23(p-2)

so, 23(p-2) * 2p = 46, p=13

so page size = 213 byte = 8KB (c)

Number of pages in cache = 1MB/8KB = 128 pages

Number of set in cache = 128/16 = 8

For any two synonym to map with same set they should be colored with

same color of that respective set. So minimum we need 8 colors for this mapping. (C)

if this is "16-bit" what would be the answer for pagesize?

A couple of questions..
1. "4 byte physical address" or 4 B PTE?
2. What does this mean? 2^3(p-2) * 2^p = 46
3. "No. of set in cache" or No. of set per page?

4. 128/16 not clear.. can you please explain this?

@Shree :Could you please elaborate the concept of these color bits needed ?? And  also explain how did you solve this .Solution you provided is a bit tricky to understand  .

Thank You