edited by
75,662 views
276 votes
276 votes

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}$
edited by

14 Answers

10 votes
10 votes

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

edited by
3 votes
3 votes

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>

 

2 votes
2 votes

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.

 

 

 

2 votes
2 votes

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.

Answer:

Related questions

51 votes
51 votes
7 answers
1
29 votes
29 votes
3 answers
2
Kathleen asked Sep 12, 2014
16,895 views
A process executes the following codefor(i=0; i<n; i++) fork();The total number of child processes created is$n$$2^n-1$$2^n$$2^{n+1} - 1$
23 votes
23 votes
4 answers
4