Fragmentation, External Fragmentation, Internal Fragmentation, first fit, best fit, worst fit in operating systems (OS)

By: Prof. Fazal Rehman Shamil						

Last modified on August 8th, 2020			

Fragmentation, External Fragmentation, Internal Fragmentation in operating systems (OS).

The user of a computer continuously load and unload the processes from the main memory. Processes are stored in blocks of the main memory. When it happens that there are some free memory blocks but still not enough to load the process, then this condition is called fragmentation.

Fragmentation is a condition that occurs when we dynamically allocate the RAM (Read More about RAM) to the processes, then many free memory blocks are available but they are not enough to load the process on RAM.

Advantages of Fragmentation

Failures: Without fragmentation, if we have no sequential free space, then the write operation will fail.
Faster data writes: Faster data writes due to short fragments.
Optimization of memory Storage: Fragmentation focus is to use every part of memory without wasting the memory.

Disadvantages of Fragmentation

Slower read times: Due to fragmentation, the amount of time it takes to read a non-sequential file can grow and can lead to slow read.
Need for regular defragmentation. Sometimes we need to defragment the memory.

There are two types of fragmentation;

External fragmentation
Internal fragmentation

External Fragmentation

Total free RAM space is enough to load a process but the process still can’t load because free blocks of RAM are not contiguous. In other words, we can say that all free blocks are not located together. For example, in the following diagram, we have a total 10 KB space free but it is not together located, so if a process with 10KB size wants to loads on the RAM, then can’t load due to external fragmentation. But in the diagram on the right side we can see that 10KB space is contiguously free, so here if a process of 10KB wants to load on the RAM then can execute.

Internal Fragmentation

Internal fragmentation occurs when fixed sized memory blocks are available and a process gets a block that is too much larger than the storage requirement of a process. The worst fit is mostly a big reason for internal fragmentation.

Difference between internal and external fragmentation in OS in tabular form

	External Fragmentation	Internal Fragmentation
Basics of fragmentation	When different size memory blocks are dynamically allocated to the processes.	When fixed sized memory blocks are allocated to the processes.
when fragmentation occurs	When the process releases the RAM, it creates the free space in the RAM which leads to cause external fragmentation.	When the memory assigned to the process is greater as compared to the memory requested by the process.
solution of fragmentation	Segmentation, paging and Compaction	The memory must be partitioned into variable sized blocks. Further, assign the best-fit block to the process.

First-fit memory allocation

In first-fit memory allocation, OS Allocate the first hole to the process that is big enough and the process size is less.

Best-fit memory allocation

In best-fit memory allocation, OS Allocate the most suitable smallest hole to the process. In best-fit memory, waste is less as compared to the worst fit and first, fit memory allocations.

Case Study of memory Fragmentation in operating systems.

Suppose we have some memory frames of 16KB, 14KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15K. Simmilalry we, have pages of 12KB, 10KB, and 9KB. How you will allocate the memory if you follow first fit, best fit, worst fit memory allocation scheme.

Example of First Fit Memory allocation
12KB page will reside in memory frame of 16KB.
10KB page will reside in memory frame of 14KB.
9KB page will reside in memory frame of 20KB.
Example of Best Fit Memory allocation
12KB page will reside in memory frame of 12KB.
10KB page will reside in memory frame of 14KB.
9KB page will reside in memory frame of 9 .
Example of worst Fit Memory allocation
12KB page will reside in memory frame of 20KB.
10KB page will reside in memory frame of 18KB.
9KB page will reside in memory frame of 15KB.
Example of Next Fit Memory allocation
12KB page will reside in memory frame of 16KB.
10KB page will reside in memory frame of 14KB.
9KB page will reside in memory frame of 20KB.

Worst-fit memory allocation

In Worst-fit memory allocation, OS Allocate the largest hole to the process and results in wastage of a large amount of memory.

Fragmentation is a memory management techniques

We can divide the memory management techniques into two main parts;

Uni-programming
Multi-programming

Uniprogramming

In uni-programming, the operating system divides them into two main parts. one part is dedicated to the operating system and another part is dedicated to the user processes.

Multiprogramming

multiprogramming is a technique which allows multiple users to share the memory at the same time. this is a very important feature of the operating system.

there are two types of possible memory allocations in multiprogramming;

contiguous memory allocation
noncontiguous memory allocation

Contiguous memory allocation

contiguous memory means that all the free blocks of memory are closely neighboured with each other.

Contiguous memory allocation in C

#include <stdio.h> 
#include <stdlib.h> 
int main() 
{ 
// This pointer will hold the base address of the block
int* T4Tutorials_Pointer; 
int n, i; 
// Total elements for the array 
n = 5; 
printf("Please Enter number of elements: %d\n", n); 
// calloc() is used to Dynamically allocate the memory 
T4Tutorials_Pointer = (int*)calloc(n, sizeof(int)); 
// memory successfully allocated or not 
if (T4Tutorials_Pointer == NULL) { 
printf("Memory not allocated.\n"); 
exit(0); 
} 
else { 
// Confirmation of Memory allocated 
printf("Memory is successfully allocated with the help of calloc funtion.\n"); 
// Getting the elements of the array 
for (i = 0; i < n; ++i) { 
T4Tutorials_Pointer[i] = i + 1; 
} 
// Displaying the elements of the array 
printf("The elements of the array are: "); 
for (i = 0; i < n; ++i) { 
printf("%d, ", T4Tutorials_Pointer[i]); 
} 
} 
return 0; 
}

#include <stdio.h>

#include <stdlib.h>

int main()

{

// This pointer will hold the base address of the block

int* T4Tutorials_Pointer;

int n, i;

// Total elements for the array

n = 5;

printf("Please Enter number of elements: %d\n", n);

// calloc() is used to Dynamically allocate the memory

T4Tutorials_Pointer = (int*)calloc(n, sizeof(int));

// memory successfully allocated or not

if (T4Tutorials_Pointer == NULL) {

printf("Memory not allocated.\n");

exit(0);

}

else {

// Confirmation of Memory allocated

printf("Memory is successfully allocated with the help of calloc funtion.\n");

// Getting the elements of the array

for (i = 0; i < n; ++i) {

T4Tutorials_Pointer[i] = i + 1;

}

// Displaying the elements of the array

printf("The elements of the array are: ");

for (i = 0; i < n; ++i) {

printf("%d, ", T4Tutorials_Pointer[i]);

}

return 0;

}

Noncontiguous memory allocation

Non-contiguous memory allocation means that all the free blocks of memory are not closely neighboured with each other.

How can we prevent memory fragmentation?

Let’s suppose that we are able to isolate exactly those places where we are likely to allocate the big blocks of the memory. In case of Windows, we can do it directly by calling the VirtualAlloc function and we can do it without the memory manager. In this way, we can avoid fragmentation within the normal memory manager.

VirtualAlloc function

Memory can be allocated by VirtualAlloc function. VirtualAlloc function is automatically initialized to zero. If we want to allocate memory in the address space of some another process, then using the VirtualAllocEx function is the best option.
Syntax of VirtualAlloc function

LPVOID VirtualAlloc(
LPVOID lpAddress,
SIZE_T dwSize,
DWORD flAllocationType,
DWORD flProtect
);

LPVOID VirtualAlloc(

LPVOID lpAddress,

SIZE_T dwSize,

DWORD flAllocationType,

DWORD flProtect

);

Frequently Asked Questions (FAQ)

Which of the memory allocation scheme suffers from external fragmentation?
Segmentation is the memory allocation scheme suffers from external fragmentation.
This scheme suffers when all blocks of free memory are too small to handle a segment when free spaces collectively are larger than the given size of the segment. So, we can say that paging suffers when the fragmentation is internal fragmentation and segmentation suffers when the fragmentation is external fragmentation.

Which of the memory management schemes solved internal fragmentation?

Best Fit Block Search is the memory management scheme that can solve the internal fragmentation.

Which of the memory management schemes solved external fragmentation?

Segmentation, paging and Compaction are the memory management schemes that can solved the external fragmentation.

What is 50 percent rule of memory fragmentation?
50 percent rule of memory fragmentation is “For every N blocks allocated, 0.5N blocks are lost only due to fragmentation”.
Unusable memory = (0.5N)/(N+0.5N)= 1/3

What is the best solution to external fragmentation problem?
The best solution to avoid external fragmentation is Paging.

Is external fragmentation possible in contiguous memory allocation?

External fragmentation can occur due to non contiguous memory allocation.

Note: The memory allocation scheme subject to external fragmentation is segmentation.

Why paging has no external fragmentation, and why it may have internal fragmentation?

In paging, a process is allowed to be allocate the memory spaces that are non-contiguous in nature.

The mac os reduces file fragmentation by using…..?

The mac os reduces file fragmentation by using clumps, which are groups of contiguous allocation blocks.

What is time sharing external fragmentation?
Time-sharing system itself causes external fragmentation of memory due to running the processes in a fragmented time quantum(as is Round robin scheduling), rather than in a single unbroken run.
This results in increase of process switching and increase of cache pressure from many processes and results in degraded performance.

Video Lecture

Briefly define memory fragmentation and disk fragmentation. how does os address these two problems?

Author
Recent Posts

Prof. Fazal Rehman Shamil

CEO @ T4Tutorials.com
I welcome to all of you if you want to discuss about any topic. Researchers, teachers and students are allowed to use the content for non commercial offline purpose. Further, You must use the reference of the website, if you want to use the partial content for research purpose.

Latest posts by Prof. Fazal Rehman Shamil (see all)

The Best Tool to Test the Speed of Your Internet - May 5, 2021
Why do we need various number systems in computer science? - April 16, 2021
5 Best Places to Study Engineering - March 19, 2021