The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+44 votes
8.6k 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 in Operating System by (75 points)
edited by | 8.6k 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 :)

6 Answers

+78 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}$
answered by Veteran (355k points)
edited by
–2

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

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

+1
Which question? And Sachin's answer also has the same assumption.
–6
don't copy made easy solutions
+4
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 :)
+8
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
@suvashish,you do not pay any one here to get the explanation .
0
yes u may right sourav.
+55 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 (15.9k points)
0
@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?
0
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 ;

0

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

 

 

+6 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 (81 points)
edited by
0
Total virtual address space = (x/4 * x/4 * x/4) * x/4 = 246

∴ x4/26 = 246

explain
+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 (2k 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 (255 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:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,018 questions
45,509 answers
131,698 comments
48,742 users