1. Introduction

Even when sufficient memory is available in the system, a process may still fail to obtain memory. This happens because the available memory is scattered into several small free blocks rather than existing as one continuous block.

This problem is known as External Fragmentation.

External fragmentation is one of the most significant drawbacks of contiguous memory allocation and was a major motivation behind the development of paging and virtual memory systems.

2. What is External Fragmentation?

External Fragmentation occurs when free memory exists in the system but is divided into multiple non-contiguous blocks, making it impossible to satisfy a request for a large contiguous memory region.

Key Idea

Total Free Memory ≥ Required Memory

But

No Single Contiguous Free Block Exists

Therefore:

Allocation Fails

The memory is available, but it is fragmented across different locations.

3. Example of External Fragmentation

Suppose memory contains the following free blocks:

50 KB
30 KB
20 KB

Total Free Memory:

50 + 30 + 20 = 100 KB

A new process requires:

80 KB

Although:

100 KB > 80 KB

Allocation fails because:

Largest Free Block = 50 KB

No single contiguous block can hold the process.

4. Visualization of External Fragmentation

Consider memory arranged as:

+-----------+
| Process A |
+-----------+
| 50 KB Free|
+-----------+
| Process B |
+-----------+
| 30 KB Free|
+-----------+
| Process C |
+-----------+
| 20 KB Free|
+-----------+

A process requiring 80 KB cannot be allocated despite 100 KB of total free memory.

5. Where Does External Fragmentation Occur?

5.1 Variable Partition Allocation

Memory partitions are created dynamically according to process requirements.

When processes terminate, holes of different sizes are left behind.

These holes gradually fragment memory.

5.2 Contiguous Allocation Systems

Any system requiring processes to occupy a continuous memory block is vulnerable to external fragmentation.

Examples include:

• Variable partition allocation

• Dynamic contiguous memory allocation

• Early operating systems

6. Why External Fragmentation Occurs

External fragmentation develops naturally over time because of repeated memory allocation and deallocation.

Step-by-Step Example

Initial State

+--------------------+
|      Free          |
+--------------------+

Allocate Processes

+----P1----+----P2----+----P3----+

P2 Terminates

+----P1----+ Free +----P3----+

New Allocations and Deallocations

Over time:

+--P1--+ Free +--P4--+ Free +--P3--+

Many small holes appear.

These holes collectively waste memory.

Key Insight

External fragmentation is caused by scattered free memory, not by insufficient memory.

7. Characteristics of External Fragmentation

• Occurs outside allocated memory blocks

• Free memory exists but is unusable

• Common in contiguous allocation systems

• Increases over time

• Reduces effective memory utilization

• Difficult to manage efficiently

8. Mathematical Perspective

A useful way to think about external fragmentation is:

Usable Memory ≠ Total Free Memory

Example

Free Blocks:

40 KB
35 KB
25 KB

Total Free Memory:

100 KB

Largest Block:

40 KB

New Process Requires:

60 KB

Allocation Fails.

Even though:

100 KB > 60 KB

No contiguous block is large enough.

9. Impact on System Performance

9.1 Allocation Failures

Processes may fail to load despite available memory.

9.2 Poor Memory Utilization

Memory remains free but unusable.

9.3 Reduced Multiprogramming

Fewer processes can reside in memory.

9.4 Increased Management Overhead

The operating system spends more effort searching for suitable memory blocks.

9.5 Performance Degradation

System efficiency gradually decreases as fragmentation grows.

10. Solution 1: Compaction

What is Compaction?

Compaction is the process of relocating processes so that scattered free spaces are merged into one large contiguous block.

Before Compaction

P1 | Free | P2 | Free | P3 | Free

After Compaction

P1 | P2 | P3 | Free Free Free

All free space is combined into one large block.

Working Steps

Step 1

Move processes toward one side of memory.

Step 2

Remove gaps between processes.

Step 3

Merge free spaces.

Step 4

Create one large free block.

Advantages

• Eliminates external fragmentation

• Improves memory utilization

• Increases allocation success rate

Disadvantages

• Expensive operation

• Requires relocation support

• CPU intensive

• Not suitable for frequent use

11. Solution 2: Paging (Most Important)

Paging completely removes the requirement that a process occupy contiguous memory.

Core Idea

Memory is divided into:

• Pages (logical memory)

• Frames (physical memory)

Pages can be placed anywhere in RAM.

Example

Instead of:

80 KB continuous block required

The process can be divided into:

Page 1
Page 2
Page 3
Page 4

Each page can occupy different memory locations.

Result

External Fragmentation Eliminated

Important Exam Point

Paging eliminates external fragmentation but may introduce internal fragmentation.

12. Solution 3: Segmentation

Segmentation divides a process into logical units such as:

• Code

• Data

• Stack

• Heap

Advantage

Provides logical organization of memory.

Limitation

Segments still require contiguous allocation.

Therefore:

External Fragmentation Can Still Occur

Segmentation reduces fragmentation in some cases but does not eliminate it.

13. External vs Internal Fragmentation

Internal Fragmentation Example

[ Process ][ Unused ]

Unused memory exists inside the allocated region.

External Fragmentation Example

[ Process ][ Free ][ Process ][ Free ]

Free memory exists but is scattered.

14. The 50% Rule (Advanced Exam Concept)

In systems using First-Fit allocation, a classical observation known as the 50% Rule states:

For every N allocated blocks, approximately:

N/2 free blocks

tend to exist because of fragmentation.

This demonstrates how external fragmentation naturally accumulates over time.

15. Real-World Analogy

Imagine a parking lot.

Available spaces:

Small Spot
Small Spot
Small Spot
Small Spot

Total space is enough for a truck.

However:

Truck Requires One Large Spot

Because no large continuous space exists, the truck cannot park.

This is exactly how external fragmentation works.

Most Important Point

External Fragmentation occurs when sufficient free memory exists in total, but it is divided into non-contiguous holes, preventing allocation of large contiguous memory blocks.