I have read that paging does not suffer from external fragmentation as the frames and the pages are all of the equal sizes, but when we store a last level page table in a frame at that time it may not fully occupy the frame. Similarly, if n such page tables are stored, that does not occupy the frames entirely, then there can be a case where all the gaps exceed a page size. Then there should be external fragmentation, right? So why is it said that paging does not have external fragmentation?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ There seems to be some context missing. This makes it difficult to help you. $\endgroup$– ratchet freakJun 13, 2019 at 15:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The details depend on the processor architecture, but the principle is the same everywhere. All page tables of a given type at a given level have the same size. When all memory blocks have the same size, there is no fragmentation: a memory block is allocated starts at an offset which is a multiple of the block size, so the size of any hole is a multiple of the block size. If a gap opens in the page table, the operating system can use this gap the next time it needs to allocate a page table.
Furthermore the size of a page table pretty much always divides the size of a page — both are powers of two. So a page contains a whole number of page tables with no leftover space. This means that the operating system can allocate pages for page tables and no table spreads over multiple pages, so there's no need for the page tables to be consecutive and therefore there's no fragmentation of the address space for the page tables themselves.
answered Jun 14, 2019 at 5:58
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
43.3k7 gold badges117 silver badges182 bronze badges
$\begingroup$
$\endgroup$
The collection of internal fragmentation do not contribute to external fragmentation. External fragmentation is contributed by the empty space which is EXTERNAL to partition(or page). So suppose if there are only two frames in main memory ,say of size 16B, each occupied by only 1B data. The internal fragmentation in each frame is 15B. The total unused space is 30B. Now if you want to load one new page of some process, you will see that you do not have any frame available. You are unable to load a new page eventhough you have 30B unused space. Will you call this as external fragmentation? Answer is no. Because these 15B unused space are INTERNAL to the pages. So in paging, internal fragmentation is possible but not external fragmentation.
