What is Fragmentation? Types of Fragmentation

Fragmentation is the problem that arises in contiguous allocation. In fragmentation, memory splits into many small pieces and some part of this piece remains unused and memory is not able to be used effectively.

Scope 

This article explains fragmentation in detail.

Definition

Suppose, a process is loaded into memory partition 1. The maximum size of partition 1 is 1Mb or 1024kb and the size of process P1 is 450kb.

After allocation of process P1 at partition 1, the wasted space can be calculated as 1024 – 450 = 574 kb space wasted. This wasted memory space is called internal fragmentation. 

If the size of the process is less than the memory partition, then there is internal fragmentation. 

If the size of the process is greater than the memory partition, then there is an external fragmentation. For example, if the size of the partition memory is 1 Mb i.e 1024 kb, and the size of the process is 1500 kb, then we can’t allocate this process to the memory location. For this condition, all the memory spaces are wasted which is external fragmentation. 

Both best fit and first fit strategies for memory allocation suffer from external fragmentation. As processes are loaded and removed from memory, the free memory space is broken into little pieces. 

External fragmentation exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous as storage is fragmented into a large number of small holes. 

If all these small pieces of memory were in one big free block instead, we might be able to run several processes.

External fragmentation may be a minor or major problem, depending on the total amount of memory storage and the average process size. Statistical analysis of the first fit states that given N allocated blocks, another 0.5N blocks will be lost to fragmentation i.e. one third of the memory may be unusable. This property is known as the 50 percent rule. 

To avoid this problem we use an approach in which we break the physical memory into fixed-sized blocks and allocate memory in units based on block size. In this approach, the memory allocated to a process may be slightly larger than the requested memory. 

Compaction is used as the solution to external fragmentation. In compaction, all the memory contents are shuffled so as to place all free memory together in one large block. Compaction is possible only if relocation is dynamic and is done at execution time. In the simplest compaction algorithm, we move all the processes toward one end of the memory and all the holes in the other direction producing one large hole of available memory.

Summary

Fragmentation is the wastage or loss of memory because we are not able to use the memory or allocate it effectively. It is of two types: external fragmentation and internal fragmentation.

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article