10,338 views

In a system with $\text{32 bit}$ virtual addresses and $\text{1 KB}$ page size, use of one-level page tables for virtual to physical address translation is not practical because of

1. the large amount of internal fragmentation
2. the large amount of external fragmentation
3. the large memory overhead in maintaining page tables
4. the large computation overhead in the translation process

If we consider a byte addressable system, we'll get $\frac{2^{32}B}{2^{10}B}=2^{22}= 4 \ million$ entries for pages of a single process.

If we choose a modest number, and say our process has $100$ pages, then the entries for pages $101$ to $4000000$ would look like this:

 $\text{Page i}$ $\text{}$

This means most of the entries in our page table are useless.

Even for a process that only needs just one page in totality, 4 million entires would have to be made and maintained. This is a monstrous overhead.

i think that option D also should be true beside of option C because if we use one level page table then that page table have 2^22 entries and for finding required PTE for given VA, we have to compare first 22 bits of VA with index bits of each page table entry (that is of size 22 bits) in sequential manner. So, translation of VA to PA should be difficult.

Subscribe to GO Classes for GATE CSE 2022

1. Internal fragmentation exists only in the last level of paging.
2. There is no External fragmentation in the paging.
3. $\frac{2^{32}}{2^{10}} = 2^{22} =4M$ entries in the page table which is very large. (Answer)
4. Not much relevant.

Computers these days have 4GB to 8GB os RAM, and just 4MB of page table per process does not sound too intensive interms of memory ...
lenear search to large single level pt i, e multiple frame also affect system performance and is overhead. so why not d?

https://gateoverflow.in/1320/gate2009-34

it says that it reduces the size of page table. Can u explain how do multi-level paging helps to reduce the size of page table and maintenance of the page table overhead in the light of this question?

Watch these videos from Video 1 to  Video 37. You will not only get what you asked, your many other doubts will be cleared also.

These all together are only 1-hour length, And worth watching 2 times :)

After this u can do this question also.

If you have time, Dont stop at 37 video, continue and watch all Cache videos then questions of different types of caches like "virtually indexed physically tagged cache" can be done smoothly :)

And if possible see my comment on one Gate question :)

nice video .... thank you
Hi Sachin, I'm good in single level page table address translation but not clear in TLB-tag bits, different associative caches, page fault inside TLB etc. Does watching above videos would solve my doubt?
In single level paging, during address translation, there is linear search from 0 to (2^22)-1, so why not option D?
How can we say internal fragmentation problem exists in the last level paging ???

Page table entry size or even framenumber size is not given ... right ? then how are you saying there is internal fragmentation problem ?
If internal fragmentation present in last level then there will definitely external fragmentation. are i correct or not?
actually it can't be possible to accomodate page table of 4mb of entries  of pages  in a size of 1 kb frame size of main memory ,that's why multi level paging is introduced so that page table can be accomodate in a single frame

moreover,4mb of entries cause overlap of frames over each other,so it is overhead
i think the answer is c . The option is definitely going to rule out by the point that we do paging to reduce or totally remove internal fragmentation. that why we keep page size =frame size . here we even dont care how much big the page is . we are very sure that its going to fit in one frame . can anybody just explain how and where internal fragmentation is there .

now the option c.we do multilevel paging because we always want to get the whole page table in one page . and that why we do multilevel paging till that level while we get the whole page table in one page . here the memory size not given so we may not even now whether we need multilevel or not . still seeing that the number of page is high answer c is the best shot .
by

@Tendua internal fragmentation is always there in paging

@suvasish

Not always but might be sometimes , that too in the last page of the process(if process size is not multiple of page size) .
Ans is c Large memory overhead would there.To reduce it  use multi level paging will be used.
option A)

how internal fragmentation happens here?
Sorry ... option C is correct..
Option a is right but option c should als be right as huge no of pages will make managing page tables an overhead.
by
Here Number of pages will be 2^32/2^10= 2^20

Hence, Number of pages is much in number,thus chances to internal fragementation due to size of pages is larger,then overhead is reduced.

So answer will be option A.
by