Fragmentation

• Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation.
• External fragmentation exists when there is enough total memory space to satisfy a request, but the available spaces are not contiguous; storage is fragmented into a large number of small holes.
• Depending on the total amount of memory storage and the average process size, external fragmentation may be a minor or a major problem.
• Statistical analysis of first fit, for instance, reveals that, even with some optimization, given $N$ allocated blocks, another $0.5N$ blocks will be lost to fragmentation.
• That is, one-third of memory may be unusable! This property is known as the 50-percent rule.
• Memory fragmentation can be internal as well as external.
  • Consider a multiple-partition allocation scheme with a hole of 18,464 bytes.
  • Suppose that the next process requests 18,462 bytes.
  • If we allocate exactly the requested block, we are left with a hole of 2 bytes.
  • The difference between these two numbers is internal fragmentation; memory that is internal to a partition but is not being used.
• The general approach to avoiding this problem is to break the physical memory into fixed-sized blocks and allocate memory in units based on block size.
• One solution to the problem of external fragmentation is compaction. The goal is to shuffle the memory contents so as to place all free memory together in one large block.
• The simplest compaction algorithm is to move all processes toward one end of memory; all holes move in the other direction, producing one large hole of available memory. This scheme can be expensive.
• Another possible solution to the external-fragmentation problem is to permit the logical address space of the processes to be non-contiguous, thus allowing a process to be allocated physical memory wherever the latter is available.
• Two complementary techniques achieve this solution:
  • paging
  • segmentation
• These techniques can also be combined.