Memory allocation – best fit

Memory Allocation – Best Fit


// Best Fit

#include <stdio.h>

#include<conio.h>

int Pr[10];

struct memblock

{

int size;

int alloc;

int PrIndex;

struct memblock *next;

};

struct memblock * CreateHdr()
{

struct memblock * temp = (struct memblock*)malloc(sizeof(struct memblock));

temp->size = 0;

temp->alloc = 0;

temp->PrIndex = -1;

return temp;

}

struct memblock * newNode(int s)

{

struct memblock *temp = (struct memblock*)malloc(sizeof(struct memblock));

temp->size = s;

temp->alloc = 0;

temp->PrIndex = -1;

return temp;

}


void InsertNode(struct memblock* H, struct memblock* N)

{

struct memblock* tmp = H;

while (tmp->next != NULL)

tmp = tmp->next;

tmp->next = N;

}


int Allocate(struct memblock* H, int s, int index)

{

struct memblock* tmp = H;

int newSize;

struct memblock* ptr = NULL;

while (tmp->next != NULL)

{

tmp=tmp->next;

if((tmp->alloc==0) && (s<=tmp->size))

{

ptr = tmp;

break;

}

}

while (tmp->next != NULL)

{

tmp=tmp->next;

if((tmp->alloc==0) && (s<=tmp->size) && (ptr->size>tmp->size))

{

ptr = tmp;

}

}

if(ptr!=NULL)

{

newSize = ptr->size-s;

ptr->size = s;

ptr->alloc = 1;

ptr->PrIndex = index;

if(newSize!=0)

{

struct memblock* t = newNode(newSize);

t->next = ptr->next;

ptr->next=t;

}

return 1;

}

return 0;

}


void printList(struct memblock *m)

{

printf(“\nBlock size \t Process”);

while (m->next != NULL)

{

m = m->next;

if(m->alloc==0)

printf(“\n %d\t\tNot Allocated\n”, m->size);

else

printf(“\n %d\t\tAllocated to Process P%d\n”, m->size,m->PrIndex);

}

}


int main()

{

int Nb, Np;

int i, j;

int blksize;

int ErrCode;

struct memblock *Hdr = CreateHdr();

printf(“\nEnter Number of Memory Blocks : “);

scanf(“%d”,&Nb);

for(i=0;i<Nb;i++)

{

scanf(“%d”,&blksize);

struct memblock *Node = newNode(blksize);

InsertNode(Hdr, Node);

}

printf(“\nEnter number of Process : “);

scanf(“%d”,&Np);

for(i=0;i<Np;i++)

{

printf(“\nEnter size of Process P%d: “,i);

scanf(“%d”,&Pr[i]);

}

printf(“\n\n*** Before Process Memory Allocation ***\n”);

printList(Hdr);

printf(“\n\n*** After Process Memory Allocation ***\n”);

for(i = 0;i<Np;i++)

{

ErrCode = Allocate(Hdr, Pr[i], i);

if(ErrCode==0)

printf(“Insufficient memory. Process P%d (%d KB) has to wait.\n”, i, Pr[i]);

}

printList(Hdr);

return 0;

}


/*

Sample output

Enter Number of Memory Blocks : 6

300

350

200

750

125

Enter number of Process : 5

Enter size of Process P0: 115

Enter size of Process P1: 500

Enter size of Process P2: 358

Enter size of Process P3: 200

Enter size of Process P4: 375

*** Before Process Memory Allocation ***

Block size Process

300     Not Allocated

600     Not Allocated

350     Not Allocated

200     Not Allocated

750     Not Allocated

125     Not Allocated

*** After Process Memory Allocation ***

Block size Process

300     Not Allocated

500     Allocated to Process P1

100     Not Allocated

350     Not Allocated

200     Allocated to Process P3

358     Allocated to Process P2

375     Allocated to Process P4

17       Not Allocated

115     Allocated to Process P0

10       Not Allocated

*/