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

 

MISTAKE 2: Choosing 20 Bits based on 32 bit VAS

---

 

 

---

why we subtract offset of particular level of page table with physical address is because 

each page table is stored in the main memory So, to address that page table we require 

(physical address bits - offset of that particular level of page table) which take us to that particular page table .

---

A 2-KB page table occupies half of a 4-KB page frame, so 24 bits identify the physical 4-KB frame and 1 more bit identifies which half contains the 2-KB page table. Hence 25 bits.

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

Key Concept to understand here-

As we know, the different level page tables are also stored in the main memory itself so, whenever you decide to divide any level of page table into equal chunks, you must divide the Main Memory into those equal chunks so that the levels can fit into the main memory.

another way of putting it-

whenever you decide to divide something (like a process or a page table) into equal chunks,
you must divide the main memory (MM) into chunks of the same size,
so that those chunks can fit inside memory properly.

So we are using the physical address here.

Also remember-

physically, MM is divided into frames.
Logically, while calculating page table address bits, we also view MM as divided into larger chunks.

Hope it helps!  :)

---

Sir, the set of videos you shared are no longer accessible..

---

• A more intuitive approach to this would be realizing that the PDEs at level 1 and level 2 point to PFNs containing the Page Tables of the next level. Since there are $2^{24}$ frames possible we would need 24 bits to address a page/frame.
   
• We fit two 2kb page tables within a single 4kb frame in this problem, so using a 24 bit PFN would still point to a frame and we would be unable to address the other page tables within a single frame.
   
• So, finally we would need 24 bits to first locate the frame, and then we would need an additional bit to select one of the two 2kb page tables that reside within a single 4kb frame. Hence 25 bits would be needed

 

This can be generalized as:
 

If $\text{Page Table Size} < \text{Page Size}$ allows $P$ page tables to completely fit into one physical frame, then we require $\log_2(P)$ additional bits apart from the PFN bits to index and select the correct page table within that specific frame

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

---

No need of making that possible worst case as in question it is given that 9 bits for each entry address, i.e. 12 to 20 bits

Answer 3

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

Thank you so much bro, for helping me out otherwise i would've gotten a headache trying to understand this answer from formulas.

---

@habedo007 Bro I'm hear for solution for my understanding to be better not for checking someone's spelling mistakes who's obviously intelligent enough to help me understand the concept behind the question.

---

Beautifully explained!!!

Sharing just the picture view of whatever explained here, 

Answer 4

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 5

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>

 

Comments

Beautifully summarized Gaurav! :)

---

This is likely the most suited explaination for me

 

Answer 6

Diagram for this ans will be

where 1st level there is 1 page table which contains contains 2²⁵ entries

2nd level there are 2²⁵ page table and each contains 2²⁵ entries

3rd level there are 2²⁵ page table and each contains 2²⁴ entries

Comments

@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 2³²/2¹¹

we can find max size of 2nd level page table as 2⁹*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$