Fragmentation in operating system is a condition that occurs during contiguous memory allocation. In contiguous memory allocation, when user processes are loaded and unloaded from the physical memory, it breaks the free memory space into little pieces, which we refer to as fragments.
Fragmentation is of two types, internal fragmentation and external fragmentation. Internal fragmentation occurs during the fixed-size memory allocation method. However, the external fragmentation is a result of variable-size memory allocation.
In this section, we will discuss fragmentation in detail and its types. So, let’s start.
Content: Fragmentation in Operating System
- What is Fragmentation?
- Types of Fragmentation
- Internal Fragmentation
- External Fragmentation
- Internal Vs External Fragmentation
What is Fragmentation?
Fragmentation in operating system is a condition or state that occurs during contiguous memory allocation. In contiguous memory allocation, the processor allocates a contiguous section of memory to each process, waiting in the input queue.
To allocate the contiguous memory to a process, we have two methods fixed-sized partition and dynamic partition.
1. Fixed-Sized Partition
In a fixed-sized partition, the main memory is divided into fixed-sized blocks such that each block/partition contains exactly one process. The fixed-sized partition strictly bound the degree of multiprogramming. Whenever a new process arrives, it is loaded into the free partition. When the process terminates, the partition becomes available for the other processes.
2. Dynamic Partition
In the dynamic partition method, the operating system maintains a table to represent which part of the memory is occupied by user processes and which is still available. At the start, the entire memory is available for user processes, and we refer to this large block of memory as a hole.
Eventually, the loading and unloading of user processes leave a set of holes of various sizes in the main memory. At this point, the OS needs to check whether the newly freed and recombined (contiguous) holes could satisfy the need of processes waiting for the memory.
Well, to resolve this problem, some of the most common solutions are first-fit, best-fit, and worst-fit.
- In the first-fit strategy, the operating system identifies a first hole big enough to accommodate the process and allocates the hole to the process.
- Now, in the best-fit strategy, the operating system identifies the smallest hole big enough to accommodate the user process and allocates it to the process.
- In the worst-fit strategy, the operating system identifies the largest hole and allocates it to the user process.
Thus, allocating and deallocating memory to user processes leaves many fragments or small holes scattered in contiguous memory allocation. These fragments, when integrated, create a total memory space that is enough to satisfy a memory request. But the available memory is not contiguous. We refer to this condition as fragmentation.
Types of Fragmentation
We can classify fragmentation into two types, i.e. internal and external.
In the section above, we have learned about the two memory allocation techniques fixed-sized memory allocation and dynamic memory allocation.
The fixed-size memory allocation leads to internal fragmentation. However, dynamic-size or variable-size memory allocation leads to external fragmentation.
Internal Fragmentation
Internal fragmentation occurs in fixed-size memory allocation techniques. The main memory is divided into fixed-size blocks in the fixed-size memory allocation technique. Now, the operating system allocates memory in units based on block size whenever memory is requested.
With the fixed-sized memory allocation technique, the memory allocated to a user process may be slightly greater than the size of the user process. Thus we can define internal fragmentation as unused memory internal to the partition.
Example of Internal Fragmentation
Consider that the operating system divides memory into several fixed-sized partitions, where each partition is 24 KB. Now consider there is a memory request of 23 KB. Now, if we allocate a fixed-sized partition of 24 KB to the process, we are left with a hole of 1 KB. We refer to this fragment as internal fragmentation.
If observed carefully, the overhead of keeping a record of this internal fragment of 1 KB is substantially greater than the fragment itself.
A solution to internal fragmentation is using a complementary method, i.e. segmentation. Segmentation divides the process into segments. The operating system loads these segments to dynamic partitions of memory that must be contiguous.
External Fragmentation
In dynamic partitioning or variable-size memory allocation methods, whenever a user process requests for memory, it is allocated exactly the required amount of memory. With dynamic partitioning, eventually, a lot of small holes (fragments) are created in the memory. Over time, this fragmentation increases, thereby reducing memory utilization. We refer to this kind of fragmentation as external fragmentation.
A solution to external fragmentation is compaction.
The operating system timely runs a shift where all the processes in the memory are shifted such that they are all contiguous. It eventually forms a single block of free memory.
Another solution for eliminating external fragmentation is to allow the logical address space allocated to the process to be non-contiguous. A complementary technique to achieve this is paging.
In paging, the system divides the memory into n number of equal size frames. The system also divides the user process into n number of pages same as the length of the frame. Now, whenever the system has to load a process into the memory, it must load all of its pages into available frames. Here, the allocated frames may or may not be contiguous.
The First-fit and best-fit methods of variable size partitioning usually result in external fragmentation. However, the amount of fragmentation differs in first-fit and best-fit.
Example of External Fragmentation
The figure below explains how external fragmentation takes place.
Consider that we have 64 megabytes of main memory, of which 8 MB is allocated to the operating system, and 56 Mb is for user processes. At first, user process 1 arrives, and the system allocates 20 MB. Next, it allocates 14 MB to process 2, then 18 MB to process 3, and still, memory space of 4 MB is available.
Now, process 2 is removed from the memory vacating the space of 14 MB. The system allocates vacated space to process 4 of 12 MB, again leaving a hole of 2 MB. Subsequently, process 1 is also removed from the memory vacating the space of 20 MB. The system allocates the vacated space to process 2 of 14 MB, which again creates a hole of 6 MB. So, the last state of memory in the figure above shows fragments of 6, 2 and 4 MB, which are too small to allocate to any other process.
Internal Vs External Fragmentation
| Basis for Comparison | Internal Fragmentation | External Fragmentation |
|---|---|---|
| Occurr | Occurs in fixed-sized memory allocation | Occurs in variable-sized memory allocation |
| Meaning | The difference between memory allocated and memory required by a process forms internal fragmentation | The unused, free or wasted space between two non-contiguous allocated memory forms external fragments that are too small to serve any process |
| Cause | Internal fragmentation occurs when the allotted memory space is greater than the user process | External fragmentation occurs when user processes are removed from memory, leaving the free space broken into little pieces |
| Solution | With segmentation allocating the best-fit block to the user process provides the solution to internal fragmentation | Compaction and paging provide a solution to external fragmentation |
So, this is all about how fragmentation in the operating system occurs. What are the types of fragmentation and their solution? We have also discussed the differences between internal and external fragmentation.
Leave a Reply