+51 votes
11.8k 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$
asked
edited | 11.8k views
+2

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

0
What is the difference? Could you please elaborate?

## 6 Answers

+96 votes
Best answer
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 \text{ KB}$

Correct Answer: $C$
answered by Veteran (400k points)
edited ago
+6
I'm not an idiot to do that FYI.
+1

Prove it if you can @suvasish pal

–5
i can not remember the question..next time when i again see i will inform u then and there :)
+11
Are you an *** student to behave like him? If you cannot prove what you accuse others of, you wont be continuing here any longer.
+3
@suvashish , i think made easy had copied from here .
0
yes u may right sourav.
0
What is significance of information given for cache memory?
0

@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.?

0

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

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

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}.$

Therefore Logical address split is

 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

answered by Boss (17.4k points)
+1
@Sachin solution is right,

Actually page table contains many number of PTEs. And each each PTE contains different pages .
+4
I did not get u, U r saying this solution is right and then u are explaining something.
What exactly u mean ? :P
0
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.
+1
Thanks. I always do it by this method only. Easy and Fast. :)
+1
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.
+2
Where is it given that all page tables occupy one page?
+1
Good solution @sachin.
+1
Hello sachin

I'm highly impressed by level of your knowledge and way to approach problems.It's a pleasure to read your answers.

Thanks for your time and contribution.
0
@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?

thanks in advance.
0

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 ;

+1

@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.

0
I understand what the three 'p-2' bits represent here. But what do the last 'p' bits represent?
0
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??
+10 votes

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

answered by (101 points)
edited
0
Total virtual address space = (x/4 * x/4 * x/4) * x/4 = 246

∴ x4/26 = 246

explain
0
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.
0
nice approach.
+5 votes

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

answered by Active (2.1k points)
0
@arjun sir is this a correct solution?
+3 votes

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.

answered by (261 points)
+2 votes

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)

answered by Active (3.5k points)
0

"32–bit physical address"
if this is "16-bit" what would be the answer for pagesize?

0

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?

0
@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  .

Please explain .

Thank You
Answer: