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:

Create an array of ones and zeros, where 1=used byte, 0=free byte.
Scan that array for blocks of contiguous zeros (i.e. available memory).
Given a process' required bytes, determine which of the above blocks is the best fit.
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.

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

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!

Quote:

Originally Posted by Adak

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?

Thanks for your help zalezog, but...

Quote:

Originally Posted by zalezog

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

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.

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.

Quote:

Originally Posted by RommelTJ

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);