IMPLEMENTATION OF MEMORY ALLOCATION ALGORITHMS

PROGRAM CODING:-
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


struct list
{
int start,end;
char *pid;
int fragment;
int framenum;
struct list *next;
};


struct process
{
char pname[2];
int size;
}*proc;


int nopro,nop;


void read(struct list*header)
{
int i;
printf("\n Enter the following details:-");
printf("\n Enter number of partitions:-");
scanf("%d",&nop);
struct list *p,*node;
p=header;
for(i=0;i<nop;i++)
{
node=(struct list*)malloc(sizeof(struct list));
printf("\n Enter starting address:-");
scanf("%d",&node->start);
printf("\n Enter ending address:-");
scanf("%d",&node->end);
node->pid=NULL;
node->next=NULL;
node->framenum=i+1;
p->next=node;
p=node;
}
printf(" Enter number of processes:-");
scanf("%d",&nopro);
proc=(struct process*)malloc(nopro*sizeof(struct process));
for(i=0;i<nopro;i++)
{
printf("\n Enter process name:-");
scanf("%s",&proc[i].pname);
printf("\n Enter size of process:-");
scanf("%d",&proc[i].size);
}
}




void insert(struct list *freelist,struct list *allocate,int i)
{
struct list *n,*m,*t,*a;
t=freelist;
int fragment,num;
n=allocate;
while(n->next!=NULL)
{
n=n->next;
if(n->next==NULL)
break;
if((n->framenum<=t->next->framenum)&&(n->next->framenum>t->next->framenum))
break;
}
num=t->next->framenum;
fragment=(t->next->end-t->next->start)-proc[i].size+1;
if(fragment!=0)
{
m=(struct list*)malloc(sizeof(struct list));
m->start=t->next->end-fragment+1;
m->end=t->next->end;
m->pid=NULL;
m->fragment=0;
m->framenum=num;
a=n->next;
n->next=t->next;
t->next=m;
m->next=n->next->next;
n->next->next=a;
n->next->pid=proc[i].pname;
n->next->framenum=num;
n->next->end-=fragment;
n->next->fragment=fragment;
}
}




void firstfit(struct list *freelist,struct list *allocate)
{
struct list *t;
int size,i;
for(i=0;i<nopro;i++)
{
t=freelist;
while(t->next!=NULL)
{
size=t->next->end-t->next->start+1;
if(size<proc[i].size)
{
t=t->next;
}
else
{
insert(t,allocate,i);
break;
}
}
}
}




void bestfit(struct list *freelist,struct list *allocate)
{
struct list *t,*need;
int size,i=0,j=0;
t=freelist;
for(i=0;i<nopro;i++)
{
t=freelist;
int small=999;
while(t->next!=NULL)
{
size=(t->next->end)-(t->next->start)+1;
if(size<proc[i].size)
t=t->next;
else if((size-(proc[i].size))<small)
{
small=size-(proc[i].size);
need=t;
t=t->next;
}
else if(t->next==NULL && small==999)
printf("\nProcess %s cant be allocated due to large size!**!",proc[i].pname);

else
t=t->next;
}
if(small!=999)
{
insert(need,allocate,i);
}
}
}






void worstfit(struct list *freelist,struct list *allocate)
{
struct list *t,*need;
int size,i=0,j;
for(i=0;i<nopro;i++)
{
t=freelist;
int small=-999;
while(t->next!=NULL)
{
size=(t->next->end)-(t->next->start)+1;
if(size<proc[i].size)
t=t->next;
else if((size-(proc[i].size))>small)
{
small=size-(proc[i].size);
need=t;
t=t->next;
}
else if(t->next==NULL && small==-999)
printf("\nProcess %s cant be allocated due to large size!**!",proc[i].pname);
else
t=t->next;
}
if(small!=-999)
insert(need,allocate,i);
}
}



void completion(struct list *freelist,struct list *allocate,char *proname)
{
int d=0;
struct list *del=allocate,*l;
struct list *add=freelist;
while(del->next!=NULL)
{
if(strcmp(del->next->pid,proname)==0)
{
while(add->next!=NULL)
{
if(add->next==NULL)
break;
if(add->next->framenum<=del->next->framenum && add->next->next->framenum>del->next->framenum)
break;
add=add->next;
}
l=add->next;
add->next=del->next;
del->next=del->next->next;
add->next->next=l;
add->next->pid=NULL;
add->next->fragment=0;
break;
}
else
{
del=del->next;
}
}
}






int compaction(struct list *freelist,int d)
{
int c=0,b=0;
struct list *n,*t;
struct list *p=freelist->next;
while(p!=NULL)
{
t=p;
n=p;
while(t->next!=NULL)
{
t=t->next;
if(p->framenum==t->framenum)
{
p->end=t->end;
n->next=t->next;
c=1;
}
else
break;
n=n->next;
}
p=p->next;
}
if(c!=1 && d==1)
{
printf("\n\nCOMPACTION NOT POSSIBLE!**!");
b=1;
}
return b;
}




void deleteall(struct list *freelist,struct list *allocate)
{
int i;
for(i=0;i<nopro;i++)
{
completion(freelist,allocate,proc[i].pname);
}
}





void display(struct list *freelist,struct list *allocate)
{
struct list *t=freelist;
struct list *a=allocate;
if(t->next==NULL)
printf("\n ALL PROCESSES ALLOCATED WITH MEMORY!**!");
else
{
printf("\n\n=================\n\n");
printf("|FREE MEMORY|\n");
printf("\n===================\n\n");
printf("starting address\t\tPID\t\tEnding address\t\tFragment\n\n");
while(t->next!=NULL)
{
t=t->next;
printf("%d\t\t        %s\t\t%d\t\t    %d\t\t     \n",t->start,t->pid,t->end,t->fragment);
}}
if(a->next==NULL)
printf("\nNO PROCESS HAS BEEN ALLOCATED WITH MEMORY!**!\n");

else
{
printf("\n\n========================\n");
printf("|ALLOCATED MEMORY|\n");
printf("\n=========================\n");
printf("starting address\tPID\tEnding address\tFragment\n\n");
while(a->next!=NULL)
{
a=a->next;
printf("%d\t\t        %s\t\t%d\t\t    %d\t\t     \n",a->start,a->pid,a->end,a->fragment);
}
}
}




int main()
{
int i=0,op=0,ch=0,b,c=0;
char proname[2];
struct list *free;
free=(struct list*)malloc(sizeof(struct list));
free->next=NULL;
struct list *alloc;
alloc=(struct list*)malloc(sizeof(struct list));
alloc->next=NULL;
while(op!=3)
{
printf("\n\n========================================");
printf("\nMEMORY ALLOCATION STRATEGIES");
printf("\n\n========================================");
printf("\n1. READ_INPUT\n2. ALLOCATION STRATEGIES\n3. EXIT");
printf("\n\tEnter your option:--");
scanf("%d",&op);
switch(op)
{
{
case 1:
read(free);
printf("\nBEFORE ALLOCATION");
display(free,alloc);
break;
}
{
case 2:
while(ch!=7)
{
printf("\n\nMENU:-\n1. First Fit\n2. Best Fit\n3. Worst Fit\n4. Deletion\n5. Compaction\n6. Display\n7. Exit");
printf("\n\t Enter your option:-");
scanf("%d",&ch);
switch(ch)
{
  case 1:
        deleteall(free,alloc);
if(c!=0)
compaction(free,1);
printf("\nBEFORE ALLOCATION");
display(free,alloc);
firstfit(free,alloc);
printf("\nAFTER ALLOCATION");
display(free,alloc);
break;


case 2:
deleteall(free,alloc);
if(c!=0)
compaction(free,1);
printf("\nBEFORE ALLOCATION");
display(free,alloc);
bestfit(free,alloc);
printf("\nAFTER ALLOCATION");
display(free,alloc);
break;

case 3:
deleteall(free,alloc);
if(c!=0)
compaction(free,1);
printf("\nBEFORE ALLOCATION");
display(free,alloc);
worstfit(free,alloc);
printf("\nAFTER ALLOCATION");
display(free,alloc);
break;


case 4:
printf("\n\nBefore completion of process:");
display(free,alloc);
printf("\nEnter PID of process that has completed its job:-");
scanf("%s",proname);
completion(free,alloc,proname);
printf("\nAfter completion of process:-");
display(free,alloc);
printf("\n\nREMOVED SUCCESSFULLY!**!");
break;

case 5:
printf("\n\nBEFORE COMPACTION");
display(free,alloc);
b=compaction(free,1);
if(b==0)
{
printf("\n\nAFTER COMPACTION");
display(free,alloc);
}
break;


case 6:
printf("\n\nPresent allocation of process!!!!");
display(free,alloc);
break;

case 7:
break;
}
c++;
}
break;
}
{
case 3:
printf("\n\n================\n");
printf("|MANAGED|");
printf("\n==================\n\n");
exit(0);
}}}
return 0;}