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?

| cite | improve this question | | | | |
  • $\begingroup$ no one for help? $\endgroup$ – CS_GUY Jun 13 '19 at 14:05
  • $\begingroup$ There seems to be some context missing. This makes it difficult to help you. $\endgroup$ – ratchet freak Jun 13 '19 at 15:32

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.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.