Fragmentation in Operating System

Prerequisites

To understand this topic, you should have some knowledge of the following Operating System topics:

• Page Replacement in OS
• Multi-processor Scheduling
• Priority Scheduling Algorithm

How Does a Program Get Loaded into the Main Memory?

The text/code file that we have on our hard disk is called a program. This is given to a compiler that compiles it and converts it to an object file that can be executed by the computer. Once the compiler generates object code then it is given to the linker.

The linker is a program that scans the object file and links all the libraries or files that are needed to be linked for the execution of the object file. Once the linker links all the files and the libraries, then an executable file is generated. This is then given to the loader.

Loader is a program that takes the object file from the linker loads it into the main memory and prepares it for execution. The loader loads the object file into the main memory. Once the object file is loaded into the main memory then it is called a process.

The diagram below shows the process of loading a program into the main memory.

A process in the main memory will not need CPU all the time because a process may also use output devices such as a printer or monitor or it might need to write/read from the disk. During this time the CPU will sit idle. This means that we are underutilizing the CPU which is not desirable.

Hence to fully utilize the CPU capacity we load multiple programs into the main memory and we manage the process(once a program gets loaded into the main memory we call it a process) in such a way that the CPU is never idle. Increasing the number of processes in the main memory is good for CPU utilization but we cannot load all the programs in the main memory as there is a limitation to the size of the main memory. Since main memory is very expensive, we cannot have a very large main memory, hence there is a need for memory management.

To do all this we need to efficiently use the memory as well as manage the processes which are executing in the main memory. This type of system is called a multiprogramming operating system where we have multiple programs running in the main memory. Processes are managed by the process manager who is responsible for the creation, scheduling, and termination of a process.

The memory management unit is responsible for allocating and managing the main memory of the computer. It manages the memory in such a way that more programs can be loaded into the main memory. Memory management will itself need a separate blog, hence here I will discuss just memory partitioning, fixed and dynamic to be specific as these need to be clear before getting into fragmentation in OS.

What is Memory Partitioning?

This is the technique of memory management where the main memory is divided into various partitions/blocks so that many processes can be present in the memory simultaneously. There are mainly two types of partitioning.

• Fixed Partitioning
• Dynamic Partitioning

Fixed Partitioning

In the Fixed Partitioning, the main memory is divided into fixed-sized partitions/blocks. The partitions/blocks can be of the same size or different sizes. The size of the partition/block is decided before the process arrives in the main memory. The diagram below shows how the main memory is partitioned using fixed partitioning.

In the diagram above you can see that we have 4 blocks of fixed size.

Now since the number of partitions/blocks is fixed, the number of processes that can reside in the main memory is also fixed and at max, it can be equal to the number of partitions/blocks. Hence the degree of multiprogramming in fixed partitioning is limited to the number of partitions/blocks in the main memory.

Dynamic Partitioning

In Dynamic Partitioning, the main memory is not divided initially. When a process arrives in the main memory it is given that much memory. Here the partition/block size is not fixed initially, instead, the size of partition/block size is equal to the size of the process. This is shown in the diagram below.

In the diagram, you can see that we loaded the process in the order they arrived as long as we have contiguous memory available in RAM. In the above diagram, the RAM size is 28MB and you will notice that we don’t have pre-defined partitions/blocks as we had in the fixed partitioning method.

Here since the partition size is not fixed therefore there is no limitation on the number of processes that can be present in the main memory simultaneously. Hence here the degree of multiprogramming is very high compared to fixed partitioning and is limited only by the size of the main memory itself.

Contiguous Memory Allocation:

An important point to note here is that we do contiguous allocation of memory in both fixed as well dynamic partitioning. Contiguous allocation of memory means when a process is given a continuous section/part of memory in the main memory. This will be clear by the following example:

In the above diagram we have taken the case of fixed partitioning for an explanation, We can see that we have 4 partitions/blocks b1,b2,b3, and b4 in the main memory of size 4MB, 4MB, 2MB, and 2MB respectively. Now if a process p1 arrives with a size of 3MB it will be loaded into partition/block b1. If p2 arrives of size 4MB it will be loaded in partition/block b2.

Now if p3 arrives of size 3MB, then it cannot be loaded because there is no partition/block where we can load p3 in a continuous section of memory. Here you can see that p1 and p2 could be loaded as we have continuous memory available whose size was greater than or equal to the process size but p3 could not be loaded even though we had sufficient memory. The reason is the non-availability of a continuous memory section of size equal to the process size p3.

What is Fragmentation in OS?

Processes get loaded into the RAM for execution and get removed after execution or when preempted. RAM is divided into memory blocks using two methods, The first one is fixed partitioning(the size is fixed before the process arrives) and the other is dynamic partitioning(the size is decided by the size of the process). In contiguous memory allocation, this loading and unloading of processes causes many fragments of the memory that can’t be allotted to the incoming new process. This condition is called fragmentation in OS. In this blog, we will see various types of fragmentation and the solution for that.

Fragmentation in OS is of the following types:-

1. Internal Fragmentation
2. External Fragmentation
3. Data Fragmentation

Internal Fragmentation in OS

This is a condition where a process is allocated to a memory block that is greater in size compared to the process. Hence the memory left in that block is unused and gets wasted.

Example: Suppose we have a RAM of size 16 MB and this is divided into memory partitions/blocks b1,b2,b3, and b4 of size 2MB, 4MB, 8MB, and 2MB respectively. Now suppose 4 processes p1,p2,p3, and p4 arrive of size 1MB, 4MB, 1MB, and 4MB. Here we will assume that the manager will assign processes to the memory blocks using the best fit method. Then p1 will be assigned to partition/block b1, p2 will be assigned to b2, p3 will be assigned to b4 and p4 will be assigned to b3. Hence after allocation, the RAM will look as given below.

The point worth noting here is that the degree of multiprogramming is limited to the number of memory blocks as the number of processes that are present in the main memory is equal to the number of memory blocks in the main memory.

Hence the degree of multiprogramming is limited by the number of memory blocks/partitions.

How to Handle Internal Fragmentation in OS?

In the diagram above we can clearly see that we have 6MB of RAM available. Now if a process of size 6MB arrives we cannot load it into the RAM. The reason behind this is the contiguous memory allocation that is used to load the process. Here we can clearly see that a process is assigned a block of size greater than its size, hence memory gets wasted and cannot be used by another process. This is called internal fragmentation in OS.

Here we don’t have any predefined partitions. We allot memory to the process according to their size as long as we have free contiguous memory available.

External Fragmentation in OS

This is a condition where we have enough memory for the incoming process but that memory is not contiguous and hence cannot be allotted to the process. Hence the unused memory gets wasted. This causes external fragmentation.

Example: Suppose we have a RAM of size 16MB and 4 processes p1,p2,p3, and p4 with size 2MB,4MB,4MB, and 6MB respectively. Since we don’t have any partitions we will allocate memory to the processes in a contiguous manner. After allocation, the RAM will look as in diagram 1.

Now after that process p1 and p3 get pulled out from the RAM after they finish execution. The RAM will look as in diagram 2.

You can clearly see that we have two holes created of size 2MB and 4MB. Now if a process of size 6MB comes that will not be loaded into RAM because we don’t have contiguous memory of size 6MB available although we have 6MB free in RAM. This is external fragmentation in OS.

How to Remove External Fragmentation?

External fragmentation is occurring because we are doing contiguous memory allocation above. If somehow we can divide the process of 6MB into three parts of size 2MB each then the first part will be loaded into the hole of size 2MB and the remaining two parts will be loaded in the hole with size 4MB.

The other approach can be to combine the two holes of size 2MB and 4MB together to have a single hole of size 6MB. Now, this process can easily be loaded into the RAM.

These two approaches are mentioned below:

• Paging:

  Now if p1 and p3 get pulled out of RAM after finishing their execution and a process of size 6MB arrives then it will be divided into 3 parts and each part will be loaded into three available holes. Hence this solves external fragmentation. This is shown in the diagram below:

In this, we don’t allocate memory in a contiguous manner. Here we fix a small unit in which the RAM, as well as a process, will be divided. Here we will have a unit of size 2MB, one can choose a unit of any size. We divide the process into small parts of equal sizes and load it into the available memory in the RAM.

Here we will divide each process p1, p2, p3, and p4 into parts of size 2MB each and then we will load it into RAM. Therefore p1, p2, p3, and p4 will be divided into one, two, two, and three parts of size 2MB each respectively. Then this will be loaded into RAM.

• Segmentation:

  This is similar to paging, the only difference is that the size of blocks/parts in which the process will be divided is not the same. Hence not explaining separately.

• Compaction/Defragmentation:

  In this, we pull out all the processes and then again load the process. In this manner, all the available memory gets in one place. This is a simple technique but if the RAM size is large then it takes a lot of time as pulling out all the processes and then again loading will take time. This is shown in the diagram below:

Data Fragmentation

In a file system, when the file system is newly created then we have a lot of contiguous memory available. Then in that case writing and reading data is very fast. As time passes some files get deleted and some files get written. This causes a lot of holes/empty memory in the file system.

Now when a new file needs to be written it gets written at multiple holes so that the available memory gets used. This increases the seek time and rotational latency of the read/write head. This is called data fragmentation.

Example: Suppose we have an empty disk and four files f1,f2,f3, and f4 are to be stored in, sizes 2MB,4MB,4MB, and 6MB. After storing we delete files f1 and f3. No, if a file f5 comes with a size 6MB then we will have to store it in two parts. This increases the write time of the read/write head as it has to write at two different locations. This will take more time as the read/write head will have to travel longer in order to write the file. This problem is called data fragmentation. This is shown in the diagram below:

How to Remove Data Fragmentation in OS?

There are various ways but the most common is compaction/defragmentation. In this, the blocks are rearranged in such a way that the blocks of each file are contiguous. This reduces read/write time. The diagram below will show disks before compaction and after compaction.

This is all about fragmentation in the operating system. I hope you liked this blog.