The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

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
asked in Operating System by Veteran (59.5k points)
edited by | 2.3k views

6 Answers

+25 votes
Best answer
  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.
answered by (291 points)
edited by
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?

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 ?
+6 votes
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 .
answered by Boss (15.7k points)

@Tendua internal fragmentation is always there in paging


Not always but might be sometimes , that too in the last page of the process(if process size is not multiple of page size) .
+5 votes
Ans is c Large memory overhead would there.To reduce it  use multi level paging will be used.
answered by Boss (31.4k points)
–4 votes
option A)
answered by Active (2.6k points)
how internal fragmentation happens here?
Sorry ... option C is correct..
–4 votes
Option a is right but option c should als be right as huge no of pages will make managing page tables an overhead.
answered by Active (3.3k points)
–5 votes
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.
answered by Active (1.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,000 questions
45,496 answers
48,632 users