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
*/