In this article, we will be going through a few strategies which Operating Systems use to fit processes into the main memory during execution. This include First, Best and Worst fit Strategies.

Table of contents:

1. An Overview to Memory Allocation
2. Contiguous Memory Allocation
3. How do we allocate memory for a Process?
   • First fit
   • Best fit
   • Worst Fit
4. Further talking points

An Overview to Memory Allocation:

While executing, every program in a computer has to give certain instructions to the CPU and supply/store vital data. The necessary instructions of the program that needs to be run are stored in the Main Memory for immediate access to the CPU. This set of executing instructions are collectively called a Process.

Our goal would be to maximize the Memory Utilization by trying to fit as many processes as possible at a time. There are various Memory Management Techniques we can put to use. We'll focus on one such technique: Contiguous Memory Allocation, more specifically, Variable (or) Dynamic Partitioning Strategies.

Contiguous Memory Allocation:

Contiguous memory Allocation allocates partitions of the Main Memory for each process. This partition is contiguous to the partition of the next given process.

It's analogous to stacking books one after another in a shelf, here the shelf represents the Main Memory and each book signifies a process.

We could use Fixed Partition Allocation (for example, each partition is 16MB irrespective of the process size)
(or)
Variable Partition Allocation (each process occupies a partition of the Main Memory equal to it's size)

How do we allocate memory for a Process?

Processes enter the main memory and stay till they get completely executed.
Once a process exits, previously occupied memory is freed creating free spaces in the memory. These spaces of unallocated memory are termed Holes.

In a Variable Partition Allocation we use three strategies to allocate memory:

• First fit

An incoming process gets allocated into a Hole of size greater than or equal to it. Searching for Holes can start from the beginning of the memory or from where the previous first fit search ended.

Sample Code

int mem_arr[7] = {0, 10, 0, 8, 0, 0, 15}; 
// Sample Main Memory Array.
// 0s represent occupied Partitions.
// A non-zero Integer 'n' represents a Hole of size 'n'.

mem_arr is a sample array to represent the Main Memory.

// First fit

int first_fit_holder = 0;
for (int i = 0; i < 7; i++)
{
    if (mem_arr[i] >= incom_process_size)
        {
            first_fit_holder = mem_arr[i];
            break;
        }
}

We traverse through the memory array to find the first Hole able to accomodate the incoming process. Traversing the memory is stopped once we acquire the First fit hole.

Speed and Simplicity are the perks of this strategy. However, it's not the most optimal in terms of the size of memory allocated.

• Best fit

We find the least sized Hole capable of holding the incoming process. This generates the smallest left over Holes.

Sample Code

// Best fit

int best_fit_holder = 0;
for (int i = 0; i < 7; i++)
{
    if (mem_arr[i] >= incom_process_size && mem_arr[i] <= best_fit_holder)
        best_fit_holder = mem_arr[i];
    else if (best_fit_holder == 0 && mem_arr[i] >= incom_process_size)
        best_fit_holder = mem_arr[i]; 
}

We traverse the array while storing the smallest suitable Hole value we come accross in the best_fit_holder variable. The entire Memory array has to be traversed to obtain the Best fit Hole.

This is the most optimal strategy based on Memory Utilization. This strategy is slower than the Best fit method.

• Worst Fit

We find the largest Hole and allocate the incoming process to it.

Sample Code

int worst_fit_holder = 0;

for (int i = 0; i < 7; i++)
{
    if (mem_arr[i] >= incom_process_size && mem_arr[i] >= worst_fit_holder)
        worst_fit_holder = mem_arr[i];
    else if (worst_fit_holder == 0 && mem_arr[i] >= incom_process_size)
        worst_fit_holder = mem_arr[i]; 
}

We traverse the array while storing the largest suitable Hole value we come accross in the worst_fit_holder variable. Similar to the Best fit strategy, the entire Memory array has to be traversed to obtain the Worst fit Hole.

As the name might suggest, its cons are plenty. First, the time taken to implement Worst fit is higher than that of First fit and Best fit strategies. Second, it's the least efficient strategy based on Memory Utilization.

Further talking points

Processes get allocated and executed leaving Holes which are often Non-Contiguous. Two Non-Contiguous Holes might not be able to fit a process whereas had the two Holes been Contiguous, another process could've been allocated a partition. This phenomenon is termed External Fragmentation. The First fit and Best fit Strategies are usually succeptible to external fragmentation. Non-Contiguous Allocation is a solution to External Fragmentation.

Having gone through this article at OpenGenus, you're bound to have a solid grasp of Memory Allocation Strategies:(First, Best and Worst fit Strategies)!