Question

In this exercise we “reverse-engineer” some code to try to determine how the heap in a C program is managed. Consider the following C program (compiled as an executable called memory):

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
   int chunk_sizes[4];
   

   if ((argc != 2) || 
       (sscanf(argv[1], "%d,%d,%d,%d", &chunk_sizes[0], &chunk_sizes[1], &chunk_sizes[2], &chunk_sizes[3]) != 4) ||
       (chunk_sizes[0] < 0) || (chunk_sizes[1] < 0) || (chunk_sizes[2] < 0) || (chunk_sizes[3] < 0) ) {
      fprintf(stderr,"Usage: %s a,b,c,d\n", argv[0]);
      fprintf(stderr,"       where a, b, c, and d above must be >=0 integers (chunk sizes)\n");
      exit(1);
   }

   char *ptrs[9];
   unsigned long sizes[9] = {1024, 128, 1024, 128, 1024, 32, 1024, 128, 1024}; 


   for (int i=0; i < 9; i++) {
      ptrs[i] = (char *)calloc(sizes[i], sizeof(char));
      printf("%ld | ", (unsigned long)(ptrs[i]));
   }
   printf("\n--------------\n");

   free(ptrs[0]); free(ptrs[1]); free(ptrs[3]); free(ptrs[5]); free(ptrs[7]);

   for (int i=0; i < 4; i++) {
          if (chunk_sizes[i] > 0) { // If the user specified a 0-size chunk, do nothing
                char *chunk = (char *)calloc(chunk_sizes[i], sizeof(char));
                printf("The %d-byte chunk was allocated at address %ld\n", chunk_sizes[i], (unsigned long)(chunk));
          }
   }
   exit(0);
}

If invoking the program as /memory1100,100,199,20 produces this output: 0 1024 1152| 2176| 2304| 3328 3360 | 4384| 4512 The 1100-byte chunk was allocated at address 52 The 100-byte chunk was allocated at address 4412 The 100-byte chunk was allocated at address 2204 The 20-byte chunk was allocated at address 32 would you say that the heap allocator uses . first fit best fit worst ft none of the above?

Answer 1

Ans:-

(b) Best fit.

• The best-fit deals with allocating the smallest free partition of memory which meets the requirement of the requesting process.
• This algorithm searches for the smallest hole that is enough from the entire list of free partitions.

As per the question

At first, we need to allocate 1100 bytes of memory for which we choose 1024 and 128 consecutive blocks because no single block of ample space is available.

After that, we need to allocate 100-bytes memory for that we have chosen the best fitted 128-byte block, allocated at 4412. and similarly, following the best-fit approach, we also allocated remaining ones.

P.S. - If you find my answer useful, please take a second to give it a THUMBS UP.