Why are we considering physical address space here??

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+83 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

- $\text{20,20,20}$
- $\text{24,24,24}$
- $\text{24,24,20}$
- $\text{25,25,24}$

+4

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

Why are we considering physical address space here??

+3

@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?

+5

Only on a uniprocessor system. For multi processor system, different processes can map to different memory spaces (page tables being different).

0

@Sir Arjun,Shared Memory in Distributed Environment.Isn't it?All d more architecture varies from processor to processor.:)

+1

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.

+110 votes

Best answer

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

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

0

@Arjun sir

Correct me if I'm wrong, this is what I understood from your solution to this question:

First level page table has 2 bits, so it can point to 4 second level page tables, and each of its entry is of 25 bits.

Second level page tables has 9 bits, so each second level page table can point to 512 third level page tables, and each of its entry is of 25 bits too.

Third level page tables has 9 bits to it, so each third level page table can point to 512 main memory frames, and each of its entry is of 24 bits.

Correct me if I'm wrong, this is what I understood from your solution to this question:

First level page table has 2 bits, so it can point to 4 second level page tables, and each of its entry is of 25 bits.

Second level page tables has 9 bits, so each second level page table can point to 512 third level page tables, and each of its entry is of 25 bits too.

Third level page tables has 9 bits to it, so each third level page table can point to 512 main memory frames, and each of its entry is of 24 bits.

0

@Arjun Sir

I am getting doubt with meaning of these line in answer

firstly "

"`A page in logical address space corresponds to a page frame in physical address space.`

shouldnot this line be "A page size in logical address space corresponds to a page frame size in physical address space."

because the offset part of logical address and physical address is same, but number of frame and number of pages of both addresses are not same

Plz elaborate this line

Secondly " `there is only 1 first level page table. But there can be many second level and third level page tables "`

how to know first level that means at end level there shouldnot be more than 1 page table?

0

can you explain me,

generally we divide physical address,

but here virtual address space is already divided into page tables.

and i tried to understand answer given by @Arjun sir, in his answer

he is dividing whole physical address space by size of Nth level page table, this means only Nth page tables are ftaking whole space of Physical address space, what about N+1, N+2 level page tables, where they will fit if Nth level page table is taking the whole space.

Actually im not get this concept. xplain it ??

generally we divide physical address,

but here virtual address space is already divided into page tables.

and i tried to understand answer given by @Arjun sir, in his answer

he is dividing whole physical address space by size of Nth level page table, this means only Nth page tables are ftaking whole space of Physical address space, what about N+1, N+2 level page tables, where they will fit if Nth level page table is taking the whole space.

Actually im not get this concept. xplain it ??

0

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

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

+1

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

+22 votes

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, t**he 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,

A

0

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 .

Virtual Address is 32 bits.

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.

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

Virtual Address is 32 bits.

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.

0

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.

0

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

0

frame no bit remain same for all level page table .because at all level, page table entry is same ...

0

sir ,page table entry size is same for all level . and PTE contain frame bit . so it also remain same.

+1

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

+2

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

- Page table page can be of the same size as page frame
- 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.

0

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 .

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 .

+3

You can solve these questions- very good ones.

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

0

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

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

+7 votes

Diagram for this ans will be

where 1st level there is 1 page table which contains contains 2^{25} entries

2nd level there are 2^{25} page table and each contains 2^{25} entries

3rd level there are 2^{25} page table and each contains 2^{24} entries

0

@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??

0

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

0

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

+1

0

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

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.

0 votes

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!

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 21
- Job Queries 61
- Projects 13

39,645 questions

46,730 answers

140,391 comments

58,091 users