Why are we considering physical address space here??

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+4

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

+6

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.

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

All the page tables are stored in main memory which has fixed size of frames in paging architecture. When you refer to any of the page table (whether it is third level ,second level or first level) you search for it somewhere in main memory frames. And number of frames in memory decide the number of bits required to address a particular frame which is same for all the main memory frames.

My question is that when all the page tables are stored in some memory frame WHY DO WE NEED 25 BITS TO ADDRESS SOME FRAME INSTEAD OF 24 BITS ??

How can we use, at the same time, different number of bits to address different level page table DESPITE THE FACT THAT ALL OF THEM RESIDE IN ONE OR THE OTHER FRAME IN MAIN MEMORY ??

Please answer. Its completely absurd to even imagine an architecture that use different number of bits OR (more precisely) different size and number of frames for the same memory at same time !!

Thank You

My question is that when all the page tables are stored in some memory frame WHY DO WE NEED 25 BITS TO ADDRESS SOME FRAME INSTEAD OF 24 BITS ??

How can we use, at the same time, different number of bits to address different level page table DESPITE THE FACT THAT ALL OF THEM RESIDE IN ONE OR THE OTHER FRAME IN MAIN MEMORY ??

Please answer. Its completely absurd to even imagine an architecture that use different number of bits OR (more precisely) different size and number of frames for the same memory at same time !!

Thank You

+1

"All the page tables are stored in main memory which has fixed size of frames in paging architecture. When you refer to any of the page table (whether it is third level ,second level or first level) you search for it somewhere in main memory frames. And number of frames in memory decide the number of bits required to address a particular frame which is same for all the main memory frames."

Where are these sentences given?

It is possible to even use pages of different sizes in a system. i.e., we can change the number of OFFSET bits and correspondingly change the page size. All we need for this is the MMU (or sometimes OS) to handle the different offset sizes which is not a difficult task.

So, in the given question, a main memory page frame is fetched with 24 bits of address and 12 offset bits, while the page frame corresponding to a third level page will be fetched using 25 bits of address and 11 offset bits (9 bits from VA + 2 bits for 4 bytes of PTE).

+1

Sir, what does that mean "number of third level page tables possible"? we have only one page table at each level for a process ryt? (I mean if multilevel paging is implemented)

+1

"Yes a memory page can be of different size based on page offset and that will vary the number of pages that can fit in memory accordingly."

But at the same time "Is it possible for main memory to keep DIFFERENT PAGE SIZES". I mean as in this question we need different page size for third and 2nd PT , So can the memory maintain both pages in memory AT THE SAME TIME ??

My doubt is that "How can memory slots be divided such that some page is of 1KB(say) and other is of 2KB at the same time " !!!

And yes you have answered that "page frame of main memory(actual page containing instructions) is fetched using 24 bits while a third level PT (containing frame numbers for actual page residing in main memory) is 25 bits." Assume that both the actual page and third level PT reside in MM at the same time how are we going to address both ??

I need 25 bits to address PT but if I use 25 bits "I MAY END UP USING SOME PORTION OF THE PAGE OFFSET OF ACTUAL PAGE IN MM AS IT IS LARGER IN SIZE THAN PT AND HENCE 1 BIT OF IT ,MSB(13 th BIT) WILL BE USED For referring a page despite it contained data !!"

If you say this does not happen this way, how would I refer PT as well as actual page at the same time.

Please explain this in particular.

Thanks for your valuable time and help .

But at the same time "Is it possible for main memory to keep DIFFERENT PAGE SIZES". I mean as in this question we need different page size for third and 2nd PT , So can the memory maintain both pages in memory AT THE SAME TIME ??

My doubt is that "How can memory slots be divided such that some page is of 1KB(say) and other is of 2KB at the same time " !!!

And yes you have answered that "page frame of main memory(actual page containing instructions) is fetched using 24 bits while a third level PT (containing frame numbers for actual page residing in main memory) is 25 bits." Assume that both the actual page and third level PT reside in MM at the same time how are we going to address both ??

I need 25 bits to address PT but if I use 25 bits "I MAY END UP USING SOME PORTION OF THE PAGE OFFSET OF ACTUAL PAGE IN MM AS IT IS LARGER IN SIZE THAN PT AND HENCE 1 BIT OF IT ,MSB(13 th BIT) WILL BE USED For referring a page despite it contained data !!"

If you say this does not happen this way, how would I refer PT as well as actual page at the same time.

Please explain this in particular.

Thanks for your valuable time and help .

0

@Gate Keeda: what I think is virtual memory page size is fixed according to fame size in main memory. Since 24 bits are needed to address fame in main memory, we ,AT EACH LEVEL need 24 bits in the PTE to address each frame(And please clear I am NOT saying that page table entry will be of 24 bits, I am saying in each entry of any page table we use 24 bits to refer a frame in MM because after all we are referring a frame out of 2^24 frames).

Now coming to the bits used for indexing. If just 9 bits are used for indexing why would that alter the page size ?? Page size must remain fixed rather we can assume that to make a fixed page size we can increase the PTE size in the page table.(NOTE that still 24 bits will be used to refer a frame but remaining bits that this PTE uses in excess can be used for other purposes or may be not used for anything).

In reference to above question bit 21-29 are used to index second level PT (which is frankly saying a SINGLE PAGE as you said above). Now to make this equal to one page so that it fits in memory frame we must use PTE of size equal to 4KB/2^9=8 Bytes. But this does not mean that we need at, this level 25 bits to address next level PT.We still need 24 bits to refer next level PT but I have used a larger entry size which may contain extra information,no matter what , and this excess information may change at each level of PTs causing different PTE size BUT SAME NUMBER OF FRAME BITS.

This is easy to assume ,that from a page table entry (even if it is of varying size at different levels, we can always pick first 24 bits to address frame/PT (which is stored in frame actually) at the next level).

Respond to this @Gate Keeda

Now coming to the bits used for indexing. If just 9 bits are used for indexing why would that alter the page size ?? Page size must remain fixed rather we can assume that to make a fixed page size we can increase the PTE size in the page table.(NOTE that still 24 bits will be used to refer a frame but remaining bits that this PTE uses in excess can be used for other purposes or may be not used for anything).

In reference to above question bit 21-29 are used to index second level PT (which is frankly saying a SINGLE PAGE as you said above). Now to make this equal to one page so that it fits in memory frame we must use PTE of size equal to 4KB/2^9=8 Bytes. But this does not mean that we need at, this level 25 bits to address next level PT.We still need 24 bits to refer next level PT but I have used a larger entry size which may contain extra information,no matter what , and this excess information may change at each level of PTs causing different PTE size BUT SAME NUMBER OF FRAME BITS.

This is easy to assume ,that from a page table entry (even if it is of varying size at different levels, we can always pick first 24 bits to address frame/PT (which is stored in frame actually) at the next level).

Respond to this @Gate Keeda

+1

@Gate-Keeda No. There can be multiple inner level page tables. And that is why multi-level paging is used. Of the numerous possible inner level page tables, only the needed ones will be loaded to main memory.

0

@Gatekeeda: I dint say there is only one table. I said when we talk of indexing of a page table we talk about just one page out of many pages at that level.because only one of them will be used for a particular page reference at a time.

0

@Sandeep Supporting multi-size pages is not an uncommon thing even for actual page frames (see below link). So, using a different page size for a page table is even simpler. All that is needed is for the MMU to know which page size is needed for the current request and correspondingly fetch that much data from memory.

0

there will be multiple inner level page tables. Agree. that's what makes it multilevel paging. But my doubt is.. The logical address is generated for a particular process at a time.. So the number of page tables will be fixed for that particular process...i.e. there is only one page table at third level So, how come we have 2^{25} number of third level page tables??

0

No. There can be multiple third level page tables for a process. Usually 2 or 3. 2^{25} is the maximum such tables possible.

+2

Wonderful question for clearing all misconceptions and doubts in Multilevel Paging. And brilliantly answered by Arjun Suresh. In many books answer is given as option (b).

0

@Arjun Suresh: Sir I solved the questions given in the link. But following are few doubts :-

1. What is meant by **page-aligned** in the Problem 3 part 2 solution ?

2. In Problem 3 part 3 solution it is given " First, the stack, data and code segments are at addresses that require having 3 page table entries active in the first level page table, so we have 3 second-level page tables."

Now the question is just by looking at three different addresses like given for data, code and stack segment in the question, can we say we have 3 entries in 1st-level Page Table. Or is there something related to grouping of addresses like base address and offset i.e data and code segment come under same group of addresses and stack in other group of addresses so we can say we have two entries. Hope u understood what i want to say?

0

@arjun sir,here i am not understanding one thing,why are we calculating number of tables in each level and why are we considering physical address space for that and even if number of tables are to be calculated then number of entries in first level page table is 2^2 i.e 4,number of tables in second level should be 4 because each entry of first level will point to a page table in next level,hence number of tables at second level should be 4 with 2^9 entries in each table as 9 bits are there in virtual address space to refer to the second level.then number of tables in third level should be 2^11 similarly with 9 bits in each entry of third level page table.

i am very confused..please have a look at it.

i am very confused..please have a look at it.

0

"So, in the given question, a main memory page frame is fetched with 24 bits of address and 12 offset bits, while the page frame corresponding to a third level page will be fetched using 25 bits of address and 11 offset bits (9 bits from VA + 2 bits for 4 bytes of PTE)."

So is my following conclusion correct(and consequently the understanding of the concept)?

1) There are 2^25 3rd level page tables.

2)There are still 2^9 entries in each 3rd level page table,but each page entry has 4 bytes,so offset(the size) becomes 2^11, and 4 bytes is 32 bits, we are using only 24 bits out of 32 for addressing page frames?

3)There are 2^25 2nd level page tables,There are still 2^9 entries in each 2nd level page table, PTE size is 4 bytes, so 32 bits are present but we are using only 25 bits out of 32 bits to address the 3rd level page tables(because we found out that there are 2^25 3rd level page tables)?

4)There are (2^36/((2^2)*(2^2)))= 2^32 1st level page table,each table has only 4 entries, but each page table entry contains 25 bits to address 2nd level page table?

5) So in layman terms, before we were going from left to right to calculate and splitting up the page tables for virtual address calculation, now we are doing up the reverse, for accommodating the page framesthe no of page tables do not remain the same at various levels,only thing remaining constant is the no of entries of page tables at each level and the PTE size, so we can calculate the offset bit for calculating the no of page tables possible?

So is my following conclusion correct(and consequently the understanding of the concept)?

1) There are 2^25 3rd level page tables.

2)There are still 2^9 entries in each 3rd level page table,but each page entry has 4 bytes,so offset(the size) becomes 2^11, and 4 bytes is 32 bits, we are using only 24 bits out of 32 for addressing page frames?

3)There are 2^25 2nd level page tables,There are still 2^9 entries in each 2nd level page table, PTE size is 4 bytes, so 32 bits are present but we are using only 25 bits out of 32 bits to address the 3rd level page tables(because we found out that there are 2^25 3rd level page tables)?

4)There are (2^36/((2^2)*(2^2)))= 2^32 1st level page table,each table has only 4 entries, but each page table entry contains 25 bits to address 2nd level page table?

5) So in layman terms, before we were going from left to right to calculate and splitting up the page tables for virtual address calculation, now we are doing up the reverse, for accommodating the page framesthe no of page tables do not remain the same at various levels,only thing remaining constant is the no of entries of page tables at each level and the PTE size, so we can calculate the offset bit for calculating the no of page tables possible?

+1

@arjun sir, After reading the solution all my enitre concept in Paging is thrashed :(

I didn't understand many things .

**Question1**

First of all , What is the question really asked ?

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

Does this mean.. *In 1st 2nd and 3rd page table entries how many bits are used as frame number ?*

Question 2

I didnt understand this equation .

Number of third level page tables possible= $\frac{Physical memory size }{Size of a third level page table}$

How it is possible to get # 3rd LEVEL page tables by Dividing entire physical memory with Size of 3rd level page table . Doesn;t the physical memory include both 1 , 2 , 3 level page tables and pages .

**Question3**

According to What I knew , Number of entries in outer page table is the number of inner page tables .

In light to this we must calculate from outer most page table to inner for finding number of page talbes BUt you provide a topic turvic solutions to my conceptual understanding. I didn't get this part . Why did u calculate it like that .

Moreover do the last level contains many page tables ? What I knew is the page number from last page table will gives the fram number to get a PAGE not another PAGETABLE

But you provided a equation like that *" Number of third level page tables poosible* "

Could u pls help me ? Im getting totally confused !!

0

Question 1: yes. But "frame number" are used for page frames (not for page tables) and hence they did not use the word. See this part

next level page table(or page frame)

Question 2: Yes, here we are going for an upper bound (the leasr possible upper bound).

Question 3:

Number of entries in outer page table is the number of inner page tables

This is true only for 1 level paging or for the first page table. Since there is only one page table, each second level page table (or page frame) requires a distinct entry in first level page table. So, in the given question we have 2 entries in first level page table and hence there must be just 2 second level page tables possible. But I wrote $2^{25}$ which is meant to denote the no. of possible addresses of second level page tables (this needs change). Had the second level page tables been at fixed location - possible in a uniprocessor system - we would have needed just 2 bits for addressing the second level page tables here.

Moreover do the last level contains many page tables ? What I knew is the page number from last page table will gives the fram number to get a PAGE not another PAGETABLE

But you provided a equation like that" Number of third level page tables poosible

The question is for 3 level paging. So, there are many page tables in 3rd level. From the third level page table, we get a page number which points to a page. I guess you got confused with the level here.

0

This is wondrfully explained . Thank you so much @arjun sir :)

Just one more point to get clarified ,

Number of third level page tables possible= $\frac{Physical memory size}{Size of a third level pagetable}$

I didn't understand why are u using this equations beause physical memory will contain all pages tables not just the entries of 3rd level .

Just one more point to get clarified ,

Number of third level page tables possible= $\frac{Physical memory size}{Size of a third level pagetable}$

I didn't understand why are u using this equations beause physical memory will contain all pages tables not just the entries of 3rd level .

+1

@Arjun sir:

Isn't it that each inner level page table is itself paged and the frame no of each of these inner pages is stored in outer page table?

So do you mean "number of pages of 3rd level page table" by "number of third level page tables possible" ?

Isn't it that each inner level page table is itself paged and the frame no of each of these inner pages is stored in outer page table?

So do you mean "number of pages of 3rd level page table" by "number of third level page tables possible" ?

+2

@pC yes, that will be more accurate. But more complex to calculate and here we are doing an upper bound only.

@Pratyush Yes, we are doing paging of page tables- but by standard notation it is not correct to refer to them as "pages" as they are page tables.

@Pratyush Yes, we are doing paging of page tables- but by standard notation it is not correct to refer to them as "pages" as they are page tables.

0

@Arjun Sir,

In third level we have 2^9 enteries and we need to point to 2^24 frames of main memory,so we should have 2^24/2^9 page tables for thirs levels?Why are we takng entire RAM ,we need to how many frames are there and not the entire address space.please help

In third level we have 2^9 enteries and we need to point to 2^24 frames of main memory,so we should have 2^24/2^9 page tables for thirs levels?Why are we takng entire RAM ,we need to how many frames are there and not the entire address space.please help

+2

@Arjun Sir

A BIG thanks to you for the explanation.

"we should not assume that page tables are page aligned." This line added a special charm to the solution.

Once Again, Amazingly explanaied. Cleared many myths that all coaching teach.

A BIG thanks to you for the explanation.

"we should not assume that page tables are page aligned." This line added a special charm to the solution.

Once Again, Amazingly explanaied. Cleared many myths that all coaching teach.

+17

@pc, why you think that is not correct ?

You must have missed something from that explanation.

I am trying to explain the crux, See if this makes sense to you-

Key Point: We can divide anything (process, any level page Table) to any size, and accordingly we have to divide MM.

When we divide Process to some size, then that size is called page/frame, we divide MM into frames.

When we divide page table to some size ($2^k$), then that size has no special name (like above frame). we also divide MM into size of $2^k$.

2 |
9 |
9 |
12 |

Outermost page table need to address one of the 2nd level page table, Question is how many bits it will take?

Before answering this a simple questions:

you have $2^{36}$ bytes of memory, you need to address one byte, how many bits you need?

- 36 bits (Because there are $2^{36}$ Bytes)

you have $2^{36}$ bytes of memory, you need to address one 2KB block, how many bits you need?

- 25 bits (because there will be such $\frac{2^{36}}{2^{11}}= 2^{25}$ blocks. )

This says: if you want to address some block or chunk, then number of bits depends on, howmany such blocks are there.

If we organize (divide) MM into size of each block, then howmany such blocks will be there.

Each 2nd level page table size = $2^9 \times 2^2 = 2^{11}$

Now , Outermost page table wants to address one of the 2nd level page table.

If we partition MM into each of size $2^{11}$ then there will be $\frac{2^{36}}{2^{11}}= 2^{25}$ partitions.

And 2^{nd} level page table can fit into one of such partition.

Therefore Outermost page table wants 25 bits to address 2nd level page table.

Important thing to notice here is MM is divided into chuncks of $2^{11}$ wrt page table, and at the same time MM is divided into frames (of size $2^{12}$).

Now say if address split is this:

3 |
8 |
9 |
12 |

outermost page table size = $2^3 \times 2^2 = 2^5$

2nd level page table size = $2^8 \times 2^2 = 2^{10}$

innermost level page table size = $2^9 \times 2^2 = 2^{11}$

Now wrt to :

1.outermost page table:

MM is divide into chunks of $ 2^5$, therefore to address outermost pagetable we need ( $\frac{2^{36}}{2^5}= 2^{31}$ ) 31 bits in Page Table Base Register.

2. 2nd level page table:

MM is divide into chunks of $ 2^{10}$, therefore to address 2nd level page table we need ( $\frac{2^{36}}{2^{10}}= 2^{26}$ ) 26 bits in outermost page table entry.

3. innermost level page table:

MM is divide into chunks of $ 2^{11}$, therefore to address innermost pagetable we need ( $\frac{2^{36}}{2^{11}}= 2^{25}$ ) 25 bits in 2^{nd} levelpage table entry.

4.Process:

MM is divide into chunks of $ 2^{12}$, therefore to address actual page we need ( $\frac{2^{36}}{2^{12}}= 2^{24}$ ) 24 bits in inner most levelpage table entry.

+9

Pleasure :)

Continuing last comment-

It's Just a view of memory that everyone has-

- Cache thinks that MM is divided into lines.

- Process thinks that MM is divided into Frames.

- Secondary memory thinks that MM is divided into Blocks.

- Page tables thinks that MM is divided into chunks of size $2^k$, here $2^k$ is size in which we divide Page table itself.(Again saying, Page tables need not to be page aligned, we can divide page tables into any size and accordingly we divide MM into same size so that each partition of Page Table can go and fit into one of the partition of MM. Again, That partition size could be anything, need not to be same as page size. Actually that partition size has nothing to do with page size.)

Now one may wonder that if we can divide PT into any size, then why to divide at all this is same as saying "Why to have multi level paging?"

Answer of this question is in this video

Here it is beautifully explained the need of multilevel paging and how this helps to reduce page table size. See this question here, this is an example of how using multi level paging we can drastically decrease page table size.

I recommend all set of videos of VM.

Once you done with all videos (total length is 1 hour) then these kinds of questions will make more sense to you - GATE-09 Question.

0

Can someone please explain why we are doing Physical memory size$ /$Size of a third level page table to calcualte number of third level page tables?

Shouldn't the page table contain the entries which are indexed based on virtual address and mapped to physical address? And so shouldn't it be Virtual memory size $/$Size of a third level page table ?

Shouldn't the page table contain the entries which are indexed based on virtual address and mapped to physical address? And so shouldn't it be Virtual memory size $/$Size of a third level page table ?

0

No. See page tables are also stored in "physical memory". Hence we are finding the no. of possible addresses for it. Virtual memory is directly relevant only for first level page table.

0

If I understand it correctly, we are using the virtual address as follow

bit 30-31 - to find the entry in first level page table which points to second level page table.

Next 9 bits are used to find the entry in second level page table, which points to third level page table.

Next 9 bits are used to find the entry in third level pable table, which points to actual physical page.

And last 12 bits are used as offset in this physical page.

So in total the number of entries in third level page table that will be pointing to physical pages is $2^{2}*2^{9}*2^{9}=2^{20}$ . Each of these third page table entries is 4 byte i.e. 32 bits, so in total $2^{20}*2^{5}=2^{25}$ , therefore third level page table will need 25 bits.

Where do you think I am going wrong?

bit 30-31 - to find the entry in first level page table which points to second level page table.

Next 9 bits are used to find the entry in second level page table, which points to third level page table.

Next 9 bits are used to find the entry in third level pable table, which points to actual physical page.

And last 12 bits are used as offset in this physical page.

So in total the number of entries in third level page table that will be pointing to physical pages is $2^{2}*2^{9}*2^{9}=2^{20}$ . Each of these third page table entries is 4 byte i.e. 32 bits, so in total $2^{20}*2^{5}=2^{25}$ , therefore third level page table will need 25 bits.

Where do you think I am going wrong?

0

@Arjun I see what you are saying now. Thanks! I guess this problem is difficult only because of the text.

+1

@sachin..please check these

- The pointer (p) stored in an entry of the outer (1st) level page table will point to an inner (next 2nd) level page table starting address.
- If inner level page tables are stored in a page/frame aligned organization then p needs to index the possible frames in MM, So, p size = frame no size.
- If inner level page tables are NOT stored in a page/frame aligned organization.
- Assuming inner page tables are stored in MM in a contiguous manner in size of one such 2nd level page table.
- Then p size = $\begin{align*} \log_2 \left ( \frac{\text{MM size}}{\text{one 2nd level PT size}} \right ) \end{align*}$

- In this NON-page/frame aligned organization, the bits required to search (or locate) one-page table in MM depends upon the size of that page table itself. And these bits may be stored in different places (base register, page entry etc) depending which page table we are looking for.

If any of above lines is incorrect, then please mention that. Moreover,

Could you please provide some links or source that indicate then NON-page/frame alignment of PT storage or possible real implementation. Because I have searched a few that says, page-alignment structure only.

(note that if you have such source already, then ok ! other wise no need to search too much)

+1

To me ur every point seems to be fine.

U can solve questions here- http://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html

U can solve questions here- http://www.cs.utexas.edu/~lorenzo/corsi/cs372/06F/hw/3sol.html

0

Sir,

Only one thing to ask these 24, 25 and 25 bits are part of page Table entry size (Here 4B = 32 bits). Right??

And pte include other aadditional info. like valid bit etc..But never uses the number of bits to adress next level page table beyond the page table entry size. Right?

Only one thing to ask these 24, 25 and 25 bits are part of page Table entry size (Here 4B = 32 bits). Right??

And pte include other aadditional info. like valid bit etc..But never uses the number of bits to adress next level page table beyond the page table entry size. Right?

0

@Debashish @Sachin

https://gateoverflow.in/61310/question-related-to-gate-2008_67-complex-question

in 3 or 4 level page table if only 1st level contains offset of the page, why other level not contains the offset?

if the 2nd and 3rd level page table size $2^{25}$ bytes and number of PTE only $2^{9}$ and page table entry size is $2^{2}$ Bytes , then is $\left (2 ^{25}-2^{9} \times2^{2}\right )$ could be used or it totally wasted?

0

@Sonam

Acc. to Sachin's solution

if

outermost page table size = $2^3 \times 2^2 = 2^5$

2nd level page table size = $2^8 \times 2^2 = 2^{10}$

innermost level page table size = $2^9 \times 2^2 = 2^{11}$

then size of physical memory will be 5+10+11+12=38

But in given question physical memory size is 36 B

Isnot it?

Acc. to Sachin's solution

if

outermost page table size = $2^3 \times 2^2 = 2^5$

2nd level page table size = $2^8 \times 2^2 = 2^{10}$

innermost level page table size = $2^9 \times 2^2 = 2^{11}$

then size of physical memory will be 5+10+11+12=38

But in given question physical memory size is 36 B

Isnot it?

0

i think ,you misinterpreted , he gave another example

"Now say if address split is this:" i think

@sachin ek bar dekh

"Now say if address split is this:" i think

@sachin ek bar dekh

0

I am not sure If I got above conversation.

Just making one point that I have taken separate example to clarify more.

Just making one point that I have taken separate example to clarify more.

0

@Sachin

https://gateoverflow.in/61310/question-related-to-gate-2008_67-complex-question

chk my command here

+1

Thanks, @arjun sir for the great answer!

Thanks, @sachin for giving such a great explanation. I actually understood this concept after seeing your explanation. It would be great if you could add it as an answer.

Thank God! I saw this question on this site before completing virtual memory concept. Actually, still many teachers are teaching it the wrong way. Also, Tanenbaum hasn't covered this part in detail which sends everyone in believing that like the innermost table, every other level page table considers page size as the only distribution of memory.

Thanks, @sachin for giving such a great explanation. I actually understood this concept after seeing your explanation. It would be great if you could add it as an answer.

Thank God! I saw this question on this site before completing virtual memory concept. Actually, still many teachers are teaching it the wrong way. Also, Tanenbaum hasn't covered this part in detail which sends everyone in believing that like the innermost table, every other level page table considers page size as the only distribution of memory.

0

One more thing I need to know @Arjun Sir

In ur ans u told

" number of possible third level page tables u have to calculate from bits from 12-20 index number"

for " number of possible second level page tables u have to calculate bits from 21 to 29 index number"

then for 1st level page tables why u not calculated from index number 30-31?

I mean why it direct taken from number of bits in page frame?

In ur ans u told

" number of possible third level page tables u have to calculate from bits from 12-20 index number"

for " number of possible second level page tables u have to calculate bits from 21 to 29 index number"

then for 1st level page tables why u not calculated from index number 30-31?

I mean why it direct taken from number of bits in page frame?

0

sir , i would like to ask one thing suppose if u r asked size of frame required to store process then u will devide frames as size of 2^36/2^12 =2^24 , but to store page table frame size should be 2^36/2^11=2^25 , as we know that main mem will be devided in equal frame then which size we will prefer ?

if u will devide frame with 2^25 then then to store 2^24 will leads lots of internal fragmentation

if u will devide frame with 2^25 then then to store 2^24 will leads lots of internal fragmentation

+1

@Arjun sir

// only third level page table entry points to data frames//

now, total page tables at third level = **2 ^{25} **

each third level page tables contain entries = **2 ^{9}**

each entry corresponds to **4KB(2 ^{12} bytes)** data frame.

**according to this total virtual address = 2 ^{25}*2^{9}*2^{12}= 2^{46} bytes, or 46 bits virtual address, but in qsn virtual address is limited to 32 bits.**

so how could this be possible?

+1

@saket Who told tht main memory can only be divided equally between pag frames and page tables? Who divides it?

@Joshi As told in the answer, there is no requirement that a given process addresses all available physical memory space. But a physical address must be large enough so that every possible address can be used (by some process).

@Joshi As told in the answer, there is no requirement that a given process addresses all available physical memory space. But a physical address must be large enough so that every possible address can be used (by some process).

0

at third level no. of page table would be...2^{11}**.**

Virtual address space is...2 9 9 12 ..now here...

1st level:- 1 page table, 2^{2 }entry and each entry cotains single...next level page table..

2nd level:- 2^{2} page table and each containing containg 2^{9 }entry.. .and each entry having next level page table:

3rd level:- 2^{2 }* 2^{9 }page table and each having 2^{9 }entry...at third level total no. of entry would be 2^{20}.which is equal to the no. of pages in the process(i.e 2^{32-12})...i.e virtual memory devided by page size...

0

yes at third level we can have at max 2^{25} tables but out of these how many will be actually used depends on the memory requirements of a process.

0

@sachine ....i thinnk paging is applied on process so we need to split logical address then why dividing physical address??

clear the doubt

clear the doubt

0

@Arjun sir,

If at level $i$ we have $2^x$ page tables,then at level $i-1$ we will have $2^x$ entries and each entry will have $x$ bits in its PTE to address next level page table.(Although PTE can have other information also along with $x$ bits)

Please verify

If at level $i$ we have $2^x$ page tables,then at level $i-1$ we will have $2^x$ entries and each entry will have $x$ bits in its PTE to address next level page table.(Although PTE can have other information also along with $x$ bits)

Please verify

0

I have a little doubt over calculation as physical address is given in bits (36 bits) and frame size is given in Bytes (4KBytes) . the calculation done is 36-12 = 24 ,so how you took 12 here ? because it should be 2^{15} rather 2^{12} .I'm sorry but I'm not getting this calculation .please clarify ,thank you!

0

We address a byte and sometimes multiple bytes which is termed a word. There is usually no "bit addressing".

0

Obviously I'm getting that its byte addressing but my question is specifically about calculations done ,to be more specific I don't get how can bit and byte both involved in single calculation without interchanging one to other .How can byte be subtracted from bits ,wouldn't it lead to wrong calculation ? going at binary level we need bits . few bits becomes bytes and few of those bytes becomes a frame or block or whatever but the ground level is bits only ,isn't ? I see it as you have set of bits for addressing like MM or VM ,in power of 2 for calculative simplicity and then we divide it in index offset etc etc and then address translation through mapping it further where we set few bits (a collection in terms of byte or word) to define frame and it goes like that ,right ? but the binary ground is bit only. I hope you I'm capable of explaining my confusion ..please clarify .thank you!

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

+2

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

+3

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!

0 votes

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,861 questions

47,532 answers

145,982 comments

62,293 users