Thread: Bug in Best-Fit Memory Allocation program (Simulation)

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    7

    Bug in Best-Fit Memory Allocation program (Simulation)

    Hi everybody. I'm trying to simulate memory allocation using a best-fit strategy and I can't get rid of this annoying bug. Can you help me?

    Here is my overall simplified strategy:
    1. Create an array of ones and zeros, where 1=used byte, 0=free byte.
    2. Scan that array for blocks of contiguous zeros (i.e. available memory).
    3. Given a process' required bytes, determine which of the above blocks is the best fit.
    4. Simulate the memory allocation for that process by flipping the array's zeros to ones.


    The problem is that I get a bug when I test it. After the allocation for the first process is done, the subsequent allocations do not go through. The variable "best" stays at 9999 which indicates to me that some variable or array is not getting updated. The problem is that I don't know which one and I've been trying to figure this out for a day now.

    Here is what I have so far. The code is well-commented and should be straight-forward. I left some print statements that I've been using for debugging:
    Code:
    /*
     * File: memory_bf.c
     * Date: 12/Dec/09
     * Author: Rommel Rico
     * Contents: Allocates memory under a Best-Fit Strategy.
     */
    
    #include "binheap.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXMEMORY 10000 //Maximum number of bytes in memory.
    #define INFINITY 99999 //Unreachable number.
    int memoryArrayBF[MAXMEMORY] = {0}; //Used to determine available memory. 0=free byte. 1=used byte.
    int idArrayBF[MAXMEMORY] = {0}; //Stores which processes are in memory and where.
    int memBlocks[100] = {0}; //Stores the size of contiguous available memory.
    int memBlocksID[100] = {0}; //Stores the id of a memory block.
    
    /* Structure defining an Event. */
    struct Event{
      int id; //To store the process id.
      int event_type; //Could be 0 (departure) or 1(arrival).
      int bytes; //Stores the bytes of process.
      double event_time; //Stores the time an event occurs.
      double run_time; //Stores the run time of an event.
    };
    
    
    
    /* Allocate Memory in a Best-Fit fashion. */
    int AllocateMemoryBF(struct Event X){
      //Scan the memoryArray for available blocks of memory.
      int i,j = 0;
      int count = 0;
      for(i=0; i<MAXMEMORY; i++){
        if(memoryArrayBF[i]==0){ //found unused memory.
          count++;
        }
        else if(memoryArrayBF[i]==1 && count>0){ //found allocated memory.
          memBlocks[j]=count;
          memBlocksID[j]=i-(count-1);
          printf("ASSIGNED %d to MEMBlocks[%d].\n", count, j);
          j++;
          count=0; //reset count.
        }
        if(count==MAXMEMORY-1){ //Entire memory is available.
          printf("Entire memory is available.\n");
          printf("ASSIGNED %d to MEMBlocks[0].\n", count);
          memBlocks[0]=count;
          memBlocksID[0]=0;
          count=0; //reset count.
        }
      }
    
      //Scan the memBlocks for the best fit.
      int best = INFINITY;
      int bestID= 0;
      for(i=0;i<100;i++){
        if(memBlocks[i]>=X.bytes && memBlocks[i]<best){
          best=memBlocks[i];
          bestID=i;
        }
      }
      printf("After scanning memBlocks, best fit is: %d.\n", best);
    
      //Allocate the memory.
      if(best==INFINITY){
        printf("NO MEMORY.\n");
        return 1; //No memory available.
      }
      else{
        int place = memBlocksID[bestID];
        printf("ALLOCATED memory in index %d.\n", place);    
        for(i=place; i<(place+X.bytes); i++){
          memoryArrayBF[i] = 1; //allocate memory.
          idArrayBF[i] = X.id;
          printf("WROTE %d to memoryArrayBF[%d] and id=%d.\n", memoryArrayBF[i], i, X.id);
        }
        return 0; //Memory was succesfully allocated.
      }
    }
    
    
    
    /* Deallocate Memory for a Best-Fit fashion. */
    int DeallocateMemoryBF(struct Event X){
      int i=0;
      for(i; i<MAXMEMORY;i++){
        if(idArrayBF[i]==X.id){
          memoryArrayBF[i] = 0; //free the memory.
          idArrayBF[i] = 0; //delete the process id.
        }
      }
      return 0;
    }
    I really appreciate your help. I know its something simple, but I just can't find the bug.

  2. #2
    Registered User
    Join Date
    Mar 2009
    Posts
    48
    Suppose you want X bytes to be allocated(the very first time).When this piece of code is executed
    Code:
    if(count==MAXMEMORY-1){ //Entire memory is available.
          printf("Entire memory is available.\n");
          printf("ASSIGNED %d to MEMBlocks[0].\n", count);
          memBlocks[0]=count;      memBlocksID[0]=0;
          count=0; //reset count.
        }
    memblocks[0] = count = MAXMEMORY - 1 = 99999 = INFINITY
    Next you initialize
    Code:
    int best = INFINITY;
    Code:
    for(i=0;i<100;i++){
        if(memBlocks[i]>=X.bytes && memBlocks[i]<best){
       ... 
       }
    Highlighted code is false for i = 0.'best' is never assigned again in the for loop(as all other values of memblocks[i] = 0).I think the allocation should have been the number of bytes requested although starting from the 0th position.



    EDIT: Adak simultaneous post
    Last edited by zalezog; 12-13-2009 at 04:05 AM.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I can't tell you, but stepping through the variables in this block, should tell you:

    Code:
      //Scan the memBlocks for the best fit.
      int best = INFINITY;
      int bestID= 0;
      for(i=0;i<100;i++){
        if(memBlocks[i]>=X.bytes && memBlocks[i]<best){
          best=memBlocks[i];
          bestID=i;
        }
      }
    I don't understand why you're setting best to infinity, and then testing if a value is less than best!

    It must be less than infinity!

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    7
    Quote Originally Posted by Adak View Post
    I don't understand why you're setting best to infinity, and then testing if a value is less than best!

    It must be less than infinity!
    Because I am trying to find the smallest element in the array. Is there a better way of doing that?

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    7
    Thanks for your help zalezog, but...

    Quote Originally Posted by zalezog View Post
    Suppose you want X bytes to be allocated(the very first time).When this piece of code is executed
    Code:
    if(count==MAXMEMORY-1){ //Entire memory is available.
          printf("Entire memory is available.\n");
          printf("ASSIGNED %d to MEMBlocks[0].\n", count);
          memBlocks[0]=count;
          memBlocksID[0]=0;
          count=0; //reset count.
        }
    memblocks[0] = count = MAXMEMORY - 1 = 99999 = INFINITY
    But memblocks[0] = count = MAXMEMORY - 1 = 10,000 - 1 = 9,999, which is not INFINITY (Infinity has an extra digit).

    Quote Originally Posted by zalezog View Post
    Next you initialize
    Code:
    int best = INFINITY;
    Code:
    for(i=0;i<100;i++){
        if(memBlocks[i]>=X.bytes && memBlocks[i]<best){
       ... 
       }
    Highlighted code is false for i = 0.'best' is never assigned again in the for loop(as all other values of memblocks[i] = 0).I think the allocation should have been the number of bytes requested although starting from the 0th position.
    I don't understand what you mean by this.
    I'll try to clarify what I'm trying to do with an example:
    I have 3 processes.
    Process 1: needs 12 bytes; Process 2: needs 8 bytes; Process 3: needs 11 bytes.
    At the beginning, everything is empty. That means that everything is initialized to '0'.
    Process 1 requires its memory to be allocated. I scan the entire array(of 10,000 elements) and find that everything is just zero. So I assign 9,999 to memBlocks[0]. I then insert 12 ones at the beginning of the memoryArrayBF. Up to this point, everything works fine.
    Then Process 2 comes along. I scan the array and should find that there is now one contiguous block of 9,987 zeros, since the first process was allocated at the beginning. I should assign the process there. Similar logic applies to process 3.


    ----------------------
    UPDATE:
    Never mind people. I found the mistake. It's amazing what a good night sleep does for your brain. Anyway, I truly appreciate your help. The mistake was in this part:
    Code:
    if(count==MAXMEMORY-1){ //Entire memory is available.
          printf("Entire memory is available.\n");
          printf("ASSIGNED %d to MEMBlocks[0].\n", count);
          memBlocks[0]=count;
          memBlocksID[0]=0;
          count=0; //reset count.
        }
    I simply replaced count for i in that if statement and it worked (plus some other minor modifications throughout the code). I think you can tell why.
    Last edited by RommelTJ; 12-13-2009 at 10:47 AM. Reason: Found the mistake

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Had to double check my allocation (rand) loop. Looks like it was right after all:
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXMEM 1000
    #define NOMEM -1
    #define FREEMEM 0
    #define MAXPROC 50
    
    int memory[ MAXMEM ];
    
    int alloc( size_t bytes )
    {
        int x = 0;
        
        while( 1 )
        {
            if( x < MAXMEM )
            {
                if( memory[ x ] == FREEMEM
                &&  x + bytes < MAXMEM
                && memory[ x + bytes ] == FREEMEM )
                {
                    int y = 0;
                    for( y = x; y < x + bytes; y++ )
                        if( memory[ y ] != FREEMEM )
                        {
                            break;
                        }
                    if( y == x + bytes )
                    {
                        for( y = x; y < x + bytes; y++ )
                            memory[ y ] = bytes; /* put something to show allocated */
                        return x;
                    }
                }
                x++;
            }
            else
                break;
        }
    
        return NOMEM;
    }
    
    void showmem( int block )
    {
        int x = 0;
        while( block + x < MAXMEM && memory[ block ] == memory[ block + x ] )
            printf( "%2d ", memory[ block + x++ ] );
        printf( "\n" );
    }
    
    int main( void )
    {
        int processes[ MAXPROC ] = {0};
        int x = 0, y = 0;
    
        for( x = 0; x < MAXPROC; x++ )
        {
            int a = alloc( 15 + (rand()%20) );
            if( a != NOMEM )
            {
                processes[ x ] = a;
                printf( "%2d b for p %2d: ", memory[ processes[ x ] ], x );
                showmem( processes[ x ] );
                y += memory[ processes[ x ] ];
            }
        }
        printf("total allocation: %d\n", y );
    
        return 0;
    }
    I don't have a 'free' in there, but it looks like it's working right. Notice I'm being lazy here with tabulation. I'm not marking the processes that failed as failed, they're just staying at zero. (Which means if you ran through looking at 'memory[ processes[ x ] ]', your tally ends up off, but that's not alloc's fault, that's just me being lazy with summation.)


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by RommelTJ View Post
    Because I am trying to find the smallest element in the array. Is there a better way of doing that?
    Yes.

    Say you had to select the smallest apple from a bowl of apples. Would you pick up the first apple and ask yourself:

    "Is this apple smaller than the universe?"

    Of course not.

    You'd look at that apple with your "good eye measuring stick", and then pick up the next apple and examine it, and so on for each apple.

    which looks like this, in code:

    Code:
    int minimum, i;
    
    for(i = 0, minimum = array[0]; i < arraySize; i++)  {
      if(array[i] < minimum)
        minimum = array[i];
    }
    
    printf("The smallest value in the array is: %d", minimum);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help! -Linked Lists, Memory Allocation, Time Steps, Debugg
    By MetallicaX in forum C Programming
    Replies: 2
    Last Post: 03-14-2009, 08:50 PM
  2. Program crashes and memory leaks
    By ulillillia in forum Tech Board
    Replies: 1
    Last Post: 05-15-2007, 10:54 PM
  3. Relate memory allocation in struct->variable
    By Niara in forum C Programming
    Replies: 4
    Last Post: 03-23-2007, 03:06 PM
  4. Program that displays amount of free memory
    By trancedeejay in forum Linux Programming
    Replies: 3
    Last Post: 01-13-2006, 01:27 PM
  5. Is it necessary to write a specific memory manager ?
    By Morglum in forum Game Programming
    Replies: 18
    Last Post: 07-01-2002, 01:41 PM