External Fragmentation

External Fragmentation in Operating Systems

External fragmentation refers to the condition where free memory space is split into small, non-contiguous blocks due to the allocation and deallocation of memory over time. These small free spaces scattered throughout the memory are not large enough to accommodate new processes or requests, even though there may be enough total free memory.

This type of fragmentation arises when memory is allocated and deallocated dynamically, causing free memory to be fragmented into small blocks of unused space, which makes it difficult to use the available memory efficiently.

1. Cause of External Fragmentation

External fragmentation happens primarily in systems that allocate memory in variable-sized blocks. When a process is allocated memory and later deallocated, the memory that was used by that process becomes free. However, since memory allocation and deallocation may occur in different locations and sizes, this results in small gaps or "fragments" of free memory between allocated regions.

For example:

• A system may allocate memory for processes A, B, and C, which leaves some unused memory in between these processes.
• If processes A and B are later terminated and their memory is deallocated, the free space between them is left fragmented. Even though there might be enough total free memory, the fragments may not be large enough to accommodate new processes or large allocations.

2. How External Fragmentation Occurs

Consider a memory system with the following scenario:

• Process 1 is allocated 200 KB.
• Process 2 is allocated 300 KB.
• Process 3 is allocated 400 KB.

At some point, Process 1 terminates and its allocated memory is freed. Now the memory space might look like this:

| 200 KB (Free) | 300 KB (Allocated) | 400 KB (Allocated) |

Then, if Process 4 requires a 150 KB block, it cannot be placed in the free 200 KB space, as there are small gaps in between allocated memory. This is where external fragmentation causes a problem.

3. Impact of External Fragmentation

• Wasted Memory: Even though the total free memory is large enough to accommodate new processes, it is scattered in small chunks that are too small to satisfy the memory requirements of any new process.
• Inefficient Memory Utilization: The system becomes inefficient because the available memory cannot be used for new allocations, even though total free space may seem sufficient.
• Increased Overhead: External fragmentation requires the operating system to perform additional tasks like defragmentation or compaction (discussed later) to optimize memory usage.

4. Example of External Fragmentation

Let’s look at a visual example of memory allocation and deallocation:

| Allocation | Allocation | Allocation | Free Space | Allocation | Free Space | Free Space |
| 200 KB     | 300 KB     | 400 KB     | 100 KB     | 250 KB     | 50 KB      | 100 KB     |

Here, there is a total of 1000 KB of memory. However, free memory is fragmented into several smaller blocks, such as:

• 100 KB between allocations of 200 KB and 300 KB.
• 50 KB between 400 KB and the 250 KB block.
• A final block of 100 KB at the end.

If a new process requires 500 KB, the system can’t allocate it despite having 1000 KB of free space because the largest contiguous free block available is only 250 KB, which is not enough.

5. How to Combat External Fragmentation

There are several techniques used by operating systems to manage and reduce external fragmentation:

a) Compaction

Compaction is the process of rearranging the contents of memory to combine the free blocks of memory into larger contiguous blocks. By shifting the processes together and moving them to adjacent areas, the free space is consolidated into one large block. However, this process can be time-consuming and resource-intensive, as it requires copying data from one part of memory to another.

Example: After compaction, the memory might look like this:

| Allocation | Allocation | Allocation | Allocation | 
| 200 KB     | 300 KB     | 400 KB     | 500 KB     | 

Now the memory is contiguous and no smaller fragmented blocks are left.

b) Paging

In systems that use paging (one of the memory management techniques), external fragmentation is virtually eliminated. In paging, memory is divided into fixed-size blocks (pages), and each process is divided into pages of the same size. These pages can be scattered throughout physical memory, but they don’t have to be contiguous. The operating system uses a page table to map the virtual address space of a process to physical memory addresses, preventing fragmentation issues that arise in contiguous allocation schemes.

• Advantage: In paging, external fragmentation is eliminated because any free page in memory can be allocated to a process, no matter where it is located.

c) Segmentation

Segmentation divides memory into variable-sized segments based on logical units of a program (e.g., code, data, stack). While segmentation can still suffer from fragmentation, it allows better management of different parts of a process. It can be combined with paging to reduce fragmentation further.

d) Buddy System Allocation

The buddy system is a memory allocation scheme that divides memory into blocks of sizes that are powers of two (e.g., 64 KB, 128 KB, 256 KB). When a memory request is made, the system tries to find the smallest block that can accommodate the request. If no block large enough is available, the system splits a larger block into two "buddies" (two smaller blocks of equal size), ensuring that blocks can be easily merged back when they are freed.

Advantage: This system reduces fragmentation by ensuring memory blocks are of a standard size, making it easier to find a suitable block for allocation.

e) Use of Large Fixed-Size Blocks

Allocating large contiguous blocks for each program or process can reduce fragmentation. However, this method might lead to internal fragmentation (where a block is larger than the actual memory needed), so it is typically used in combination with other methods.

6. Internal vs External Fragmentation

• Internal Fragmentation: Occurs when fixed-size blocks of memory are allocated, and the allocated memory block is larger than the required memory. This leads to unused space within a block (e.g., if a 1 MB block is allocated to a process that only needs 900 KB, the remaining 100 KB is wasted).
• External Fragmentation: Happens when free memory is scattered in small chunks, making it impossible to allocate a contiguous block of memory large enough to satisfy a new request.

7. External Fragmentation vs Paging

• External Fragmentation: Typically occurs in systems that use contiguous allocation or segmentation, where memory is allocated in variable-sized blocks. As programs are loaded and unloaded, memory becomes fragmented.
• Paging: Paging eliminates external fragmentation because memory is allocated in fixed-size pages that do not need to be contiguous. This leads to more efficient use of memory, even in the presence of large numbers of programs running simultaneously.

8. Conclusion

External fragmentation is a common problem in memory management, particularly in systems that use contiguous allocation or segmentation schemes. It results in inefficient use of memory, as free space is scattered into small chunks that cannot be used to fulfill memory requests.

To combat this, techniques like compaction, paging, and segmentation can be employed to reduce or eliminate fragmentation. In modern systems, paging is the most effective method for handling memory allocation, as it entirely eliminates external fragmentation. However, for systems that still rely on contiguous memory allocation, compaction and buddy systems can help reduce the impact of external fragmentation.