Fragmentation in OS (Operating System)

When we work on computers, we may use various applications and programs through browsers, and all of them occupy some storage in the RAM of the computer. However, what happens when RAM is not managed properly or becomes fragmented? This is leading to memory fragmentation, which can be a problem. Let’s explore the concept of fragmentation in an operating system, its impact on a computer, and how operating systems manage memory to eliminate fragmentation.

Table of Contents:

• What is Fragmentation in Operating System?
• Memory Management Fundamentals
• Contiguous Memory Allocation Explained
• Common Causes Behind Fragmentation
• Types of Fragmentation in Operating Systems
• Fragmentation Handling & Prevention Techniques
• Impacts of Fragmentation in Operating Systems
• Drawbacks of Fragmentation in Operating Systems
• Fragmentation in Windows vs Linux
• Conclusion

What is Fragmentation in Operating System?

Fragmentation in an operating system is a condition in which memory is divided into small parts, and those parts are wasted. Even if there is free memory, a new program may not be able to utilize that free space because it is not in one sufficiently large contiguous block.

You can think of it like this: you have a drawer, and between your clothes, you have several small empty spaces, but there is not one big enough space to put a new shirt. Even though there is a space overall, it cannot be used. Fragmentation on a computer causes memory inefficiency and latency.

Why Fragmentation Matters in Memory Management:

• It helps in reducing the usable memory that is available.
• If there is enough total free space, it may stop new programs from loading.
• Management of memory gets very difficult for the OS.

Memory Management Fundamentals

Memory partitioning is the process of dividing the memory into smaller parts called partitions. These partitions enable you to organize the storage of programs and processes in memory. Partitioning is one of the main methods used in memory management to utilize the memory space provided by the computer efficiently and prevent programs from overlapping.

The two types of partitioning are

• Fixed Partitioning
• Dynamic Partitioning

Let us understand each one:

Boost your tech career with Software Development – Sign up now!

Practical projects, job-ready skills, and expert guidance.

Explore Program

1. Fixed Partitioning

In fixed partitioning, we allocate memory into predefined blocks when a system is started. The block size remains the same throughout the life of the operating system. Each partition can hold only one program, regardless of how much memory the program needs.

In fixed partitioning, we allocate the memory into blocks that are predefined when the system starts.

Fix Partitioning Advantages:

• Simple implementation: Simple design and implementation in the operating system.
• Fast allocation: Because the partitions are predefined, memory allocation is fast.
• Low overhead: There is less processing overhead to manage memory blocks.
• Memory management is predictable: The allocation and usage of memory are more predictable.

Fixed Partitioning disadvantage:

• Internal Fragmentation: If a program is smaller than its partition, then there can be a waste of memory.
• Limited Program Size: If a program is too large, then it will not fit in any partition.
• Inefficient Use of RAM: If partitions are poorly allocated, then not all memory may be used.
• Inflexibility: Being fixed makes it tough to adapt to various workloads/program sizes.

2. Dynamic Partitioning

In Dynamic Partitioning, memory is allocated according to the true size of the program, and when a program needs memory, a block is created to exactly fit the needs of the program. Dynamic Partitioning provides more flexibility as compared to Fixed Partitioning.

Advantages of Dynamic Partitioning:

• Utilization of Memory: There will be less internal fragmentation since blocks will fit the program size exactly.
• Flexible Allocation: Programs of various sizes will be better supported.
• No Unused Partition Space: Unused memory can be utilized for future programs.
• Room for Large Programs: Programs can be loaded without the limiting block size.

Dynamic Partitioning Disadvantages:

• External Fragmentation: Small gaps can exist between blocks that are allocated.
• Slow Allocation: Finding a suitable block will take time.
• Management Complexity: The Operating System must manage allocations and gaps in free space.
• Compaction Overhead: The OS will spend time periodically compacting memory to remove fragmentation.

Contiguous Memory Allocation Explained

One of the methods for storing programs in memory is called Contiguous Memory Allocation. In this method, each program must reside in a single continuous block in memory. This means the OS has to find a single unbroken section of RAM that is big enough to hold the entire continuous block of allocated memory. The OS attempts to load up every program in a continuous block by not breaking any program up or loading only a part of the program in memory at any one time. This makes it easier to load the program as a whole into memory, but consequently leads to memory problems in the long run.

Common Problem: Fragmentation

As programs are loaded and unloaded, small pockets of free memory can result between allocated sections. This leads to fragmentation, where there may be enough total memory available, but not enough contiguous space available to load a new program.

To address the fragmentation, the OS may use

• Compaction: Moving programs in memory so that the free space is grouped.
• Paging and Segmentation: More advanced techniques where programs are broken down into small parts, which can be stored non-contiguously. (This is dealt with in more advanced memory management.)

Common Causes Behind Fragmentation

Fragmentation occurs when free memory is broken up into small, unusable chunks that the system cannot allocate to a new program. While the total free memory may be available to the program, if the free memory is scattered, it will not be usable.

Fragmentation as a Result of Allocation and Deallocation

When programs are loaded or allocated to memory and later removed (deallocated from memory), they leave gaps or holes in memory. Over time, those holes or gaps will become small enough that they become unusable, resulting in fragmentation. The more often programs are loaded and deallocated from memory, the more fragmentation in the memory there will be.

Types of Fragmentation in Operating Systems

Let’s explore different types of fragmentation in an operating system:

1. Internal Fragmentation

Internal fragmentation occurs when memory is segmented into fixed-size memory blocks, where the program does not fully use the whole space, which means wasted space inside of the block.

Advantages of Internal Fragmentation:

• Easy Allocation: Memory management is simple.
• Predictable Block Sizes: Makes memory management easier for the OS.
• Fast Access: Memory access is faster, and mapping in memory is done quickly because of fixed sizes.
• Good for Uniform Application Sizes: If most applications/programs exhibited similar sizes, it would work.

Disadvantages of Internal Fragmentation:

• Waste Memory: Unused space inside a memory block could not be utilized by another program.
• Limited What We Can Do with Memory: The fixed-size memory blocks may not work with all applications.
• Limits Usable Memory: Internal gaps in memory reduce available memory; free memory does not necessarily mean it is available.
• Decreases System Efficiency: Small amounts of unused memory add to large amounts of waste when considered as a whole.

Dealing with Internal Fragmentation

• Use dynamic memory partitioning instead of static partitioning.
• Try to choose a block size according to the average size of the program.
• Utilize paging, where memory is broken into equally sized small pieces with little internal wastage.
• Examine application memory use to better match memory allocations.

2. External Fragmentation

External Fragmentation becomes an issue when, over time, pieces of free memory become small, and, therefore, the fragmentation in memory occurs. Even if you have enough free memory overall, it cannot be used because there is no contiguous piece large enough to fill the request.

Advantages of External Fragmentation:

• Efficient for Large Allocations Initially.
• Supports Dynamic Program Size
• There is no wasted space inside partitions.
• Very flexible memory allocation.

Disadvantages of External Fragmentation:

• Even though the memory is technically free, it is unusable due to a lack of contiguous space.
• Must compact and move programs frequently, which might reduce performance as the OS has to rearrange programs in memory.
• Allocating memory becomes too slow because gaps need to be searched to find suitable ones.
• The performance of a system will degrade over time, especially for long-running systems that make changes to allocations frequently.

How to Remove External Fragmentation

• Compaction: Move programs that are in memory so that free blocks are together in one space.
• Segmentation: Programs are comprised of logical segments that can fit into a gap at different locations in memory.
• Paging: Programs are assigned to fixed-size pages, so it avoids the need for them to be in continuous blocks.
• More Efficient Allocation Algorithms: Apply allocation algorithms that extract fragmentation internally or externally to reduce the fragmentation. Use first-fit, best-fit, and worst-fit techniques.

3. Data Fragmentation

Data fragmentation takes place when similar data is stored in separate, non-contiguous locations, often in secondary storage (such as a hard disk or database), making access to that data slow since the user would need to jump between locations to access each bit of the full data.

Advantages of Data Fragmentation:

• Better Disk Utilization: Efficient use of smaller disk spaces that may not otherwise be utilized.
• Faster Initial Writes: No need to seek out large amounts of free contiguous space.
• Increased Parallel Access: In distributed access systems, each data fragment can be read at the same time.
• Better Flexibility in Storage: Allows the user to have data that is on separate storage media and supplies location points.

Cons to Data Fragmentation:

• Slower Speed of Access: Reading fragmented data significantly slows down the access time.
• Increased Disk I/O: More head movement, which increases the number of read operations the disk head performs due to non-contiguous data.
• Difficult to Manage: Data management can become difficult.
• Reduced Performance: Particularly in large datasets and with frequent access.

How to Prevent Data Fragmentation

• Use Defragmentation Tools: Run system tools to rearrange files into a contiguous set of disk space.
• Optimize Database: Rebuild indexes or compact stored data.
• Feasible Storage: Using techniques such as clustering or caching can help.
• Good Practices: Practice regular maintenance and schedule cleaning tasks regularly, which can help reduce data fragmentation over time.

Fragmentation Handling and Prevention Techniques

Now let’s discuss the various techniques for handling and preventing fragmentation:

1. Compaction (Defragmentation)

Compaction involves the OS moving programs in memory to put all scattered free space back together in one block of space. This is a way to eliminate external fragmentation.

Advantages:

• Maximizes Free Space: Combines small gaps of free space into one block that can be used.
• Increases the Chance of Successful Allocation: It can be easier to fit large programs into memory.
• Simple concept: Easy to understand and visualize.
• Better Use of Memory: Frees up contiguous space.

Disadvantages:

• Time-Consuming: Involves moving a lot of data from one location to another.
• CPU Overhead: Uses processing power (CPU) during compaction.
• Breaks Program Execution: Certain programs may have to stop.
• Temporary: Continued use will lead to fragmentation again.

2. Paging

Paging partitions memory and programs into small, fixed units called pages (memory) and frames (programs). These units of memory can exist within memory non-contiguously.

Advantages:

• Reduces External Fragmentation: Programs stored in non-contiguous memory locations.
• Increased, More Efficient Memory Usage: Memory only holds necessary pages.
• Faster Memory Allocation: No search for unbroken larger blocks of memory.
• Simplifies memory management from complexity: Units of memory are the same size, making it easier for the OS to track.

Disadvantages:

• Internal Fragmentation: The last page or frame may not be used.
• Overhead from Page Tables: Managing logical-address to physical-address mapping means an overriding need for storage to keep the mapping.
• Page Faults: Accessing unloaded pages tends to slow the entire system down.
• Complex Address Translation: This involves translating logical addresses into physical addresses.

3. Segmentation

In segmentation, memory is divided into chunks of variable size according to logical divisions in the program (functions, arrays, etc.). Each segment exists separately.

Advantages:

• Logical Organization: Aligns with the way programmers organize code.
• Flexible Allocation: Allocates segments of different sizes to fill memory gaps.
• Easier Sharing, Easier Protection: Segments can have different permissions.
• Support for Modular Programs: Easier to manage code and data.

Disadvantages:

• External Fragmentation: Variable size of segments means that there will be gaps between segments.
• Complex Management: It requires segment tables and mapping
• Difficult to Compact: Segments vary in size, the same way that physical pages vary, so moving sizes will always be tricky.

4. Paging with Virtual Memory

Virtual memory is an extension of paging with the use of virtual memory that allows programs to use more memory than is physically present by getting the data written to disk on a temporary basis.

Advantages:

• Run bigger programs: Even though you may have a small physical memory. This supports doing intensive work programs on systems with basic RAM.
• Better Multitasking: Handle multiple programs smoothly. Each of the programs has a Virtual Memory space and does not interfere with the others.
• Efficient use of RAM: Only the active pages are in memory; the inactive ones are written away (swapped). With virtual memory, RAM is only used for the important memory and currently needed references.
• Automatic memory management: Memory management is handled automatically by the operating system. Reduce manual configuration and improve how memory is handled and managed in your system.

Disadvantages:

• Slow access: Disk access is much slower than memory access, and swapping is slow. Swapping pages out is often slower than when the memory is simply accessed directly.
• Thrashing: The computer can be frozen with multiple pages swapped out. When a system spends more time swapping and taking pages back and forth than executing any tasks, it becomes “thrashing”.
• Page fault overhead: If there are too many page faults in a program, it can slow execution. If a page fault occurs, there will be an interruption of processes, and it will stop responsiveness when it is accessing the disk to load the information back into memory.
• Disk dependent: Virtual Memory and any paging look to optimize the disk IO path as fast as the memory. A slow disk that is in use or overloaded will certainly slow down any system, since disk access is much slower than memory access.

5. Buddy System

The buddy system allocates memory in powers of two (examples: 2 KB, 4 KB, 8 KB, etc.). If the data or program requires a bigger block than is available, we split the buddy and then allocate one of the halves.

Advantages:

• Efficient Allocation & Deallocation: It’s easy to split and merge blocks of memory. Memory management happens quickly when an executable program is running.
• Fast Search: The power-of-two structure allows for easier accessibility. Minimal lag in locating and allocating memory blocks.
• Reduces Fragmentation: When we merge buddies, we can reclaim space in memory. It allows space that was once used to be put back to work.
• Straightforward Implementation: It is easy to write and control. It is ideal for embedded systems and low-level OS memory management.

Disadvantages:

• Internal Fragmentation: The system may give you more memory than you need. The unused memory in the memory block cannot be used elsewhere.
• Space Consistency: The buddy system will have generally had consistent memory allocations. Some applications may require sizes that do not fit neatly into the buddy model.
• Wasted Memory: The system may set aside much more memory than your program will ever use.

Impacts of Fragmentation in Operating Systems

Let’s explore the impact of fragmentation on the system:

1. Effects on System Performance

Fragmentation can have a serious impact on system performance, including slowing and increasing inefficiency in memory allocation. With memory fragmented into many small, disjointed chunks, the operating system takes longer to find a matching free memory block for programs to run. This can cause increased CPU overhead and affect the total time taken to access memory. This can become a major issue when you go to run a program, and even though there is enough free memory, there is not a large enough contiguous block of memory available. Users who experience longer loading times or run multiple applications tend to see reduced response times from the system, which in some cases will cause system lag or crashes. Fragmentation causes a decreased spectrum of responsiveness and productivity for systems over time, as well as increased maintenance.

2. Memory and Resource Waste

Fragmentation causes more memory to be unused inside allocated blocks (internal fragmentation) or in the gaps (external fragmentation) between these blocks than you may think. Even when the total amount of free memory is still sufficient, free memory is often unusable because of fragmentation. This creates wasted memory that cannot be allocated to new processes. This also causes resource waste because the computer system is unable to use the full memory capability of the hardware. Over time, the waste can lead to unnecessary hardware strain, higher power consumption, and system degradation from using secondary storage (virtual memory) that is inherently slower, thus causing further degradation.

3. Problems in Large Applications

Large applications such as video editors, database systems, games, etc., have memory demands that are substantial but continuous; therefore, having sufficient memory allocated may be problematic. Memory fragmentation makes it difficult to allocate big enough memory blocks, resulting in failed loads or decreased performance levels. If a program cannot allocate enough memory at runtime, then the system may encounter abrupt failures or errors. Additionally, memory fragmentation makes it difficult to manage and maintain large applications, requiring developers and system administrators to add additional logic or even implement more tools (e.g., compaction or memory defragmentation utilities) to maintain memory demands consistently. This increases both the development time and system overhead when taking on this responsibility.

Drawbacks of Fragmentation in Operating Systems

1. Wasted Memory Usage

Fragmentation, both internal and external, inflicts damage in the form of small, unusable blocks of memory; these blocks compound together to reduce the total usable amount of memory, even when free memory is still available.

2. Performance Alignment

Fragmentation will also reduce performance, as fragmentation slows access to memory and allocation of new memory. If the available memory is fragmented, memory access and allocation will be slower as the OS will be working harder to find the appropriate blocks. Over time, fragmentation is cumulative and can lead to lag and inefficiencies in the system.

3. Higher Rate of Allocation Failures

Allocation failures will occur more often when fragmentation takes place. In many instances, unless the system is completely jammed, there is enough memory to run a program, but what may be problematic is finding a large enough continuous space. This can dramatically affect the ability to run large applications.

4. Higher Overhead Management

Whenever fragmentation occurs, the OS has to work harder. Over time, the memory management requires the OS to incur more overhead, and thus the OS has to work harder through processes like compaction or defragmentation, all while consuming additional CPU.

Fragmentation in Windows vs Linux

Advance Your Career with Software Engineering – Start Learning Now!!

Join thousands of learners building in-demand skills.

Explore Program

Conclusion

In this blog, we have learned about fragmentation in an operating system that uses memory inefficiently and performs worse overall. Techniques like paging, segmentation, and compaction can help reduce internal and external fragmentation, despite the fact that they are common. Better performance and more effective use of resources are guaranteed by proper memory management.

Fragmentation in Operating Systems – FAQs