GATE CSE 2021 Set 1 | Question: 11

Question

In the context of operating systems, which of the following statements is/are correct with respect to paging?

• A. Paging helps solve the issue of external fragmentation
• B. Page size has no impact on internal fragmentation
• C. Paging incurs memory overheads
• D. Multi-level paging is necessary to support pages of different sizes

Comments

External Fragmentation can be resolved by two techniques-

     → Compaction and Non-Contagious Memory Partition (Paging).

So Paging solves External Fragmentation. But it suffers from Internal Fragmentation (as it follows fixed partition mechanism).

Paging consumes memory for storing the page-tables, so memory overhead.

Multi-level paging is done to reduce the innerpage table size.

 

So answer is (A) and (C).

 

Answer 1

Pages are divided into fixed size slots , so no external fragmentation

But applications smaller than page size cause internal fragmentation

Page tables take extra pages in memory. Therefore incur extra cost

Correct ans A and C

Comments

Do we have different page sizes in x86 machines?

---

https://stackoverflow.com/a/60348716 

From the above ref,

Is it possible (and used in any known relevant OS) that one process does have multiple page frame sizes?

Yes, It's relatively common for 64-bit 80x86 where there's 4 KiB pages, 2 MiB (or 4 MiB) "large pages" (plus maybe 1 GiB "huge pages"); and done to reduce the chance of TLB misses (while also reducing memory consumed by page tables). Note that this is mostly an artifact of having multiple levels of page tables - an entry in a higher level table can say "this entry is a large page" or it can say "this entry is a lower level page table that might contain smaller pages". Note that in this case it's not "multiple page sizes in the same table", but is "fixed page size for each level".

---

Page size is for the system, not the program. If segment 1 is divided into 2KB pages, then segment 2 will also be divided into 2 KB pages, otherwise we won't be able to implement the paging concept properly, because the frame size will be same for all pages.

Answer 2

• A. Pages are of fixed size and hence causes no external fragmentation. So, option A is TRUE.
• B. When the required amount of memory for a process is not an exact multiple of page size, internal fragmentation happens. So, option B is FALSE.
• C. Paging requires all the pagetables in use to be in main memory which causes memory overhead. So, option C is TRUE.
• D. This is slightly debatable. Typically a system allows only pages of a fixed size but $\textsf{x86}$ allows Huge pages or even $\textsf{Transparent Huge Pages}$ of size even $1\;\text{GB}$ (typically $2\;\text{MB})$ which can drastically increase the $\text{TLB}$ hit rate for processes needing large amount of memory. And this usage of multiple size of pages is typically handled using multi-level paging. Since there is no strict requirement of multiple levels of page tables to support multiple page sizes (though its not theoretically required I do not know of any such system) this option is FALSE due to the presence of “necessary”

Correct Answer: A;C.

Comments

Sir ,

For option b if I say pages of muliple sizes can be a possible solution to avoid internal fragmentation to some extent then would it be true ??

Answer 3

• Paging is the technique of non contiguous allocation of physical memory which solves external fragmentation.
• Paging may cause internal fragmentation depends on the page size and process size in last page, if page size is larger and process size is smaller.
• Implementation of Paging requires management of Page tables which resides in pages and hence consume additional memory.
• Multilevel paging is required when size of page table exceeds the size of page. Since page table reside in page, it is further divided to pages of same size. 

With these reasoning $A$ and $C$ is correct