Subject: Operating System

Topic: Memory Management

Difficulty: Hard

Fragmentation:

Fragmentation is a phenomenon in which storage space is used inefficiently, reducing capacity or performance and often both.

The exact consequences of fragmentation depend on the specific system of storage allocation in use and the particular form of fragmentation.

In many cases, fragmentation leads to storage space being "wasted", and in that case the term also refers to the wasted space itself. For other systems (e.g. the FAT file system) the space used to store given data (e.g. files) is the same regardless of the degree of fragmentation (from none to extreme).

Whenever a process is loaded or removed from the physical memory block, it creates a small hole in memory space which is called fragment. Due to fragmentation, the system fails in allocating the contiguous memory space to a process even though it have the requested amount of memory but, in a non-contiguous manner.

The fragmentation is further classified into two categories Internal and External Fragmentation.

Internal fragmentation: Internal fragmentation is the wasted space within each allocated block because of rounding up from the actual requested allocation to the allocation granularity.

External fragmentation: External fragmentation is the various free spaced holes that are generated in either your memory or disk space.

Both the internal and external classification affects data accessing speed of the system. They have a basic difference between them i.e. Internal fragmentation occurs when fixed sized memory blocks are allocated to the process without concerning about the size of the process, and External fragmentation occurs when the processes are allocated memory dynamically.

Internal Fragmentation

Internal fragmentation occurs when the memory is divided into fixed sized blocks. Whenever a process request for the memory, the fixed sized block is allocated to the process. In case the memory assigned to the process is somewhat larger than the memory requested, then the difference between assigned and requested memory is the Internal fragmentation.

This leftover space inside the fixed sized block can not be allocated to any process as it would not be sufficient to satisfy the request of memory by the process. Let us understand Internal fragmentation with the help of an example. The memory space is partitioned into the fixed-sized blocks of 18,464 bytes. Let us say a process request for 18,460 bytes and partitioned fixed-sized block of 18,464 bytes is allocated to the process. The result is 4 bytes of 18,464 bytes remained empty which is the internal fragmentation.

The overhead of keeping track of the internals hole created due to internal fragmentation is substantially more than the number of internal holes. The problem of internal fragmentation can be solved by partitioning the memory into the variable sized block and assign the best-sized block to a process requesting for the memory. Still, it will not totally eliminate the problem of internal fragmentation but will reduce it to some extent.

External Fragmentation

External fragmentation occurs when there is a sufficient amount of space in the memory to satisfy the memory request of a process. But the process’s memory request can not be satisfied as the memory available is in a non-contiguous manner. Either you apply first-fit or best-fit memory allocation strategy it will cause external fragmentation.

When a process is loaded and removed from the memory the free space creates the hole in the memory space, and there are many such holes in the memory space, this is called External fragmentation. Although the first fit and best fit can affect the amount of external fragmentation, it can not be totally eliminated. Compaction may be the solution for external fragmentation.

Compaction algorithm shuffles all memory contents to one side and frees one large block of memory. But compaction algorithm is expensive. There is an alternative solution to solve external fragmentation issue which will allow a process to acquire physical memory in a non-contiguous manner. The techniques to achieve this solution are paging and segmentation.