GATE CSE 2008 | Question: 67

Question

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

• A. $\text{20,20,20}$
• B. $\text{24,24,24}$
• C. $\text{24,24,20}$
• D. $\text{25,25,24}$

Comments

Few more explanations:

https://web.archive.org/web/20140805205005/https://www.gatementor.com/viewtopic.php?f=251&t=4863

https://stackoverflow.com/questions/21702389/number-of-page-table-index-bits-in-multilevel-paging

---

The main point to note here is $For\ each\ level\,\  page\ size/frame\ size\ depends\ on\ the\ size\ of\ page\ used\ in\ the\ next\ level\\.$

$Page\ size\ in\ multilevel\ paging\ may\ change,\ it\ need\ not\ be\ same\ in\ every\ level.$

If you understand this point you’ll able to answer the question.

---

This is like the 6th time I have come back to this question because I hadn't been able to understand the solution well enough and it has been an unscratchable itch for weeks but this time I think I have succeeded in getting to the gist of the concept. I think the most important observation to be drawn here is that the page tables will not be page aligned this is why you need more bits to address page tables than the page frames themselves(because they are larger 2¹²B > 2¹¹B). I hope this is the last time I'm here. Goodluck everyone.

Answer 1

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. 

So, answer is (D). 

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

Comments

@Arjun @Sachin Mittal 1

in the provided questions of CS372 in 3^rd question 2^nd part it is saying that 2^nd level and 1^st level page table will address to whole physical memory hence at least the bits per entry will be same as bits of physical memory . i am not able to understand this?

BUT

as per the explanation bits per entry of any level depends on what it is pointing to , i mean as inner most level is pointing to pages or frames so MM is divided into pages and hence the bits per entry of innermost is calculated.

similarly for ith level entry (bits) is decided on how i+1 ^th level single page table is dividing MM into chunks.

---

@mayajeet Sharing whatever I understood, in case it helps –

That is because in the CS372 question, we are being provided with the process’ physical memory requirement itself (in the above PYQ, we were provided with just the MM size, in which case we calculate for the worst case scenario - refer towards the end of Arjun sir’s video linked in the best answer), and we found out that only a single 3^rd level page table suffices for all the pages of the process. Now, this 3^rd level page table can actually be placed anywhere on the physical memory (had we not known beforehand how many 3^rd level page tables are required, then we need to divide the MM into chunks of 3^rd level page table size for maximum physical memory usage). Moreover, the answer of the CS372 question further explains how aiming for a low sized chunk division of the MM is not feasible (PTE size grows larger than 4B), and how increasing the size of this chunk saves us no more space than just storing a regular pointer in the PTEs of the first and second level page tables, and just using the regular memory allocator.

---

can you please provide the links for the set of VM videos again?

Answer 2

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.

 

Comments

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

Answer 3

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  .
 

Comments

So, does that mean the page tables are not present in frames?

---

"Page tables in frames" means?

---

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

Here, in problem 2:

In solution, point number 2 should be: With 4-byte entries in the page table we can reference 2^34 pages. Since each page is 2^13 B long, the maximum addressable physical memory size is 2^34 * 2^13 = 2^47 B (assuming no protection bits are used). 

REASON: 2^36/ 2^2 = 2^34, please correct me if I am wrong.

Answer 4

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.  

IF QUESTION WOULD HAD BEEN 

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.

HENCE ANSWER WOULD HAD BEEN 24,24,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.

 

 

 

 

  

 

 

 

Comments

Your answer is more explanatory than arjun sir's. Especially the first half of the frame is chunks.

---

Amazing Explanation Sir!

---

brilliant