Fragmentation in Operating System

Fragmentation is a memory-management problem in which some portion of available memory becomes difficult to use efficiently because of the way memory has been allocated to processes. The important point is that fragmentation does not simply mean that memory has become "empty." It describes a mismatch between the way free space is arranged and the way memory requests need to be satisfied.

During the lifetime of a system, processes are created, loaded into memory, suspended, terminated, and replaced by other processes. When these operations occur repeatedly, the arrangement of allocated and free memory can become less convenient for future allocations. Depending on the allocation technique, the unused space may occur inside an allocated block or may appear as separate gaps between allocated blocks.

Why Does Fragmentation Occur?

Fragmentation is closely related to the memory allocation strategy used by an operating system. Consider a system that initially has a large free memory area. Several processes may be loaded into that area. Later, some of those processes finish and release their memory. The newly released areas may not be adjacent to one another.

A future process may require a particular amount of memory. Even if the total amount of free memory is greater than the requested amount, the request may still be difficult to satisfy when the allocation method requires one sufficiently large contiguous region.

Two Main Forms of Fragmentation

Fragmentation is generally discussed in two forms:

• Internal Fragmentation – unused space exists inside an allocated block.
• External Fragmentation – free space exists outside allocated blocks but is scattered into separate regions.

---

1. Internal Fragmentation

Internal fragmentation occurs when the allocation unit supplied to a process is larger than the amount of memory that the process actually needs. The unused portion remains inside the allocated unit. Since that block has already been assigned, the operating system cannot normally give the unused portion to another process as an independent allocation.

The key characteristic is therefore the location of the wasted space. The unused memory is located within the boundary of an allocated block.

Figure 1: Internal fragmentation occurs when unused space remains inside an allocated memory block.

Internal Fragmentation in Paging

Paging is based on fixed-size pages and frames. A process is divided into pages, and each page occupies a complete frame. If the last page of a process does not completely fill its frame, the remaining portion of that frame is unused by that process.

For example, if the page size is 4 KB and a process requires 10 KB, the process needs three pages:

• Page 1 → 4 KB
• Page 2 → 4 KB
• Page 3 → 2 KB actually used

The third page occupies a complete 4 KB frame, leaving 2 KB unused in that frame. This unused portion represents internal fragmentation.

Characteristics of Internal Fragmentation

• The unused space is located inside an allocated block.
• It is strongly associated with fixed-size allocation units.
• Paging can produce internal fragmentation, particularly in the last page.
• Smaller allocation units can reduce waste but may increase management overhead.
• The wasted space is already part of an allocated block.

---

2. External Fragmentation

External fragmentation has a different structure. Here, memory that is currently free exists outside allocated blocks, but the free space is divided into multiple separated regions.

This becomes important when an allocation request needs one contiguous memory region. The operating system may have enough total free memory, but no individual free region may be large enough for the request.

Figure 2: External fragmentation occurs when free memory is distributed across separate holes.

Where Does External Fragmentation Occur?

External fragmentation is commonly associated with variable-size contiguous allocation. When processes of different sizes are allocated and later released, holes of different sizes can appear between active processes.

Segmentation is another technique in which variable-sized segments can contribute to external fragmentation when segments need contiguous physical regions.

Characteristics of External Fragmentation

• Free memory exists outside allocated blocks.
• Free space is divided into multiple holes.
• The total free memory may be sufficient for a request.
• A contiguous allocation request may still fail.
• Compaction can sometimes combine scattered free areas into a larger region.

Internal vs External Fragmentation: Core Difference

Point	Internal Fragmentation	External Fragmentation
Where is space wasted?	Inside an allocated block.	Between allocated blocks as separate free holes.
Main reason	Allocation unit is larger than the actual request.	Free memory becomes divided into separate regions.
Nature of allocation	Usually associated with fixed-size allocation.	Usually associated with variable-size contiguous allocation.
Typical example	Unused portion of the last page.	Several small holes between processes.
Can total free space be misleading?	Yes, because some allocated space may not be useful.	Yes, because free space may be scattered.
Common approach	Choose an appropriate allocation unit size.	Use compaction or an allocation technique that reduces unusable holes.

Visual Understanding of Internal Fragmentation

The entire 8 KB block has been allocated to the process. The 2 KB unused portion is located inside the allocated block, so it is internal fragmentation.

Visual Understanding of External Fragmentation

The free regions are separated by allocated processes. Their total size may be large, but a process requiring one contiguous block may not fit into any individual hole.

---

Fragmentation and Memory Allocation Strategies

Variable-size memory allocation strategies can influence how free holes are created and reused. Three commonly discussed strategies are First Fit, Best Fit, and Worst Fit. These algorithms do not completely eliminate fragmentation; instead, they determine how a requested block is selected from available free holes.

First Fit

First Fit searches the free list from the beginning and selects the first hole that is large enough for the requested process.

Best Fit

Best Fit searches for the smallest available hole that can satisfy the request. The intention is to avoid wasting a large hole for a relatively small process.

Worst Fit

Worst Fit chooses the largest available hole for the request. The idea is to leave a reasonably large remainder after allocation.

Solved Numerical Problem 1: Internal Fragmentation

Solved Numerical Problem 2: Paging and Internal Fragmentation

Solved Numerical Problem 3: External Fragmentation

Solved Numerical Problem 4: Effect of Compaction

What is Memory Compaction?

Compaction is a technique used to reduce external fragmentation by moving allocated memory blocks so that separate free holes are brought together into one larger free region.

Imagine that memory contains several active processes with small gaps between them. If those processes can be relocated safely, the operating system can move them toward one side of memory. The gaps then merge into a larger continuous free area.

Advantages of Compaction

• Combines multiple small free holes into a larger free region.
• Can make a large contiguous allocation possible.
• Improves the usability of scattered free memory.
• Can reduce the immediate effect of external fragmentation.

Limitations of Compaction

• Moving processes requires processing time.
• Memory contents must be relocated carefully.
• Address-related information may need to be updated or handled through relocation support.
• It does not increase the total amount of physical memory.
• It is not appropriate as a remedy for internal fragmentation.

Can Fragmentation Be Completely Eliminated?

There is no single memory-management technique that removes every form of memory wastage in every situation. The choice of allocation method determines which type of fragmentation is more likely and how it can be controlled.

Fixed-size allocation can make free-space management simpler, but it may introduce unused space inside allocated units. Variable-size allocation can use requested sizes more directly, but repeated allocation and release can create separated free holes.

Paging is particularly useful for avoiding the need for a process to occupy one contiguous physical memory region. However, paging can still have internal fragmentation, especially in the final page of a process.

Compaction can address scattered free space in systems where relocation is practical, but it introduces its own overhead.

Fragmentation in Paging and Segmentation

Technique	Fragmentation Concern	Reason
Paging	Internal Fragmentation	The final page of a process may not completely fill its allocated frame.
Segmentation	External Fragmentation	Segments are variable in size and may require contiguous physical space.
Fixed Partitioning	Internal Fragmentation	A partition can be larger than the process assigned to it.
Variable Partitioning	External Fragmentation	Repeated allocation and release can create separated free holes.

Internal Fragmentation Percentage

In numerical questions, fragmentation may also be expressed as a percentage of the allocated memory.

External Fragmentation: A Numerical Way to Think About It

External fragmentation does not have one universally useful percentage formula comparable to internal fragmentation because the practical issue is often whether a particular contiguous request can fit into an individual hole.

Therefore, numerical questions involving external fragmentation usually provide a list of free holes and ask whether a requested process can be allocated using a particular strategy.

Common Mistakes Students Make

1. Confusing total free memory with a contiguous free block.
   A system may have enough total free memory but still fail a contiguous request.
2. Calling every unused byte internal fragmentation.
   Internal fragmentation specifically refers to unused space within an allocated unit.
3. Assuming compaction creates new memory.
   Compaction rearranges memory; it does not increase physical memory capacity.
4. Assuming Best Fit always produces the least fragmentation.
   The result depends on the sequence of allocations and releases.
5. Mixing page size with process size.
   In paging problems, the number of pages is obtained by rounding the required number of pages upward.

Advantages and Disadvantages of Studying Fragmentation Techniques

Frequently Asked Questions

Interview Questions on Fragmentation

1. What is the main difference between internal and external fragmentation?
   Internal fragmentation wastes space inside an allocated block, whereas external fragmentation refers to free space scattered between allocated blocks.
2. Why does paging generally avoid external fragmentation?
   Because a process's pages can be placed in separate physical frames instead of requiring one contiguous physical region.
3. Why can paging still have internal fragmentation?
   Because a process's final page may use only part of its allocated frame.
4. What is the purpose of compaction?
   Compaction combines scattered free holes into a larger contiguous region.
5. Can external fragmentation exist even when total free memory is large?
   Yes. If the free memory is divided into small holes and a request requires one contiguous block, the request may fail.
6. What are First Fit, Best Fit and Worst Fit?
   They are memory allocation strategies used to select an appropriate free hole for a process request.
7. Which allocation strategy always gives the best performance?
   There is no universally best strategy. Performance depends on the memory workload and implementation.

Practice Problems

Try the following questions without opening the solutions first. These problems cover both conceptual and numerical aspects of fragmentation.

Quick Revision: Fragmentation

• Fragmentation: inefficient utilization of available memory.
• Internal Fragmentation: unused space inside an allocated block.
• External Fragmentation: free space scattered between allocated blocks.
• Paging: can have internal fragmentation.
• Segmentation: can have external fragmentation.
• Compaction: combines scattered free holes.
• First Fit: first suitable hole.
• Best Fit: smallest suitable hole.
• Worst Fit: largest suitable hole.
• Important numerical point: total free memory is not necessarily equal to usable contiguous memory.

Exam-Oriented Short Notes

Conclusion

Fragmentation is an important concept in operating-system memory management because the usefulness of memory depends not only on how much memory is available but also on how that memory is organized. Internal fragmentation represents unused space within allocated units, while external fragmentation represents separated free regions that may be difficult to use for contiguous allocation.

Understanding this distinction makes several other operating-system topics easier to study. Paging explains how fixed-size pages and frames can avoid the need for contiguous physical allocation, while segmentation demonstrates the advantages and challenges of variable-size logical memory regions. Memory-allocation algorithms such as First Fit, Best Fit and Worst Fit provide different ways of selecting free regions, while compaction can consolidate scattered free space when relocation is possible.

For examinations and interviews, the most important points to remember are the location of wasted space, the reason fragmentation occurs, the type of fragmentation associated with common allocation techniques, and the numerical method used to calculate unused space or determine whether a contiguous request can be satisfied.