48,675 views

A processor uses $36$ bit physical address 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 2nd level page table.
• Bits $12-20$ are used to index into the 3rd level page table.
• 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

1. $\text{20,20,20}$
2. $\text{24,24,24}$
3. $\text{24,24,20}$
4. $\text{25,25,24}$

Since,the virtual address space is 2^32 so, number of pages in the virtual address space should be 2^32/2^12=2^20.... and,so the number of page table entries in the last level should be 2^20 only...
Why are we considering physical address space here??
Because then we would be wasting the remaining physical address space.
what you mean wasting physical memory size?
@Arjun but since the logical address space is 2^32 and physical address space is 2^36.Isn't it implied that the CPU will not be able to address the entire physical memory ?? Please clarify?
Only on a uniprocessor system. For multi processor system, different processes can map to different memory spaces (page tables being different).
@Sir Arjun,Shared Memory in Distributed Environment.Isn't it?All d more architecture varies from processor to processor.:)
edited by

Important point --> Page tables need not to be page aligned.

Notice in this question virtual memory is used to create a illusion that  actual physical memory size is less. :)

PS: Although, I should not write thanks message because sometimes it is considered as spamming but I can not control ( Bcz you guys has done really good job) So Thank You @Aruj ji and @Sachin Mittal 1 ji.

This question has maximum views.10k+.:)
Please make a video on this concept so that it will be very helpful because it was mostly confusing to all students .
edited by

For those who did not understand the solution and especially those who have big misconception that multi level page tables are used only when page do not fit in a single frame of main memory:

3. Come back to solution.

Everything will fall in place.

@tusharp,

Your Link That you have mentioned in the 2nd Point of the Above Comment is not Present. Please Update the Link so that it will be helpful for many of us.

Lmao , this question cleared so many frikkin doubts that I didn’t even know I had . :)

@Arjun
@Sachin
@Bikram

Please I have one simple doubt.
We are using $25 bits$ in Page Table -1 but PTE is of  4 bytes, $4 \times 8 = 32 bits$ , but we are only using $25 bits$ out of it and similarly, in Page Table -2 we are again only using $25 bits$ out of 32 bits and in Page Table 3 we are using $24 bits$ out of $32 bits$ . The rest of the bits are used for some other information? Can I assume this?

Please correct me if I am wrong any where.

Pls, help! Really need it! Thank you so much!

I think, @Arjun sir, we are using PAS just because, PAS is greater than VAS
In actual the no. of such page tables depend on the memory usage of a given process, but for addressing we need to consider the worst case scenario

edited

@Vinspatel That is similar to asking why do we find how many frames in a physical memory are there in total, even though a process might not use all those frames. That's because it gives us the addressing bits as we've to assign unique address to each frame.

Same concept is applied here too, in order to find the addressing bits so that each block of page table can be uniquely identified, we gotta find how much blocks of page table can actually fit in a given main memory.

Physical address is $36$ bits. So, number of bits to represent a page frame $= 36-12 = 24\ bits$ ($12$ offset bits as given in question to address $4$ KB assuming byte addressing). So, each entry in a third level page table must have $24$ bits for addressing the page frames.

A page in logical address space corresponds to a page frame in physical address space. So, in logical address space also we need $12$ bits as offset bits. From the logical address which is of $32$ bits, we are now left with $32-12 = 20\ bits$; these $20\ bits$ will be divided into three partitions (as given in the question) so that each partition represents 'which entry' in the $i^{th}$ level page table we are referring to.

• An entry in level $i$ page table determines 'which page table' at $(i+1)^{th}$ level is being referred.

Now, there is only 1 first level page table. But there can be many second level and third level page tables and "how many" of these exist depends on the physical memory capacity. (In actual the no. of such page tables depend on the memory usage of a given process, but for addressing we need to consider the worst case scenario). The simple formula for getting the number of page tables possible at a level is to divide the available physical memory size by the size of a given level page table.

$\text{Number of third level page tables possible} = \frac{\text{ Physical memory size}}{\text{ Size of a third level page table}}$
$\qquad = \frac{ 2^{36} } {\text{Number of entries in a single third level page table} \times \text{ Size of an entry} }$
$\qquad = \frac{2^{36}} {2^9 \times 4} \because \text{ (bits 12-20 gives 9 bits)}$
$\qquad = \frac{2^{36}}{2^{11}}$
$\qquad =2^{25}$

PS: No. of third level page tables possible means the no. of distinct addresses a page table can have. At any given time, no. of page tables at level $j$ is equal to the no. of entries in the level $j-1$, but here we are considering the possible page table addresses.

http://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html See Problem 3, second part solution - It clearly says that we should not assume that page tables are page aligned (page table size need not be same as page size unless told so in the question and different level page tables can have different sizes).
So, we need $25$ bits in second level page table for addressing the third level page tables.

Similarly we need to find the no. of possible second level page tables and we need to address each of them in first level page table.

Now,

$\text{Number of second level page tables possible} = \frac{\text{ Physical memory size}}{\text{ Size of a second level page table}}$
$\qquad= \frac{ 2^{36} } {\text{Number of entries in a single second level page table} \times \text{ Size of an entry} }$

$\qquad = \frac{2^{36}} {2^9 \times 4} \because \text{ (bits 21-29 gives 9 bits)}$
$\qquad= \frac{2^{36}}{2^{11}}$
$\qquad=2^{25}$

So, we need $25$ bits for addressing the second level page tables as well.

Video Explanation for Multi-level Paging: https://youtu.be/bArypfVmPb8

(Edit:-
There is nothing to edit for such awesome explanation but just adding one of my comment if it is useful - comment. However if anyone finds something to add (or correct) then feel free to do that in my comment.)

by

Same doubts as srestha.
Why we are dividing VAS in to pages when it can easily fit in PAS ? As size of physical address is more than virtual address so why do we need to implement paging in this case!!

Thanks Arjun Sir for the wonderful explanation

Thanks Sachin Mittal 1 for the Brilliant Explanation and breaking the concepts in pieces. Understanding this is not very difficult but it's also not very easy.

By mistake i clicked on flag button for spam on your comment . Sorry about that. :)

I think 1 video for this particular concept is required as this concept is not discussed anywhere

If there happen to be only 224   frames in physical address space then how can we need more than 24 bits to address this memory?? Confused any help would be welcomed

Thank you so much for such great insights. Really helpful. :)

@ sir ,

Just a small doubt ,As we found that number of bits required to address next level page table are 26,25,24

But the size of PTE at each level is 4B..how the entry is maintained 4B at each level ..because rest of options like valid dirty will take same space in each entry.

4 bytes doesn't mean all bits are in use. When we use 25 bits for address we still have 7 extra bits for page protection and replacement policies.
Got it sir,,thanks
• Arjun Sir,
• If there happen to be only 2^24   frames in physical address space then how can we need more than 24 bits to address this memory? I understood ur explanation that page table entries maybe of variable sizes but how does it all actually plays out?

Process thinks that MM is divided into Frames and insert data in some frames out of 2^24 and Page tables thinks that MM is divided into chunks of size 2^k and insert page tables some out of 2^25 chunks, won't there be a possibility of processes and page tables overlapping?

@Arjun @Sachin Mittal 1 @Debashish Deka @srestha (sirs) if we page the physical address space then how does the mapping from virtual to physical address takes place?Is virtual address space is also paged ?but why do we need to page the physical address space when processes can work only 4 GB VAS?

@Arjun Sir, @Sachin Mittal 1 Sir, please reply, 25+25+24=74 right? but Physical address space is not 2^74 right?

@Arjun

Hello,  I do not quite follow the explanation you have given. According to my understanding , each page table has to be stored in the main memory (irrespective of levels ,also TLB is not assumed here). From the virtual address, we could select the index of the page table(s) , and corresponding index values always contains a frame address (because the page table/page pointed by that particular index has to be stored in main memory). So ,since the PAS is 24 bits ,we only need in 24 all page level entries to address the next level page table. I thought about this a lot and cannot find any flaw in my reasoning.

@Arjun-Awesome Answer and Awesome Assignment questions.They really now made me good in multi-level paging concepts.Thank you sir. :)

I understood the answer sir.... but in general...we r given 12 bits for offset and 20 bits for page table entries..so how can we get 25 bits for addressing pages..the virtual address is only 32 bit.....

In general we  load the required page table to physical memory when needed....so with 2^9 page table size in third level we r accessing 2^24 frames means we have 2^15 page tables in third level and we load required page table when needed.so only 9 bits are sufficient.....

I think in question it is asked in general which is not possible.......am i correct sir..........

If 25 bits are required in all levels we can go for single level paging..

Sir if we gone for single level for this question we have only 20 bits for page table and we require 24 bits for addressing the frames.....is it okk not to have all frame addresses in page table.....?????....

I have a doubt here..

3 rd level page table is of size $2^{11}$ Bytes. So with respect to 3rd level page table, main memory is partitioned into blocks of size  $2^{11}$ Bytes and a 3rd level page table sits into one such block.

So there must be a base address to that block right? My question is how do we get that base address of block(36 bits) in which 3rd level page table sits..

we just get the block number(25 bits) from the 2nd level page table and 9 bits from the address to index into the block(i.e. the 3rd level page table) .

where am i going wrong??

http://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html

In the 2nd sub problem of 3rd problem, they don't have this issue because they have taken entire physical address in each page table entry...

How can the number of page tables possible in a process depend on the size of physical memory?

I think there are 2^24 frames possible so number of bits required to address those frames would be same i.e 24 in all levels.
edited by

As there will be 4 entries in first level page table. So at max it can address 4 second level page tables. But we have almost 2^25 second level page tables. So my question is how first level page table will address these many tables?

As the process might not use all the page tables. So, will at a time maximum 4 second level page tables be addressed which are being used by the process, by referring their respective addresses from first level page table.

Please tell me the addressing way of these huge amount of tables. @Arjun sir.

@Arjun i understood that page table size need not be aligned with the actual page size, but that implies that a page table needs to be distributed among different frames, because it can be a few pages long.

In that case, say for example a second level page table has 2^12 entries, and each entry is 32 bits (4bytes) long, therefore page table size is 8KB, and my frame size (page size) is 4KB, that means the second level page table would be stored in 2 pages, and therefore 2 frames in the physical memory. Now, in the first level page table, there would be only one entry per 2nd level page table, and it would point to only one of the 2 frames in which the page table is stored.

How would this work? Am i thinking in the wrong direction by assuming that page tables (even though they need not fit in a single frame) are divided into pages and placed in random available frames?

Also, in the homework questions link you provided, they mention

“The top-level page table should not assume that 2nd level page tables are page-aligned. So, we store full physical addresses there”

But in this case you are only considering 25 bits to address a 3rd level page table from a 2nd level page table. Please help. let me know where im going wrong!

relly thanx man you saved me from maze of pagging

Total no. of physical frames = 2^(36)/2^(12) = 2^24
Therefore, bits needed to address a physical frame = 24 .
Now, A 3rd level PTE[Page table entry] contains  "bits to address a Physical frame"[final mapping from virtual to physical address] + valid/Invalid bit + some other bits[R/w etc.] .

But, question specifically asks for only "bits needed to address the next level page table or page frame".
So, the bits needed to address the page frame is 24.

A 2nd level PTE[Page table entry] contains  "bits to address a Physical frame"[Physical address where a 3rd level page resides in main memory ] + valid/Invalid bit + some other bits[R/w etc.]
So, the bits needed to address the page frame/next page table is 24.
Similarly,
A 1st level PTE[Page table entry] contains  "bits to address a Physical frame"[Physical address where a 2nd level page resides in main memory ] + valid/Invalid bit + some other bits[R/w etc.]
The bits needed to address the page frame/next page table is 24.

Hence , the answer is B .

See figure 2 here for reference http://www.cs.berkeley.edu/~kamil/teaching/sp04/031104.pdf  .

by

You have assumed that page table size is same as a page size.
edited by
Page table size is of no use here . A PTE contains the address of the physical frame from where the next level page table starts[The next level page table may span many contiguous frames ; to find the required PTE in this table we use the Bits in the Virtual Address(for that specific level) to index into it ] .

Anyway, In this case every page table comes inside a single physical frame .

2[1st level table index]   9[2nd level table index]  9[3rd level table index]  12[offset in the final physical frame]
So, the 1st level table has 2^2 = 4 PTE   [i.e 4 pointers to 4 different 2nd level tables]
the 2nd level table has 2^9 = 512 PTE  [i.e 512 pointers to 512 tdifferent 3rd level tables ]
the 3rd level table has 2^9 = 512 PTE  [i.e 512 pointers to 512  final physical frame ]

Assuming a PTE of maximum 4 Bytes , the maximum space a page table[of any level] can take is 2^11 bytes [less than a frame size].
Note : N page tables of  2nd (or 3rd) level  will take  N physical frames for each page table respectively.
Exactly, when the page table size is less than the size of a page, we can have more number of page tables than the number of pages possible. i.e., consider page size as the size of the page table and see how many page table entries are required.
this question is asking about  only page frame  bit ,is it ? then why we are calculate all these, it is simply 24 bit,24,24  ..
24 bit for lowest level is fine. But how 24 for other two?
frame no bit remain same for all level page table .because at all level, page table entry is same ...
No. There is no rule like that. You can see the link given in the answer.
sir ,page table entry size is same  for all level . and PTE contain frame bit . so it also remain same.
No. Where you saw this?
from tanenbaum ..in chapter 4 ,structure of page table entry , here also PTE is 4B and it is same for all level of paging then frame bit also same na.. sir am talking about frame bit not page entry address bit

okay. But page frame bit is there only for last level page table as that is the only level referring to a page frame. All previous levels refer to the next level page table. Now, the page table it self can be paged and there are two possibilities

1. Page table page can be of the same size as page frame
2. Page table page can be of a different size

Unless specified we can't assume case is 1 though that is common. This question actually is meant to check this concept only. Here, case is 2.

you are mistaken something  .

page size and frame size must be of same size . Page table entry (aka PTE) minimum must contain frame address (mandatory) plus it sometimes also contains additional data (like flag reference bit ) . so PTE differ .
ohk arjun sir

You can solve these questions- very good ones.

@Arjunsir by "page table page" you mean page table entry size? i.e. 4 bytes?
@resilientknight

"@Arjunsir by "page table page" you mean page table entry size? i.e. 4 bytes?"

No, as i think, the 'page table page' means that during paging the page table itself, the size of page (that will be result of paging page table), and it is different from the actual page size that is given 4KB.
@Rohan7980,Look Page Frame Size is 4 KB n d page table is 4 Bytes.Why to confuse?
arjun sir they are asking simply for PTE bit..it which is fixed in all page table entry.
So, does that mean the page tables are not present in frames?
"Page tables in frames" means?

Answer by Arjun Sir and Sachin Sir are really great :)

I am just trying what I understood and hope it will be helpful for aspirants like me.

by

OK,YOU HAVE SAY THAT WE NEED 2^25 TABLE AT LEVEL 3 AND THAT'S WHY WE NEED 25 BIT IN SECOND LEVEL FOR ADDRESSING 3rd LEVEL PAGE TABLE.NOW SEE THIS

AT SECOND LEVEL WE STORE 2^25 ENTRIES AND PAGE TABLE SIZE AT SECOND LEVEL IS (2^9)*4=2^11 byte.SO NUMBER OF TABLE WE GET AT LEVEL 2nd IS (2^25)/(2^11) =2^14.

SO AT LEVEL 1st WE MUST HAVE 14 BIT TO ADDRESS TABLES OF 2nd LEVEL

CORRECT ME IF I AM WRONG
SECOND THING IS THAT IF YOU CONSIDER THAT WE HAVE TO  PERFORM (2^36)/(2^11) TO OBTAIN NUMBER OF PAGE TABLE AT LEVEL 2nd THEN MY QUESTION IS WHY??

AS WE KNOW THAT IN MULTILEVEL PAGING CONCEPT WE HAVE TO FIND THE PAGE TABLE ADDRESS OF NEXT LEVEL AND FROM THAT NEXT LEVEL PAGE TABLE WE HAVE TO FIND THE ADDRESS OF NEXT LEVEL PAGE TABLE ,AND THIS PROCESS CONTINUE DEPENDING ON LEVEL OF PAGING.

SO IN 4 LEVEL PAGING IF WE CONSIDER LAST PAGE TABLE THEN IT MUST CONTAIN ADDRESS OF PAGE TABLES OF 3rd POSITION.IT IS NEVER GOING TO CONTAIN ADDRESS OF WHOLE PHYSICAL ADDRESS SPACE.IAND IF IT GOING TO CONTAIN ADDRESS OF DIRECTLY PHYSICAL ADDRESS SPACE THEN WHY WE APPLY MULTILEVAL PAGING,JUST ONE PAGE IS ENOUGH.

CORRECT ME IF I AM WRONG

TO ALL THE CONFUSED GUYS LIKE ME I WILL MAKE EVERY THING CLEAR;;

WHATEVER WE HAVE LEARNT IS 100% CORRECT..... SO BE HAPPY   SEE HOW

1-- THIS QUESTION DUE TO THE USE OF JUST ONE WORD IS MAKING EVERYTHING CONFUSING AND WE ARE NOT SEEING THAT WORD.

A processor uses 36 bit physical address and 32 bit virtual addresses, with a page frame size of 44 Kbytes. Each page table entry is of size 44 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 2nd level page table.
• Bits 12−20 are used to index into the 3rd level page table.
• Bits 0−11 are used as offset within the page.

The number of bits required for addressing the next level (SEE THE DIFFERENCE HERE HERE WE REMOVED THE WORD PAGE TABLE) page frame in the page table entry of the first, second and third level page tables are respectively.

SO THIS IS WHAT WE HAVE LEARNT EVERYWHERE . HERE EVERYTHING WILL BE DIVIDED INTO FRAMES WHICH IS SAME IS PAGE SIZE. AND THUS NOW EVEN IN CASE OF MULTILEVEL PAGING IF THE PAGE TABLE OF INNER PAGE TABLES ARE DIVIDED INTO PAGES OR FRAMES (SINCE PAGE SIZE=FRAME SIZE) THEN THEN FOR FINDING THE NEXT LEVEL PAGE FRAME IN THE PTE WE JUST NEED THE NO OF BITS REQUIRED TO REPRESENT FRAMES WHICH IS 24.

BUT THEY HAVE CLEARLY GIVEN

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.

IT CLEARLY MEANS THAT SINCE 3RD LEVEL WILL BE POINTING TO THE ACTUAL FRAMES WHERE THE PAGES OF THE PROCESS ARE PRESENT IN THE MM HENCE THEY COULD BE PRESENT ANYWHERE IN THE MM FRAMES AND WE HAVE 2^24 FRAMES HENCE WE NEED 24 BITS FOR SURE AT 3RD LEVEL PAGE TABLE .

SO  EITHER B OR D COULD BE POSSIBLE

a)    NOW 2ND LEVEL PAGE TABLE WILL BE POINTING TO THE 3RD LEVEL PAGE TABLE NOW SINCE IN THE QUESTION IT IS EXPLICITLY AND DELIBERATELY GIVEN THAT ADRESSING THE NEXT LEVEL PT OR PAGE FRAME HENCE HERE THEY MEAN PAGE TABLE NOT PAGE FRAME.

b)  ACTUALLY HERE IF WE DONT CONSIDER THE BITS DIVISION GIVEN BY THE QUESTION SETTER THEN WE NEED JUST 2 LEVELS OF PAGING UTILIZING VERY EFFICIENTLY BUT SINCE THEY HAVE NOT UTILIZED IT 100% HENCE THATS WHY WE HAVE TO THINK DIFFERENTLY .

c) AT LEVEL 1 WE HAVE 2 BITS IT MEANS WE HAVE 4 ENTRIES HERE SIMPLE. AND HENCE LEVEL 1 SIZE WILL BE 4*SIZE OF EACH ENTRY = 4*4B=16B

AT LEVEL 2 WE HAVE 9 BITS IT MEANS USING PAGE TABLE BASE AND LEVEL 1 IF WE GO TO A PARTICULAR FRAME IN LEVEL 2 THEN HERE ENTRIES PER PAGE/FRAME = 2^9  AND HENCE LEVEL 2  EACH PAGE/FRAME    SIZE WILL BE 2^9 *SIZE OF EACH ENTRY = 2^9*4B=2*11B

SEE WE HAVE PAGE SIZE =2^12 B BUT WE ARE USING JUST 2^11 IT MEANS WE ARE USING JUST THE HALF SIZE OF THE PAGE

AT LEVEL 3 WE HAVE 9 BITS IT MEANS USING PAGE TABLE BASE AND LEVEL 1 AND LEVEL 2 WE WENT TO EXACT FRAME IN LEVEL 3 THEN HERE ENTRIES PER PAGE/FRAME = 2^9.    AND HENCE LEVEL 3 EACH PAGE/FRAME SIZE WILL BE 2^9 *SIZE OF EACH ENTRY = 2^9*4B=2*11B

SEE WE HAVE PAGE SIZE =2^12 B BUT WE ARE USING JUST 2^11 IT MEANS WE ARE USING JUST THE HALF SIZE OF THE PAGE .

THATS WHY WE HAVE TO GO A/T THE QUESTION WHICH CLEARLY MEANS THAT PAGE TABLES ARE NOT DIVIDED INTO PAGES RATHER THEY HAVE BEEN DIVIDED INTO SOME CHUNKS OF SOME OTHER SIZE (NOT PAGE SIZE) SO HERE

DELIBERATELY I WILL USE THE TERM NO OF BITS REQUIRED FOR ADDRESSING NEXT LEVEL PAGE TABLE (NOT PAGE FRAME)  ..

SO NOW A/T LEVEL 2            LEVEL 3 HAS BEEN DIVIDED INTO EACH CHUNK SIZE IS 2*11B (EARLIER WHAT I HAVE MENTIONED AS SIZE OF EACH PAGE/FRAME).

SO FOR LEVEL 2 IT HAS TO LOOK INTO THE MM/ PHYSICAL MEMORY WHERE LEVEL 3  CHUNK WILL BE PRESENT AND THERE ARE CHUNKS OF SIZES 2*11B AT LEVEL 3 .... SO LETS CALCULATE HOW MANY SUCH CHUNKS ARE THERE = SIZE OF PHSICAL MEMORY / SIZE OF EACH CHUNK = 2^36/2^11= 2^25

THUS AT LEVEL 2 TO GO TO A PARTICULAR CHUNK OF LEVEL 3 WE NEED 25 BITS

d)   NOT AT LEVEL 1 WE HAVE TO GO TO A PARTICULAR CHUNK IN LEVEL 2 SO LEVEL 2'S EACH CHUNK SIZE = 2^11B(EARLIER WHAT I HAVE MENTIONED AS SIZE OF EACH PAGE/FRAME).

SO FOR LEVEL 1 IT HAS TO LOOK INTO THE MM/ PHYSICAL MEMORY WHERE LEVEL 2  CHUNK WILL BE PRESENT AND THERE ARE CHUNKS OF SIZES 2*11B AT LEVEL 2 .... SO LETS CALCULATE HOW MANY SUCH CHUNKS ARE THERE = SIZE OF PHSICAL MEMORY / SIZE OF EACH CHUNK = 2^36/2^11= 2^25

THUS AT LEVEL 1 TO GO TO A PARTICULAR CHUNK OF LEVEL 2 WE NEED 25 BITS.

HENCE WE NEED 25BITS,25BITS,24BITS.

SO FINALLY WHATEVER WE HAVE LEARNT IS CORRECT . WE HAVE ALWAYS ASSUMED IN OUR LEARNING THAT PAGE SIZE WILL BE 100% UTILIZED BUT IF GATE WANTS TO USE INEFFIECIENCY THEN IT IS THERE FAULT NOT OUR FAULT.  IN THAT CASE SOLVE LIKE THIS.

Extension of the question: https://gateoverflow.in/255086/self_doubt

The answer to this question in gate key is B . 24,24,24
How did you get that key? GATE never published a key before 2011
Brother then what is the difference between this question and https://gateoverflow.in/379/gate2013-52?
What are you even trying to write? Writing in CAPS LOCK shows that you're shouting, and there's to many spelling mistakes in your answer.
Your answer is more explanatory than arjun sir's. Especially the first half of the frame is chunks.

Diagram for this ans will be

where 1st level there is 1 page table which contains contains 225 entries

2nd level there are 225 page table and each contains 225 entries

3rd level there are 225 page table and each contains 224 entries

by

@srestha,first level page tble contains 2^25 entries cuz there are 2^25 second level page tables??and same for no of entries in each table of second level..and how do you know that there is only 1 table in first level??
and do you mean to say at second level,there re 2^25 tables,each contain 2^25 entries and each entry has 25 bits to address 2^25 entries in a single page table of level 3rd??
@srestha according to ur diagram 1st level page table contains 2^25 entries but according to question it is given that " Bits 30-31 (2 bits) are used to index into the first level page table." i think there will be 2^2 entries in 1st level page table plzz correct if a m wrong....

Actually 2 is no. of page available in 1st level and 225 are number of entries in single page.

@srestha i think  there should be always one page table at 1st level.
ok but when we r calculating page table size on 1st level like (no of page table entries/index * page table entry size )= 2^2 * 4 B.
as in sol given by arjun sir when he is calculating 2nd level page size
Number of entries in a single second level page table× Size of an entry= 2^9×4 B
in ur diagram it is given that no of page tables at 2nd level =2^25 at the same time it shows that each page table on 2nd level entries are (0 to 2^25 -1)
nd thnx for quick rply.

why are we calculating max size of 2nd level page table as 232/211

we can find max size of 2nd level page table as 29*4 also.

pls explain!!

This is wrong. The question clearly says that there are 2 bits reserved for Page Table 1, 9 bits for Page Table 2, and 9 bits for Page table 3.
This means that the number of entries in PT-1 = $4$, PT – 2= $2^9$ and PT-3 = $2^9$

TO ALL THE CONFUSED GUYS LIKE ME I WILL MAKE EVERY THING CLEAR;;

WHATEVER WE HAVE LEARNT IS 100% CORRECT..... SO BE HAPPY   SEE HOW

1-- THIS QUESTION DUE TO THE USE OF JUST ONE WORD IS MAKING EVERYTHING CONFUSING AND WE ARE NOT SEEING THAT WORD.

A processor uses 36 bit physical address and 32 bit virtual addresses, with a page frame size of 44 Kbytes. Each page table entry is of size 44 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 2nd level page table.
• Bits 12−20 are used to index into the 3rd level page table.
• Bits 0−11 are used as offset within the page.

The number of bits required for addressing the next level (SEE THE DIFFERENCE HERE HERE WE REMOVED THE WORD PAGE TABLE) page frame in the page table entry of the first, second and third level page tables are respectively.

SO THIS IS WHAT WE HAVE LEARNT EVERYWHERE . HERE EVERYTHING WILL BE DIVIDED INTO FRAMES WHICH IS SAME IS PAGE SIZE. AND THUS NOW EVEN IN CASE OF MULTILEVEL PAGING IF THE PAGE TABLE OF INNER PAGE TABLES ARE DIVIDED INTO PAGES OR FRAMES (SINCE PAGE SIZE=FRAME SIZE) THEN THEN FOR FINDING THE NEXT LEVEL PAGE FRAME IN THE PTE WE JUST NEED THE NO OF BITS REQUIRED TO REPRESENT FRAMES WHICH IS 24.

BUT THEY HAVE CLEARLY GIVEN

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.

IT CLEARLY MEANS THAT SINCE 3RD LEVEL WILL BE POINTING TO THE ACTUAL FRAMES WHERE THE PAGES OF THE PROCESS ARE PRESENT IN THE MM HENCE THEY COULD BE PRESENT ANYWHERE IN THE MM FRAMES AND WE HAVE 2^24 FRAMES HENCE WE NEED 24 BITS FOR SURE AT 3RD LEVEL PAGE TABLE .

SO  EITHER B OR D COULD BE POSSIBLE

a)    NOW 2ND LEVEL PAGE TABLE WILL BE POINTING TO THE 3RD LEVEL PAGE TABLE NOW SINCE IN THE QUESTION IT IS EXPLICITLY AND DELIBERATELY GIVEN THAT ADRESSING THE NEXT LEVEL PT OR PAGE FRAME HENCE HERE THEY MEAN PAGE TABLE NOT PAGE FRAME.

b)  ACTUALLY HERE IF WE DONT CONSIDER THE BITS DIVISION GIVEN BY THE QUESTION SETTER THEN WE NEED JUST 2 LEVELS OF PAGING UTILIZING VERY EFFICIENTLY BUT SINCE THEY HAVE NOT UTILIZED IT 100% HENCE THATS WHY WE HAVE TO THINK DIFFERENTLY .

c) AT LEVEL 1 WE HAVE 2 BITS IT MEANS WE HAVE 4 ENTRIES HERE SIMPLE. AND HENCE LEVEL 1 SIZE WILL BE 4*SIZE OF EACH ENTRY = 4*4B=16B

AT LEVEL 2 WE HAVE 9 BITS IT MEANS USING PAGE TABLE BASE AND LEVEL 1 IF WE GO TO A PARTICULAR FRAME IN LEVEL 2 THEN HERE ENTRIES PER PAGE/FRAME = 2^9  AND HENCE LEVEL 2  EACH PAGE/FRAME    SIZE WILL BE 2^9 *SIZE OF EACH ENTRY = 2^9*4B=2*11B

SEE WE HAVE PAGE SIZE =2^12 B BUT WE ARE USING JUST 2^11 IT MEANS WE ARE USING JUST THE HALF SIZE OF THE PAGE

AT LEVEL 3 WE HAVE 9 BITS IT MEANS USING PAGE TABLE BASE AND LEVEL 1 AND LEVEL 2 WE WENT TO EXACT FRAME IN LEVEL 3 THEN HERE ENTRIES PER PAGE/FRAME = 2^9.    AND HENCE LEVEL 3 EACH PAGE/FRAME SIZE WILL BE 2^9 *SIZE OF EACH ENTRY = 2^9*4B=2*11B

SEE WE HAVE PAGE SIZE =2^12 B BUT WE ARE USING JUST 2^11 IT MEANS WE ARE USING JUST THE HALF SIZE OF THE PAGE .

THATS WHY WE HAVE TO GO A/T THE QUESTION WHICH CLEARLY MEANS THAT PAGE TABLES ARE NOT DIVIDED INTO PAGES RATHER THEY HAVE BEEN DIVIDED INTO SOME CHUNKS OF SOME OTHER SIZE (NOT PAGE SIZE) SO HERE

DELIBERATELY I WILL USE THE TERM NO OF BITS REQUIRED FOR ADDRESSING NEXT LEVEL PAGE TABLE (NOT PAGE FRAME)  ..

SO NOW A/T LEVEL 2            LEVEL 3 HAS BEEN DIVIDED INTO EACH CHUNK SIZE IS 2*11B (EARLIER WHAT I HAVE MENTIONED AS SIZE OF EACH PAGE/FRAME).

SO FOR LEVEL 2 IT HAS TO LOOK INTO THE MM/ PHYSICAL MEMORY WHERE LEVEL 3  CHUNK WILL BE PRESENT AND THERE ARE CHUNKS OF SIZES 2*11B AT LEVEL 3 .... SO LETS CALCULATE HOW MANY SUCH CHUNKS ARE THERE = SIZE OF PHSICAL MEMORY / SIZE OF EACH CHUNK = 2^36/2^11= 2^25

THUS AT LEVEL 2 TO GO TO A PARTICULAR CHUNK OF LEVEL 3 WE NEED 25 BITS

d)   NOT AT LEVEL 1 WE HAVE TO GO TO A PARTICULAR CHUNK IN LEVEL 2 SO LEVEL 2'S EACH CHUNK SIZE = 2^11B(EARLIER WHAT I HAVE MENTIONED AS SIZE OF EACH PAGE/FRAME).

SO FOR LEVEL 1 IT HAS TO LOOK INTO THE MM/ PHYSICAL MEMORY WHERE LEVEL 2  CHUNK WILL BE PRESENT AND THERE ARE CHUNKS OF SIZES 2*11B AT LEVEL 2 .... SO LETS CALCULATE HOW MANY SUCH CHUNKS ARE THERE = SIZE OF PHSICAL MEMORY / SIZE OF EACH CHUNK = 2^36/2^11= 2^25

THUS AT LEVEL 1 TO GO TO A PARTICULAR CHUNK OF LEVEL 2 WE NEED 25 BITS.

HENCE WE NEED 25BITS,25BITS,24BITS.

SO FINALLY WHATEVER WE HAVE LEARNT IS CORRECT . WE HAVE ALWAYS ASSUMED IN OUR LEARNING THAT PAGE SIZE WILL BE 100% UTILIZED BUT IF GATE WANTS TO USE INEFFIECIENCY THEN IT IS THERE FAULT NOT OUR FAULT.  IN THAT CASE SOLVE LIKE THIS.

1 comment

reshown

This is a simple question, I don't know why people has made it so complicated. The question here they are asking is "The number of bits required for addressing the next level page table(or page frame) in the page table entry"

1st point- Page table entry size will be same in all level of page table & they contain bits required to address all frame because page table or pages of process can be present anywhere in the main memory. in this case 24,24,24

2nd point- According to some people, Question is asking only about where these 3 page table might be present, there is no sense in searching 2nd or 3rd page table directly, think about it why would we do that, access of page table only make sense when we access it from outer level page table to inner level page table and then finally frame no in which process page is present.

Spent a lot of time and effort to understand what is going here.

According to the concept we have learnt, we would have divided the process into pages as follows [Assuming page tables are page aligned]:

VA = 32 bits, PA= 36 bits, Page Size= 2^12 B

No. of pages in the process = Process Size/Page size= 2^32/2^12 = 2^20

Therefore, page table size(PTS1) = 2^20 * 2^2 = 2^22 Bytes > 2^12 Bytes (Page Size). So we need to divide this page table again into pages and create page table for level 2.

No. of pages in PTS1= Size of PTS1/Page Size = 2^22/2^12 = 2^10.

So, page table size(PTS2)= 2^10 * 2^2= 2^12 Bytes = Page Size. Therefore two level of paging would have done the job for us.

Dividing the virtual Address space as follows:

In this case the number of bits required to address each level would be same i.e equal to number of bits to address each frame because page tables occupy entire frame in main memory. 24-bits in each case.

But, in the question they have made it inefficiently using three level page tables. Also, they are not considering the page table size equal to Page Size. Additionally different level page tables may have different sizes unless explicitly told in the question. This is the main cause of confusion how the number of page tables at a level are decided by main memory size (as discussed by Arjun Sir).

According to question they have divided the virtual address space as follows:

Also note that they are asking for "The number of bits required for addressing the next level page table(or page frame)".

So, third level page tables will be pointing to actual page frames. So, number of bits required to address page frames depend on the number of frames available in physical memory.

No. of frames= MM size/ Page size = 2^36 / 2^12 = 2^24. There 24-bits will be required by 3rd level page table.

2nd level page tables will be pointing to 3rd level page tables. So, the number of bits required to address depends on number of page tables present in 3rd level. Considering worst case, All the main memory frames could have been occupied.

No. of page tables present @ 3rd level = (Size of MM) / (Size of each Page table @ level 3) = (2^36) / (No. of entries * Size of entry)

= (2^36) / ( 2^9 * 2^2) = (2^36) / ( 2^11) = 2^25. Therefore, 25-bits will be required by 2nd level page table.

1st level page tables will be pointing to 2nd level page tables. So, the number of bits required to address depends on number of page tables present in 2nd level. Considering worst case, All the main memory frames could have been occupied.

No. of page tables present @ 2nd level = (Size of MM) / (Size of each Page table @ level 3) = (2^36) / (No. of entries * Size of entry)

= (2^36) / ( 2^9 * 2^2) = (2^36) / ( 2^11) = 2^25. Therefore, 25-bits will be required by 1st level page table.

So, answer would be (D). <25,25,24>

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?

@Arjun Sir @Praveen Saini Sir plz have a look ! Thank you!

I am doing the same way u mentioned,why is it not correct?

Kindly explain this comment what is wrong in it , please explain it because in http://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html problem 1 question 2  same thing is used please please explain all genius  minds of world  please help

The question given is wrong,

The question should be 36 bits in the virtual address and 32 bits in the Physical address and if this was the condition then option  B (24,24,24 )is right.

WHY THIS QUESTION IS WRONG???

if you do according to the right procedure you will find that the way they have allocated the bits in the Logical address for page table indexing is wrong :

Allow me to clarify it:

let us say 1st level means outermost page table. and 3rd  level means innermost page table.

and we know that page size= frame size = 4kb= 12 bits in page offset or frame offset  field

Since virtual  address space is 32 bits then

no of pages= (2 ^ 32 ) / page size  = (2 ^ 32) / 4 kB = (2 ^ 20) = 2 M

for the innermost level or says at 3rd level: page table size =

(2^ 20 ) * 4 BYTE =   4 MB which is greater than page size and it can't fit in one frame so we have to again do paging. // 4 B is page table entry size they have given it.

for the second level

No of page table entry  = 4 MB / 4 KB = 1 K pages and size of the page table for the second level is 1k *4B= 4 KB which is equal to page size, it means now we don't need any other LEVEL. Two level paging is enough for this question

to allocate bits, divide the virtual  memory as

Total bits = 32

for innermost we need 10 bits because it is completely filed and for outermost page table we need 10 bits and for page offset, we need 12 bits.

1.NEVER divide physical address into pages, it can be divided only in two field  Frame no  and frame offset

2.Don't attempt any wrong question in gate they are going to give marks to everyone who is not attempted.

by

why will 2^20 be 2M, isnt it 1M
Sorry for mistyping.

yes, it is 1M.