25,638 views

A computer uses $46\text{-bit}$ virtual address, $32\text{-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 $\text{(T1)}$, which occupies exactly one page. Each entry of $\text{T1}$ stores the base address of a page of the second-level table $\text{(T2)}$. Each entry of $\text{T2}$ stores the base address of a page of the third-level table $\text{(T3)}.$ Each entry of $\text{T3}$ stores a page table entry $\text{(PTE)}.$ The $\text{PTE}$ is $32$ bits in size. The processor used in the computer has a $1\;\textsf{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 $\textsf{KB}$ in this computer?

1. $2$
2. $4$
3. $8$
4. $16$

edited by

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 :)

What is the difference? Could you please elaborate?
In Question its given that cache block size is 64 bytes, isn't this equal to main memory frame/page size?
Can we say that No. Of Entries In Inner Page Table = No. Of Pages In whatever in larger between (PAS,VAS)?

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 page size) = $\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}$
$\implies x^4 =2^{52}$
$\implies x = 2^{13}$
$\implies x = 8\;\textsf{KB}$

Correct Answer: $C$
by

That's an assumption -- which ideally should have been in question.

then why have we not assumed it in question https://gateoverflow.in/490/gate2008-67#c61309

I am confused :(

That assumption is usually taken -- but not always. That 2008-67 is explicitly looking for "that assumption". I mean it was meant to give negative marks for those who by-heart the assumption. That question and its options -- that is the reason why this assumption is not valid there.
reshown 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.
reshown by
reshown by
I'm not an idiot to do that FYI.

Prove it if you can @suvasish pal

reshown by
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.
yes u may right sourav.
What is significance of information given for cache memory?

@Arjun

Why have you take PTE of T2 as 4Bytes, while in Gate 2008-67 question you have told that PTE might vary with level of tables.?

Because question says "T1 stores the base address of page of T2. T2 stores the base address of page of T3."

Take the page size as 2^x and follow the above steps to derive the page size, solution will be simple to cal then.

https://gateoverflow.in/379/gate2013-52?show=153518#c153518

@Arjun Sir,

What is that assumption that you are referring to $?$ Which is valid here but not there.

Should we bothered that Total table page size at T3 = $2^{48}/2^{13} which\ is\ 2^{35}\ bytes \ has\ exceeded\ the\ 2^{32}\ bytes\ possible\ in\ Main\ memory.$ ?

Maybe I missed something.

“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.” So this was irrelevant info for this question right…., I was trying to make use of this

edited by
Good explanation :)

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 $2^p$ Bytes.

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

Number of entries in any page of any pagetable =page size/PTE $=\frac{2^p}{2^2} = 2^{p-2}.$

 p-2 p-2 p-2 p

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

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

$⇒p=13.$

Therefore, page size is $2^{13}$ 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.
@Sachin Mittal 1

Here is an observation,

In this question , it is given that PTE = 32 bits, and generally PTE hold frame number, so here PTE size = Physical address,  if i think in this way frame size (which is same as page size) = 1B

can you please tell me where i'm going wrong?

can u prove it---

Number of entries in any page of any pagetable =page size/PTE

bcoz of  CASE 1-  no. of entries= process uses by page table size/page size

CASE 2-  no. of entries= logical address - page size ; for example logical address 2n  and

page size= 2 then  no. of entries= 2n/2k ;

@Sachin Mittal​​​​​​​

You write that Logical address split in

 p-2 p-2 p-2 p

How can you taken this please explain?

Because this condition is taken when it was given in the question that all page table fits in a single page.

I understand what the three 'p-2' bits represent here. But what do the last 'p' bits represent?
But it is explicitly given in question that T1 and T2 refer to base address of a table (which will be equal to address of a frame in Main Memory) whereas T3 is having PTE of 32 bits. Now, since PTE may include frame address + some other info( like dirty bit) wouldn't it be incorrect to assume entry in each table to be of same size??
@Sachin bro, i have same doubt as of @Matrix
why the PTE entry size for each of the page table same ?

My understanding:

As the inner  page table (like T1 and T2) entry in each page table is used to store the base address of the page table in the next level.And the page tables are stored inside the frame in the physical memory.So each entry stores the physical frame address.Now the outer page table(T3) entry also stores the physical frame address.So logically the size of the page table entry(PTE) should be same in all the page tables.

Am I right ?
As the inner  page table (like T1 and T2) entry in each page table is used to store the base address of the page table in the next level.And the page tables are stored inside the frame in the physical memory.So each entry stores the physical frame address.Now the outer page table(T3) entry also stores the physical frame address.So logically the size of the page table entry(PTE) should be same in all the page tables.

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

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

∴ x4/26 = 246

explain
Here x^4/4^3=2^46     he just simplified 4^3 as 2^6

so finally x^4=2^52

x=2^13=8*2^10 which is 8KB.
nice approach.
Plz explain how  take t1=x/4.
Why are we taking page table size as same as page size ?

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

by

### 1 comment

@arjun sir is this a correct solution?

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)

by

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

edited

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

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.