Memory Allocation Methods: An Overview

Dynamic memory management requires regular memory allocation and space clearance. This article lists a few methods that can be used for memory allocation.

Calling the malloc (memory allocation) or free function results in a reference to the allocated memory address, or it frees memory back for others to use each time it is called. Dynamic memory management necessitates regular memory allocation and space clearance.

What should be done with the space that has been freed up as well as with the space that has been used? How do we figure out which addresses/slots to utilise for the next malloc call? There are three approaches for managing memory that we can use to solve these questions, which we shall discuss in detail.

The table below illustrates the current state of one large memory block of 1024 bytes. We will see how each method uses it for the allocation of memory.  

First Fit
In the First Fit method, the free list is traversed sequentially to find the first free block that can hold the requested size.

Once the block is found, one of the two operations given below is performed:

• If the size is equal to the requested amount, it is removed from the free list.
• Else it is split into two parts. Here, the first portion remains on the list and the second is allocated.

The reason for allocating the second part is that the operation of updating the list may be avoided by just making a change in the size of the free node.

Let’s now try to allocate 200 bytes and understand how the structure changes.

As can be seen, the memory is allocated in the second section with the prior block pointing to the first part. If the first portion was used, the change would have had to be made in the list by pointing to the second section.

Now, let’s examine the algorithm:

p = freeblock;
alloc = null;  // pointer to store the allocated size n’s address
q = null;

// find the free node which can allocate the given size n
while ( p != null && size(p) < n) {
    q = p;   // previous node
    p = next(p);
}

// if there is block large enough found
if ( p != null ) {
    s = size(p);
    alloc = p + s – n; // alloc contains the address of the desired block

    // if the block size matches the requested size, remove the block from the free list
    if ( s == n) {
         
         // if the match is found in the first block update the pointer of freeblock to point the next of free block
         if ( q == null ) {
               freeblock = next(p);
         } else {
              next(q) = next(p);
        }
    } else {
       size(p) = s – n;  // adjust the size of the remaining free block
   }
}

Best Fit
The smallest of the free blocks, whose size is more than or equal to the specified size ‘n’, is chosen in the Best Fit approach. To discover the best match, this algorithm must run through the full list.

Let’s now try to allocate 200 bytes and note the changes in the structure:

The memory Free 1 was ignored, and Free 2 was updated to Block 3. Free 1 is now pointing to Free 3 (since changed to Free 2). As the requested size matches the allocated size, it is removed from the free pointer list.

Worst Fit
The algorithm in the Worst Fit technique always allocates a portion of the largest free memory block. The idea behind this strategy is that by continuously employing a small number of very large blocks to serve the majority of requests, many of the smaller blocks will remain unfragmented.

Let’s now try to allocate 200, and see how the structure gets changed.

As Free 1 holds the maximum of 300 bytes, the memory is allocated there. If we try to allocate 100, though we have the first free size with 100 bytes, it will still be allocated to Free 2, which is the maximum now.

Each method has its own advantages. Let’s understand that with examples.

First Fit as best case
In the scenario given below, only First Fit is able to serve all the requests.

Best Fit as best case
In the scenario given below, only Best Fit is able to serve all the requests.

Worst Fit as best case
Only Worst Fit is able to serve all the requests in the instances given below.

As mentioned earlier, each method has its uses though, generally, the First Fit method is preferred.