Learn Internal and External Fragmentation in OS with examples, advantages, disadvantages, real-time applications, and solutions using Paging

Understanding Internal and External Fragmentation

Imagine you are hosting a birthday party. You rent tables for your guests, but each table can seat exactly 8 people. Now, if a group of 5 friends arrives, you still have to reserve the full table, leaving 3 seats empty. That empty space inside the table is like internal fragmentation in memory – memory that is allocated but goes unused.

Later, more guests arrive in smaller groups, and you have several empty seats scattered across multiple tables. But no single table has enough space for a group of 6, so you can’t seat them, even though there are enough empty seats in total. This is exactly like external fragmentation – free memory exists, but it’s scattered, making it unusable for larger allocations.

This simple party scenario helps visualize why memory fragmentation occurs in operating systems and why efficient memory management is crucial.

In operating system memory management, fragmentation is a common issue that affects efficient memory utilization. Fragmentation occurs when memory is used inefficiently, leading to wasted space. There are two main types of fragmentation: internal fragmentation and external fragmentation. Understanding their differences, along with how paging and segmentation address them, is crucial for students, developers, and IT professionals.

What is Internal Fragmentation?

Internal fragmentation happens when fixed-sized memory blocks are allocated to processes, but the allocated memory is slightly larger than the required memory. The unused portion inside the allocated block becomes wasted space.

Example of Internal Fragmentation:
Suppose a process requires 27 KB of memory, and the operating system allocates memory in blocks of 32 KB. The remaining 5 KB within that block cannot be used by other processes. This wasted space inside the allocated block is internal fragmentation.

Key Points:

• Occurs due to fixed-size memory allocation.
• Wasted space is inside allocated memory blocks.
• More common in contiguous memory allocation systems.

What is External Fragmentation?

External fragmentation occurs when free memory is scattered into small, non-contiguous blocks. Even if the total free memory is enough to satisfy a process, it cannot be allocated because it is not contiguous.

Example of External Fragmentation:
Imagine a system with 100 KB of free memory scattered as 20 KB, 15 KB, 30 KB, and 35 KB blocks. If a process requests 50 KB, the request cannot be fulfilled despite having 100 KB free because no single contiguous block is large enough.

Key Points:

• Happens in dynamic memory allocation.
• Wasted space exists between allocated blocks.
• Affects long-running systems with frequent memory allocation and deallocation.

How Paging Solves Fragmentation

Paging is a memory management scheme that divides physical memory into fixed-size blocks called frames and logical memory into pages. To learn more about how demand paging works and its practical applications in operating systems, you can check out this detailed guide here.

Benefits for Fragmentation:

• Reduces external fragmentation: Pages can be placed anywhere in physical memory. The process does not require contiguous memory.
• Internal fragmentation remains small: Some space may still be wasted if the last page of a process is not fully used.

Example:
A process of 70 KB is divided into 4 pages of 20 KB each. Each page fits into a frame anywhere in memory. Even if frames are scattered, the process runs smoothly. The last page may waste 10 KB, which is internal fragmentation, but there is no external fragmentation.

How Segmentation Solves Fragmentation

Segmentation divides memory into variable-sized segments based on logical divisions like code, data, and stack.

Benefits for Fragmentation:

• Reduces internal fragmentation: Segments are sized exactly as per requirement.
• May still face external fragmentation: Since segments are variable-sized, free memory might get fragmented.

Example:
A program has a code segment of 40 KB, data segment of 30 KB, and stack of 10 KB. Each segment is loaded exactly into memory without wasting space inside the segment, minimizing internal fragmentation.

C Implementation Example

Memory management is a crucial topic in operating systems. Issues like internal and external fragmentation can lead to inefficient memory usage. Techniques like paging and segmentation help manage memory efficiently. Let’s understand these concepts with practical C examples.

1. Internal Fragmentation in C

Internal fragmentation occurs when a fixed-size memory block is allocated to a process, but the process does not fully use it.

#include 

#define BLOCK_SIZE 32 // Fixed memory block size in KB

int main() {
    int process_size = 27; // Memory required by process
    int allocated_block = BLOCK_SIZE;
    int internal_frag = allocated_block - process_size;

    printf("Process size: %d KB\n", process_size);
    printf("Allocated block: %d KB\n", allocated_block);
    printf("Internal fragmentation: %d KB\n", internal_frag);

    return 0;
}

Output:

Process size: 27 KB
Allocated block: 32 KB
Internal fragmentation: 5 KB

Explanation: The 5 KB unused space inside the allocated block represents internal fragmentation. This is common in fixed-size allocation systems, like embedded systems or real-time operating systems (RTOS).

2. External Fragmentation in C

External fragmentation occurs when free memory is scattered in small, non-contiguous blocks. Even if total memory is sufficient, allocation fails.

#include 

int main() {
    int free_blocks[] = {20, 15, 30, 35}; // Free memory blocks in KB
    int process_size = 50;
    int allocated = 0;

    for(int i = 0; i < 4; i++) {
        if(free_blocks[i] >= process_size) {
            allocated = 1;
            free_blocks[i] -= process_size;
            break;
        }
    }

    if(allocated)
        printf("Process allocated successfully.\n");
    else
        printf("Cannot allocate process due to external fragmentation.\n");

    return 0;
}

Output:

Cannot allocate process due to external fragmentation.

Explanation: Although total free memory is 100 KB, the process cannot be allocated because no single contiguous block is large enough.

3. Paging Simulation in C

Paging divides memory into fixed-size frames and logical memory into pages, eliminating external fragmentation.

#include 

#define FRAME_SIZE 20 // Each frame is 20 KB
#define NUM_FRAMES 6

int main() {
    int process_size = 70; // Process requires 70 KB
    int pages_needed = (process_size + FRAME_SIZE - 1) / FRAME_SIZE;

    printf("Process size: %d KB\n", process_size);
    printf("Frame size: %d KB\n", FRAME_SIZE);
    printf("Pages needed: %d\n", pages_needed);

    // Simulate allocation
    for(int i = 0; i < pages_needed; i++) {
        printf("Allocating page %d to frame %d\n", i+1, i+1);
    }

    return 0;
}

Output:

Process size: 70 KB
Frame size: 20 KB
Pages needed: 4
Allocating page 1 to frame 1
Allocating page 2 to frame 2
Allocating page 3 to frame 3
Allocating page 4 to frame 4

Explanation: Even if frames are non-contiguous, the process is successfully allocated. Only the last frame may have minor unused space (internal fragmentation).

4. Segmentation Simulation in C

Segmentation allocates memory in variable-sized blocks based on logical divisions like code, data, and stack.

#include 

int main() {
    int code_segment = 40;  // 40 KB
    int data_segment = 30;  // 30 KB
    int stack_segment = 10; // 10 KB

    printf("Code segment: %d KB\n", code_segment);
    printf("Data segment: %d KB\n", data_segment);
    printf("Stack segment: %d KB\n", stack_segment);

    printf("Total memory allocated: %d KB\n", code_segment + data_segment + stack_segment);

    return 0;
}

Output:

Code segment: 40 KB
Data segment: 30 KB
Stack segment: 10 KB
Total memory allocated: 80 KB

Explanation: Memory is allocated exactly as needed for each segment, minimizing internal fragmentation. However, external fragmentation may still occur if free memory blocks are scattered.

Key Differences Between Internal and External Fragmentation

Advantages and Disadvantages

Fragmentation in memory management can significantly impact the performance of an operating system. Understanding the advantages and disadvantages of internal and external fragmentation, along with their solutions like paging and segmentation, is crucial for optimizing memory use.

Internal Fragmentation

Internal fragmentation occurs when a process is allocated fixed-size memory blocks, and the allocated memory is larger than required, wasting space inside the block.

Advantages of Internal Fragmentation

1. Simple Memory Allocation
   • Fixed-size allocation simplifies memory management because the OS knows exactly how big each block is.
   • Easy to implement using paging or block allocation.
2. Faster Access and Less Overhead
   • Because blocks are of uniform size, memory allocation and deallocation are faster.
   • Reduces computational overhead during memory management.
3. Predictable Performance
   • Fixed-size blocks make memory access predictable, which is important for real-time systems.

Disadvantages of Internal Fragmentation

1. Wasted Memory Space
   • Any unused memory within a block remains wasted.
   • Example: Allocating a 32 KB block for a 27 KB process wastes 5 KB.
2. Scalability Issues
   • With many small processes, internal fragmentation can accumulate, reducing overall memory efficiency.
3. Not Suitable for Variable-Sized Data
   • Fixed-size allocation struggles with processes that have varying memory requirements.

External Fragmentation

External fragmentation occurs when free memory is split into small, non-contiguous blocks. Even if total free memory is sufficient, processes may not fit.

Advantages of External Fragmentation

1. Efficient for Variable-Sized Allocation
   • Allows allocation of different-sized memory blocks according to the process requirements.
   • Supports segmentation, where memory is allocated based on logical divisions like code, stack, and data.
2. Flexibility
   • Processes do not have to conform to fixed-size blocks, making memory allocation more flexible.

Disadvantages of External Fragmentation

1. Memory Wastage Between Blocks
   • Free memory is scattered and may be too small for incoming processes.
   • Example: A total of 100 KB free memory may be unusable if scattered in blocks smaller than requested size.
2. Memory Compaction Overhead
   • To reduce fragmentation, operating systems may perform memory compaction, which is CPU-intensive.
3. Inefficient Long-Term
   • Systems with frequent allocation and deallocation can accumulate external fragmentation over time, decreasing performance.

How Paging Helps

Paging divides memory into fixed-size frames and logical memory into pages.

Advantages in Addressing Fragmentation:

• Eliminates external fragmentation: Pages can be allocated anywhere in physical memory.
• Minimizes internal fragmentation: Only the last page may have slight wasted space.
• Simplifies memory management: No need to find contiguous blocks for processes.

Disadvantages of Paging:

• Slight internal fragmentation: If a process doesn’t perfectly fit into frames, some memory is wasted.
• Page table overhead: Requires additional memory for storing page tables.

How Segmentation Helps

Segmentation divides memory into logical, variable-sized segments.

Advantages in Addressing Fragmentation:

• Reduces internal fragmentation: Segments are sized to exact requirements of processes.
• Logical organization: Code, data, and stack can be managed separately, making programs easier to handle.

Disadvantages of Segmentation:

• Can cause external fragmentation: Since segments are variable-sized, free memory blocks may get scattered.
• Complex memory management: Requires segment tables and mapping logic.

Summary Table: Fragmentation Pros and Cons

Real-Time Applications of Fragmentation

In modern computing, efficient memory management is critical for the performance of systems. Internal and external fragmentation are key challenges that can degrade system efficiency if not properly managed. Techniques like paging and segmentation are widely used to handle these issues. Understanding their real-time applications helps engineers design optimized systems.

Real-Time Applications of Internal Fragmentation

Internal fragmentation occurs when memory blocks are larger than required, leaving unused space inside allocated blocks. Despite being considered a memory “waste,” internal fragmentation is still applicable in several real-time scenarios:

1. Embedded Systems
   • Many embedded devices allocate fixed-size memory blocks for sensors, controllers, or microcontrollers.
   • Example: A microcontroller reading sensor data may allocate 32 KB blocks, even if the sensor needs only 28 KB. The slight internal fragmentation simplifies memory management and ensures predictable performance.
2. Real-Time Operating Systems (RTOS)
   • RTOS environments prioritize deterministic behavior. Fixed-size memory allocation leads to predictable access times, reducing scheduling delays.
   • Example: In an automotive control system, memory blocks for critical tasks are preallocated to avoid delays caused by dynamic allocation.
3. Networking Buffers
   • Routers and switches use fixed-size buffers for packets. Wasted memory in buffers (internal fragmentation) is acceptable because it ensures faster packet processing.

Real-Time Applications of External Fragmentation

External fragmentation happens when free memory is scattered in small, non-contiguous blocks, making allocation difficult even when sufficient total memory exists. Its real-time applications include:

1. Dynamic Memory Management in Servers
   • Web servers and database servers frequently allocate and deallocate memory of variable sizes. External fragmentation occurs naturally.
   • Example: A database engine may fail to allocate a large data structure even if total memory is sufficient because the free space is fragmented.
2. Multimedia Systems
   • Video or audio streaming applications allocate memory dynamically for frames or audio buffers. External fragmentation can slow down real-time streaming if contiguous memory is required.
3. Long-Running Operating Systems
   • External fragmentation is more common in OS that run continuously, like industrial control systems. Memory compaction or paging is often used to maintain real-time performance.

Real-Time Applications of Paging

Paging divides memory into fixed-size frames, removing the need for contiguous memory. Its real-time applications include:

1. Operating System Memory Management
   • Paging eliminates external fragmentation, ensuring efficient memory usage in systems that handle multiple processes.
   • Example: Linux-based real-time OS running multiple applications uses paging to allocate memory frames anywhere in RAM.
2. Virtual Memory Systems
   • Paging allows real-time applications to exceed physical memory limits by mapping pages to disk storage.
   • Example: Real-time simulation software for engineering may use virtual memory without performance degradation due to paging.
3. Real-Time Multi-Tasking Systems
   • Ensures each task gets memory instantly, without waiting for contiguous memory.
   • Example: Industrial robots using multi-tasking RTOS benefit from fast, predictable memory allocation through paging.

Real-Time Applications of Segmentation

Segmentation divides memory into logical, variable-sized segments, offering flexibility in memory allocation. Real-time applications include:

1. Programming Language Memory Models
   • Segmentation matches logical program divisions such as code, stack, and data.
   • Example: A real-time compiler allocates memory segments for program modules, ensuring efficient execution and reducing internal fragmentation.
2. Critical Embedded Systems
   • Systems with multiple critical functions, like avionics or medical devices, use segmentation to allocate precise memory to each module.
   • Example: Flight control systems allocate segments for navigation, communication, and monitoring subsystems independently.
3. Database Management Systems (DBMS)
   • Segmentation is used to separate index, data, and transaction logs in memory. This helps in predictable performance for real-time queries.

Conclusion

Understanding internal and external fragmentation is essential for effective memory management in operating systems. While internal fragmentation wastes space inside allocated blocks, external fragmentation leaves free memory unusable due to scattering. Techniques like paging and segmentation efficiently address these issues, ensuring optimal memory utilization and improving system performance.

FAQ : Master Internal and External Fragmentation , Paging & Segmentation

1. What is internal fragmentation in operating systems?

Answer: Internal fragmentation occurs when a process is allocated a fixed-size memory block, but does not use all the space inside it. The unused memory within the block is wasted. This commonly happens in paging systems where the last page of a process may be partially empty.

2. What is external fragmentation in operating systems?

Answer: External fragmentation happens when free memory is split into small, non-contiguous blocks. Even if the total free memory is sufficient for a process, it may not be allocated because no single block is large enough. It is common in systems with variable-sized memory allocation.

3. How does paging solve fragmentation?

Answer: Paging eliminates external fragmentation by dividing memory into fixed-size frames and logical memory into pages. Pages can be placed in any available frame, allowing non-contiguous memory allocation. This ensures efficient memory usage and fast process allocation. For more details, see demand paging.

4. How does segmentation address fragmentation?

Answer: Segmentation divides memory into logical, variable-sized segments like code, data, and stack. It reduces internal fragmentation because each segment is allocated exactly as required. Segmentation is useful in embedded systems, DBMS, and real-time applications.

5. What is the difference between internal and external fragmentation?

Answer: Internal fragmentation wastes memory inside allocated blocks, while external fragmentation wastes memory between blocks. Internal occurs in fixed-size allocation; external occurs in variable-sized allocation. Paging reduces external fragmentation, and segmentation reduces internal fragmentation.

6. Can internal and external fragmentation occur together?

Answer: Yes. Some systems may experience both. For example, paging can still cause small internal fragmentation in the last page, while segmentation may lead to external fragmentation if segments cannot fit into contiguous memory.

7. What are real-time applications of internal fragmentation?

Answer: Internal fragmentation is acceptable in embedded systems and RTOS, where predictable memory allocation is more important than slight wasted space. Examples include sensor buffers, automotive controllers, and networking devices.

8. What are real-time applications of external fragmentation?

Answer: External fragmentation affects systems with dynamic memory allocation, like web servers, multimedia streaming, and long-running industrial OS. Memory compaction or paging is often used to maintain real-time performance.

9. Which is better: paging or segmentation?

Answer: Both have advantages:

• Paging: Eliminates external fragmentation, simple to implement, suitable for multi-tasking.
• Segmentation: Reduces internal fragmentation, aligns with logical program structure.
  The choice depends on system requirements; many modern OS use a combination of paging and segmentation.

10. How can I reduce fragmentation in my program?

Answer: To reduce fragmentation:

• Use paging for large multi-tasking systems.
• Use segmentation for logically divided programs.
• Regularly compact memory in systems with variable-sized allocations.
• Allocate memory carefully to minimize wasted space in embedded or real-time systems.

Raj Kumar

Mr. Raj Kumar is a highly experienced Technical Content Engineer with 7 years of dedicated expertise in the intricate field of embedded systems. At Embedded Prep, Raj is at the forefront of creating and curating high-quality technical content designed to educate and empower aspiring and seasoned professionals in the embedded domain.

Throughout his career, Raj has honed a unique skill set that bridges the gap between deep technical understanding and effective communication. His work encompasses a wide range of educational materials, including in-depth tutorials, practical guides, course modules, and insightful articles focused on embedded hardware and software solutions. He possesses a strong grasp of embedded architectures, microcontrollers, real-time operating systems (RTOS), firmware development, and various communication protocols relevant to the embedded industry.

Raj is adept at collaborating closely with subject matter experts, engineers, and instructional designers to ensure the accuracy, completeness, and pedagogical effectiveness of the content. His meticulous attention to detail and commitment to clarity are instrumental in transforming complex embedded concepts into easily digestible and engaging learning experiences. At Embedded Prep, he plays a crucial role in building a robust knowledge base that helps learners master the complexities of embedded technologies.

embeddedprep.com/