The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
118 views

For a computer architecture with multi level paging, a page size of $4 \hspace{0.1cm}KB$, and $64 \hspace{0.1cm} bit$ Physical and Virtual address:

  1. What is the smallest possible size for a page table entry, rounded up to a power of $2$?
  2. using your result above, and assuming a requirement that each page table fits into a single page, How many levels of Page tables would be required to completely map the $64 \hspace{0.1cm} bit$ virtual space?
asked in Operating System by Junior (861 points)
edited by | 118 views
0
How you got 4?
0
sorry it will be 6 level and PTE=16B
0
what is ans?
0

Yes  total 6 level Page tables would be required to completely map the 64 bit virtual space.

But i did not understand your approach in given answer.

i think @arungate has given the right approach .

0

for (b)

what i am getting is :

Total No. of Pages= 252

Page Size= 212 Bytes and Entry size from part (a) 8 Bytes (64 Bits).

No. of Entries=Page Size/Entry Size=212-3=29

So Page Table Size=252 * 8 Bytes = 255 Bytes

Here we cannot fit Page Table into Single Page (255 --> 212)

So No. of Pages Required to fit a Page Table = 255/212  = 243 Pages

Here as per Question Each Page Table fits into Single Page so we would required 243 Page Tables to Store 255 Bytes.

Now No. of Levels in Paging:

Last Level              : Total Page Table  =243

Second Last Level : Total Page Table  =243/29 = 234

Third Last Level     : Total Page Table  =234/29 = 225

Fourth Last Level   : Total Page Table  =225/29 = 216

Fifth Level               : Total Page Table  =216/29 = 27

So Total No. of Levels=6

0
part a is trivial that answer is $64$.

Part $b-:$

$\text{PTE(Page table entry size)=64 bits}=2^6 \text{bits}=2^3 \text{byte}$  

 

for level $1$,

# of pages$=\frac{2^{64}}{2^{12}} $

 

size of page table $=\frac{2^{64}}{2^{12}} \times 2^3=2^ {64} \times (\frac{1}{2^{9}})$

 

According to question

$2^ {64} \times (\frac{1}{2^{9}})^{x}=2^ {12}  \Rightarrow  x=6$
0

Anand. can we generalize this as below?:

If Each Page Table fits into a Single Page Then

$2^{LA} X (\frac{1}{2^{No. of Entries}})^{x}=Page Size$

Where, x is No. of Levels in Paging.

+1

It is not generalised like this .This form is due to the data given.I am writing  each steps below

 

$\text{number of pages}=\frac{2^{64}}{2^{12}}$ as total size of Virtual address space is $2^{64} B$

and size of each page is $2^{12} B$


Now size of page table$=\text{number of entries in page table i.e number of pages} \times \text{size of each entry}$

$\text{size of each entry}=64 bits=2^3 B$ from part a)

 

 


suppose we have only single level,then size of page table $ =\frac{2^{64}}{2^{12}} \times 2^3=2^{64} \times (\frac{2^3}{2^{12}})$

for 2 level,

$=\frac{2^{64} \times (\frac{2^3}{2^{12}})}{2^{12}} \times 2^3=2^{64} \times (\frac{2^3}{2^{12}})^{2} $


In the question it is given that size of page table should fit into single page for x level

 

i.e  $2^{64} \times (\frac{2^3}{2^{12}})^{x}=2^{12} \Rightarrow 2^{64} \times (\frac{1}{2^{9}})^{x}=2^{12}$

0

Ok got it now!

Thank you :) @Anand

0

@Anand

One question i am having that What will be the no. of bits required in each level in LA Addressing.?

2 Answers

+1 vote
(a) Physical memory size = $2^{64}$ bytes

Page size = $4$ Kbytes

So, number of pages = $2^{64}$$/2^{12}$ = $2^{52}$

So, a page table entry should have atleast $52$ bits.

Rounding to the nearest power of two, the answer is $64$.

 

(b) According to our above result, a page table entry needs $64$ bits = $8$ bytes.

So, number of entries in one level of page table is $4$ KB$/$ $8$B $= 2^9$

So the first level can address $2^9$ x $2^{12}$ $=$ $2^{21}$ bytes

Remaining addresses $=$ $2^{64}$$/$$2^{21}$ $=$ $2^{43}$

For this, we need $43$$/$$9$ $=$ $5$ more levels.

Therefore, the required levels of page tables is 5 + 1  $=$ $6$.
answered by Active (1.3k points)
0
@arungate How many bits would be available for storing other information ?
0
52 bits is enough out of 64, so 12 bits I guess.
0
52 bits are for number of pages

not for PTE I think
+1

@arungate you are correct 

srestha Here Page Size= 4KB=212

so Page Offset (d)=12 bits

Now 64-12=52bits

so for Page Table entry 52bits are here for rounding of 2 it will be 64 Bits or 8Byte.

0
who told 52 bits are PTE?

where r u getting this thing?
0 votes

Let size of a page table entry be  x bytes 
Page Table Size  = 4 KByte = 212B - requires 12 bits for addressing. 
Logical Address Space = 264 B

Now, we know

Size of page table=(Logical Address Space/Page Size)*Page Table Entry Size

Size of 1st level page table = (264/2​​12)*x

Size of 2nd level page table = (264/(2​​12)2)*x2

........................................................................

........................................................................

like that

Now, last level of page table fits into single page

So,  (264/(2​​12)y)*xy  = 212

Using trial and error method and y=6

we get x6=224

then x=24B=16 B

Size of PTE=16B

and  6 level of page table are required

answered by Veteran (98.3k points)
edited by
0

Page Table Size  = 4 Byte = 212B - requires 12 bits for addressing. 

Can't get this.... Isn't it 8B? both physical and virtual space given as 64 bits...

 

0
how 8B?
0

arungate Actually i guess there is typo its 4 KByte = 212 B

right? @srestha

0
I have edited more

See if it is clear?
0
yea corrected
0
@srestha i think you have made a mistake in eqtn,see my comment above
0
@Anand

Can u show me any calculation mistake in my calculation?
0
I suppose u all guessing 64 bit as PTE

but it cannot be, if we go with fully with the equation
0
$\text{PTE=}2^6bit=2^3 \text{byte}$
0
but u r not getting 64 bit from question, u r getting only 52 bits

by the way, if there any calculation mistake u got in my calculation?


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

40,805 questions
47,492 answers
145,714 comments
62,249 users