Memory Allocation Methods: An Overview

0
937
memory allocation

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.  

0 1023
Address 0 250 550 700 900 950-1023
Allocation
details
Block 1 allocated Free 1 Block 2 allocated Free 2 Block 3 allocated Free 3
  Size = 250 Size = 300 Size = 150 Size = 200 Size =
50
Size =
73

 

Note: In this blog we will only consider the First Fit algorithm, though each of these methods has its own use cases. Generally speaking, preference is given to the First Fit.


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.

0 023
Address 0 250 350 550 700 900 950 – 1023
Allocation
details
Block 1 allocated Free 1 Block 2 allocated Block 3
allocated
Free 2 Block 4
allocated
Free 3
  Size = 250 Size = 100 (new) Size = 200 Size= 150 Size = 200 Size = 50 Size =
73

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:

0 1023
Address 0 250 550 700 900 950 – 1023
Allocation
details
Block 1 allocated Free 1 Block 2
allocated
Block 3
allocated
Block 4
allocated
Free 2
  Size = 250 Size = 300 Size= 150 (new)Size = 200 Size = 50 Size =
73

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.

0 1023
Address 0 250 350 550 700 900 950-1023
Allocation
details
Block 1 allocated Free 1 Block 2
allocated
Block 3
allocated
Free 2 Block 4 allocated Free 3
  Size = 250 Size = 100 Size= 200 (new) Size = 150 Size = 50 Size = 50 Size = 73

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.

Request Blocks remaining using
First Fit Best Fit Worst Fit
Initially 110, 54 110, 54 110, 54
25 85, 54 110, 54 85, 54
70 15, 54 40, 29 15, 54
50 15, 4 Cannot be fulfilled 15. 4
14 1, 4 1, 4
1 0, 4 1, 3
2 0, 2 Cannot be fulfilled


Best Fit as best case

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

Request Blocks remaining using
First Fit Best Fit Worst Fit
Initially 110, 54 110, 54 110, 54
50 60, 54 110, 4 60, 54
100 Cannot be fulfilled 10, 4 Cannot be fulfilled

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

Request Blocks remaining using
First Fit Best Fit Worst Fit
Initially 200, 300, 100 200, 300, 100 200, 300, 100
150 50, 300, 100 50, 300, 100 200, 150, 100
100 50, 200, 100 50, 300, 0 100, 150, 100
125 50, 75, 100 50, 175, 0 100, 50, 100
100 50, 75, 0 50, 75, 0 0, 50, 100
100 Cannot be fulfilled Cannot be fulfilled 0, 50, 0

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here