How will you find out internal fragmentation? How will you avoid it?

  • 0

    Fragmentation needs to be considered with memory allocation techniques. Paging is basically not a memory allocation technique, but rather a means of providing virtual address spaces.

    Considering the comparison with segmentation, what you're probably about is the difference between an memory allocation technique using fixed size blocks (like the pages of paging, assuming 4KB page size here) and a technique using variable size blocks (like the segments used for segmentation).

    Now, assume that you directly use the page allocation interface to implement memory management, that is you have two functions for dealing with memory:

    alloc_page, which allocates a single page and returns a pointer to the beginning of the newly available address space, and
    free_page, which frees a single, allocated page.
    Now suppose all of your currently available virtual memory is used, but you need to store 1 additional byte. You call alloc_page and get a 4KB block of memory. You only use 1 byte of that huge block, but also the other 4095 bytes are, from the perspective of the allocator, used. If this happens multiple times eventually all pages will be allocated, so further calls to alloc_page will fail. Even if you just need another additional byte (which could be one of the 4095 that got wasted above) the allocator will tell you that you're out of memory. This is internal fragmentation.

    If, on the other hand, you would use variable sized blocks (like in segmentation), then you're vulnerable to external fragmentation: Suppose you manage 6 bytes of memory (F means "free"):

    You first allocate 3 bytes for a, then 1 for b and finally 2 bytes for c:

    Now you free both a and c, leaving only b allocated:

    You now have 5 bytes of unused memory, but if you try to allocate a block of 4 bytes (which is less than the available memory) the allocation will fail due to the unfavorable placement of the memory for b. This is external fragmentation.

    Now, if you extend your page allocator to be able to allocate multiple pages and add alloc_multiple_pages, you have to deal with both internal and external fragmentation.

  • 0

    When the total size of all program allocations is less than the total memory and yet the OS complains of no free memory, you have internal frag.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.