The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
969 views

A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows • Bits 30-31 are used to index into the first level page table • Bits 21-29 are used to index into the second level page table • Bits 12-20 are used to index into the third level page table, and • Bits 0-11 are used as offset within the page The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively.

tHIS QUESTION HAS BEEN ASKED PREVIOUSLY ALSO..BUT PLS EXPLAIN WITH A GOOD FIGURE

asked in Operating System by Boss (13.6k points) | 969 views
0

@arjun sir,please answer this question.

@arjun sir,here i am not understanding one thing,why are we calculating number of tables in each level and why are we considering physical address space for that and even if number of tables are to be calculated then number of entries in first level page table is 2^2 i.e 4,number of tables in second level should be 4 because each entry of first level will point to a page table in next level,hence number of tables at second level should be 4 with 2^9 entries in each table as  9 bits are there in virtual address space to refer to the second level.then number of tables in third level should be 2^11 similarly with 9 bits in each entry of third level page table.

i am very confused..please have a look at it.
0
i will answer it soon with good story
0
Oohky tauhin

2 Answers

0 votes
Best answer

Assume in rajngar extension..ghaziabad...the famous...GATEOVERFLOW  BUILDERS.. launched a project GATECSE APARTMENTS... 
builder  purchased certain amount..of land..and also assume land is available in bytes...64GB land they purchased(i.e in given in question 2^36 p.a)...now the size  room of  is fixed
as 4kbytes....so total no. of rooms = land available/room size = 64GB/ 4KB = 2^24 ...now every room has a number..so 24 bits are required to identify paricular room as there are 2^24 rooms..
now.....keeping in mind....GATE  2017.....parents decided..to buy..the rooms...one room for 1 child..a parent may have 4 child..then he has to buy..4 rooms..the rooms need not to be 
adjacent...they can be anywhere ...inside  APARTMENTS...

and it is also assumed that room is capable enough to fit child inside it...means room size is equal to child size ..now to keep information of there child..that where there child's room is located...parents are alloted..the rooms where 

they can keep information regarding there child..and each father is alloted the room...the size of room alloted..to father(third level) is diffrent from the child and is also called (third level page table) ....the room available to father have slots or partitions..& the no. of slots have to be fixed(same) for all the father's room....and  that slot....is 4BYTE  in length...if the parent have four child (assume..order..with age) youngest child's information is placed in the 1 slot & ..subsequently..rest also..will be placed..every slot may not be filled if a parent have 3 child & suppose slot allocted in the room for parent is 4..then 1 slot will be free

now consider question 
as we know 64GB memory(land) is available and frame size (room size...)..is 4kb
total no. of frames(rooms) = P.A.S/frame size=  64GB/ 4KB = 2^24 
now ..a particular father(third level) requires...how many bits to keep information about the room of child...in slot which is  of 4byte...means 4*8= 32 bits...
and we know..24 bits are required...to identify particular room...so out of 32 bits ..24 bits are used for addressing rooms...
similarly...
here slot is same page entry size.....and father is same as process(third level)..& child is same as pages of process...room is same as frame...that particular page is available in which frame..it takes 24 bits to identify....page frames 
now..there can be many fathers..and how many fathers can alloted rooms also depend upon land.. available in APARTMENT..assume..1st floor..rooms are allotted to father...now akriti asked a question why we are considering.. physical memory..for constructing..the page table evry time ...the 1st floor cannot be construced if land is not there...similarly..1st/2nd/3rd  level page table cannot be construced..if physical memory..is not there....page table is stored in main memory...
one father( third leve) roomsize(third level table size)  = no. of slots * slot size = no.of entries * entrysize = 2^9 *4byte = 2^11 byte
now no. of fathers(processes) that have rooms (page tables) ==p.a.s / third level page table size==2^36 byte/2^11 ==2^25...means to identify particular father's rooms ..25 bits are required.....means grand father of child & father of a father....requires..25 bits..to identify...his son(on 1st floor)..meaning..there by 25 bits out of 32 bits available must be allocted..in second level page table enrty..to idenify..particular..third level page table...
now..one..grand father(2nd level ) roomsize (2nd level page table size)==no. of slots * slot size = no.of entries * entrysize = 2^9 *4byte = 2^11 byte
no. of grand  fathers(2nd level ) that have rooms (page table) ==p.a.s / 2nd level page table size==2^36 byte/2^11 ==2^25..
means if a great grand father(1st level) want to know...about his son..he requires 25 bits....means there must be 25 bits in 1st level page table entry to locate particular..second level page table...

..now akriti says..there is 2^2 ..4 entries..in 1st level page table to ..so there must be 4 page table in second level...
first thing.. all the process may not have same pages...means if a table has 4 entries...and a process have 3 pages..so 1 slot is free..4 entries..doesnot..necessarily..means we have 4 page tables.////.in entries....information must b provided..of concerned pages..
next...akriti only considering..one 1st level..page table...there can be many 1st level page table...or there can be only one 1 page enough..to store information abt..2nd level page table..if it is big enough.....but..this has no concern in above question...we only need to find no..of bits required in 1 st level page table...to store info. abt 2nd level ....only 1 table is enough to calculate that..

answered by Loyal (9.9k points)
edited by
0
Tauhin,first of all,i would say that you have made a very very good and clear explanation to above problem.that would have taken a lot of your time,so thanks a lot.:-)

and secondly,i got the idea of your approach.one thing i want to ask that the page tables in second and third level have 2^9 entries each na because in virtual address space,9 bits are for pointing to second nd third level.am i right??
0

yes u r correctsmiley

0

in this figure

can you pls look into this figure..is it correct??

now my doubt...

we have got 2^25 tables in third level and according to 9 bits in virtual address space for pointing to third level,we have 2^9 entries in each page table of third level,so how 25 bits in the previous level i.e second level will point to page tables of third levell?i am not getting this 9 and 25 bits things...I.E if 25 bits of second level will point to one of the 2^25 tables of third level then how will we point to a particular page of third level page table?? 

+1

...don't get  confused...

1st level page table
page0  2bits 25 bits 
page1  2bits 25 bits
page2  2bits 25 bits to search in which 2nd level page table the page 2 is present assume 00000000 00000000 00000000 0
page3  2bits 25 bits
2nd level page table no-0(zero)
page0 //9bits 25bits to search page 0 of 2nd level page is available in which 3rd level page table 00000000 00000000 00000000 1
page1 /9bits  
....  
....  
...  
page 511 ///i.e 29  
third level page table n0-1
page0///9 bits 24 bits to search page 0 of 3rd level page table is available in which main memory frame..it contains frame no..
page 1///9bits  
page 2 ,,,,,  00000000  00000000 00000011
...  
...  
511//9bits  
main memory
frame 0///24 bits page 0
  page 33
frame 2 ...
frame 3 page 2
   
frame 224  

now consider for example let us assume 32 bit L.A.S...10 000000001 000000010 000000000000

NOW...in above address first two bits.. idenify the particular page..of 1st level i.e is 10 means page 2..now goto first level page table and in that search page 0 is available in which particular second level table..25 bits will tell u....here we consider "25 zeros 00000000 00000000 00000000 0" means in 2nd level pagetable no.0(zero) now after going to that zero page table . ....next 9 bits in the address will tell which page to access..////in the address 000000001 means access page 1 of  2nd level pagetable no.0(zero)...now in that we again search for...25 bits 00000000 00000000 00000000 1 will tell which third level table...here third level page table n0-1 as addrsss in 25 bits tell...now again 9bits of address will tell which page to access which is

 000000010 means page-2 of  third level page table n0-1...now in that 24 bits will tell in which frame page 2 is available..24bits here 00000000  00000000 00000011 (3)means in frame-3 page-2 is available...

0
I GOT U TAUHIN,THAT MEANS THAT 25 BITS OF THE PAGE ENTRY OF A PARTICULAR PAGE TABLE will tell which page table to look at then 9 bits from virtual address space will tell which page to look at in that prticular page table selected.

just one thing,in your first level page table representation,the 01 bits from V.A point to 2nd entry that is 1st page of first level page table,that is second row,but in your table drwaing,you have pointed to page 0 of  frst level,i mean,u have made entry in page 0 of first level and 01 refers to page 1,i understand that you are finding page 0 in the memory,can you clear my doubt??(if possible :-P)

PS - thanks for clearing this much
0

yes..u r right..i made wrong...it myself....so that ..hours..of wasting..my time...if u did n't understood ///i will commit suicide..but..u catched..that up...hope u saved my life..i have updated it...surprise

0

hahah..you have not wasted your time tauhin,teaching someone is a noble deed..cheeky keep it up..:-P..and i completely got your solution,so be relaxed.

thanks aginyes

PS-you have again made entry in page 2 while it should be in page 1..hahahlaugh,,anyways,i have got it all

0
now... i need to relax...for 2 days...else i will bcom mad
0
@akriti how 2^25 u r getting...
0
I copied answer from previous post for the same question as my answer is coming same.Can anyone explain the flaw in following approach?

 

Here what I want to know is what is the total size required by the page tables?
My explanation: Number of frames : 2^36/2^12=2^24 , now each third level page table can address 2^9 , so total number of third level page tables required to address PA is 2^24/2^9=2^15
Now we have 2^15 entries in the second level page tables , but each second level page table can adres 2^9 pages , so 2^15/2^9 =64 page tables for second level
Now 4 entries per first level PT , and we must address 64 entries for the first level , so 64/4 = 16 first level page tables
------------------------------------------------------------------------------------
Is the above explanation correct?
So : Number of first level PTs=16
Number of scnd level PTs=64
Number of third level PTs=2^15

Am I crct in the abve explanation or is there something wrng?
0
@Arjun Sir,

In third level we have 2^9 enteries and we need to point to 2^24 frames of main memory,so we should have 2^24/2^9 page tables for third levels?Why are we takng entire physical memory size?we need to know how many frames are there and not the entire address space.please help
+4 votes

Answer :

Virtual address size = 32 bits
Physical address size = 36 bits
Physical memory size = 2^36 bytes
Page frame size = 4K bytes ===> 2^2*2^10 ===> 2^12 bytes
No. of bits required to access physical memory frame = 36 - 12 = 24 (Here 12 is offset given in question )

All above information is given in question .I have not written anything new.
So in third level of page table, 24 bits are required to access an entry.

9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes.

So size of second level page table is (2^9)*4 = 2^11 bytes.

It means there are (2^36)/(2^11) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. Similarly, the third page table needs 25 bits to address it.

answered by Boss (45.3k points)
0
Why are you considering physical address space for calculating number of page tables at each level?? Is this the way we calculate numbwr of page tables or is it particularly for this question??
0
It is given in question see this

Bits 21-29 are used to index into the 2nd level page table. ====>9 bits
0
yea.that i know

Mthat means there are 2^9 entries in second page table...but how. Is it related to my doubt??
0
What is understood from your doubt is how to get Page table rt ?

well page table is as big as no of pages in the process and each entry will contain some bits

so PTS = no of frames * size of each entry

this is how we calculate PTS in general .
0
noo..thats not my doubt..what i think is in the frst level there are 2^2 entries because 2 bits are used to refernce frst level and each page of first level points to each page table of second level,hence there should be 4 second level page table with each page table having 2^9 entries as 9 bits in virtual address spce are used to point to second level and hence each page table entry of first level should contain 9 bits to refer to second level page table entry and similarly for third level..

thats my point of view of thinking..is that wrong??
0
what is the problem in this approach??is it not true that each page of one level points to next level page table??and hence from this,number of entries in previous level is equal to number o fpage tables in next level..am i right or wrong??
0
yes you are right ?
0
then why is question being solved by other approach only??your approach is right but mine is also correct..how will i get to know whther the question is to be solved by trick or this one??
0
just follow the standard approach .don't get into shortcut initially if you do some practice on it then you'll get the intuition to apply shortcut .there are lots of shortcut .but you have to patiently practice a lot on it ..give it some time definitely you'll get the result.
0
it is not a shortcut..it is actualy written in book..i am applying no shortcut here..its a different approach,if it had been a shortcut then my answer would have been same as yours but because i am thinking differently that is why i am getting diff answer..any ways thankyou

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

40,812 questions
47,492 answers
145,717 comments
62,249 users