2,360 views
0 votes
0 votes

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

2 Answers

Best answer
1 votes
1 votes

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

edited by
4 votes
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.

Related questions

0 votes
0 votes
1 answer
1
Mrityudoot asked Mar 20
99 views
If Page size = Frame size is always true and offset in Logical address = offset in physical address holdsThen how/why Logical address size can come different than physica...
0 votes
0 votes
1 answer
2
0 votes
0 votes
2 answers
3
Unique_999 asked Aug 17, 2023
293 views
Can Any explain the relationship between The “ Word Size “ and “ Logical Address Space “