GATE CSE 2003 | Question: 26

Question

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 

• A. the large amount of internal fragmentation
• B. the large amount of external fragmentation
• C. the large memory overhead in maintaining page tables
• D. the large computation overhead in the translation process

Comments

https://gateoverflow.in/916/gate2003_26#viewbutton

---

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{<Not in any frame>}$

 

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. 

VA - virtual address

PA -  physical address

---

When a process is divided into fix sized pages, there is generally some leftover space in the last page(internal fragmentation). When there are many processes, each of their last page's unused area could add up to be greater than or equal to size of one page. Now even if you have to total free size of one page or more but you cannot load a new page because a page has to be continuous. External fragmentation has happened. So, I don't think external fragmentation is completely zero in paging.

https://stackoverflow.com/questions/32744662/how-is-there-internal-fragmentation-in-paging-and-no-external-fragmentation

Answer 1

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

Comments

"Internal fragmentation exists only in the last level of paging" Can you elaborate this one?

Assume 7kb heap and 7kb text section of a process and it is given 8kb page size. I don't think heap and text will share a page (7+1) due to different permissions. Instead they will be in separate pages causing 1kb internal fragmentation in both pages.

---

"Internal fragmentation exists only in the last level of paging"

But here its only1 level, so internal frag is possible?

And how do we know that 4M is too big for this system?

---

@julkar9


Source: Galvin

Answer 2

Ans is c Large memory overhead would there.To reduce it  use multi level paging will be used.

Answer 3

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 .

Comments

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

Answer 4

The correct answer is C. the large memory overhead in maintaining page tables.

---

 

Let's break down the math to see why the memory overhead is the critical problem.

 

1. Deconstruct the Virtual Address

 

A virtual address is split into two parts: a page number (which acts as an index into the page table) and an offset (which tells us where the data is within that page).

• Virtual Address Size: 32 bits

• Page Size: 1 KB = $2^{10}$ bytes

To find the number of bits needed for the offset, we take the log base 2 of the page size:

• Offset Bits: $\log_2(2^{10}) = 10$ bits

The remaining bits are used for the page number:

• Page Number Bits: 32 (total bits) - 10 (offset bits) = 22 bits

 

2. Calculate the Number of Page Table Entries

 

The number of page table entries is determined by the number of possible virtual pages a process can have. This is $2$ raised to the power of the page number bits.

• Number of Entries: $2^{22} = 4,194,304$ entries

This means that for every single process, the operating system would need to create a page table with over 4 million entries.

 

3. Calculate the Total Page Table Size

 

Each entry in the page table (Page Table Entry or PTE) needs to store the physical frame number and some control bits. A typical PTE size is 4 bytes.

• Size of one PTE: 4 bytes

• Total Page Table Size per Process: Number of Entries × Size of one PTE

  • $2^{22}$ entries × 4 bytes/entry = $4,194,304 \times 4$ bytes = $16,777,216$ bytes

  • 16 MB

 

Conclusion

 

A single-level page table would require the system to allocate 16 MB of contiguous physical memory for every single process. Even if a program is tiny (like a simple "Hello, World!"), it would still need this massive 16 MB table. This is an enormous and impractical memory overhead, which is why multi-level paging was invented to solve this exact problem.

Answer 5

option A)

Comments

how internal fragmentation happens here?

---

Sorry ... option C is correct..

Answer 6

Option a is right but option c should als be right as huge no of pages will make managing page tables an overhead.