AIM:
To write a C program to implement first fit algorithm for memory management.
ALGORITHM:
Step 1: Start the program.
Step 2: Get the number of blocks.
Step 3: Get the number of jobs.
Step 4: Compare the blocks with each job.
Step 5: If first block is great enough to place the job then place the job in it, otherwise compare the next blocks.
Step 6: Display the result.
Step 7: Stop the program.
PROGRAM:
#include
#include
typedef struct freelist
{
int start;
int end;
struct freelist *next;
} FreeList;
typedef struct alloclist
{
int pid;
int start;
int end;
struct alloclist *next;
} AllocList;
void allocatememory(int pid, int progsize);
void insertinAlloclist( AllocList *p2);
void insertinFreelist( FreeList *p2);
void freememory( int pid );
void updatefreelist(FreeList *p1, FreeList* p2, int progsize);
void dispfreelist( );
void dispalloclist( );
FreeList *freelist=0;
AllocList *alloclist=0;
int main()
{
int ch=0,pid=0,progsize=0;
char s[10];
// create free list
freelist = (FreeList*) malloc(sizeof(FreeList));
freelist->start=1;
freelist->end=100;
freelist->next=0;
while(1)
{
system("cls");
printf("\n\n-----------------------------\n");
printf("Memory Management First Fit\n");
printf("-----------------------------\n");
printf("1. Allocate memory\n");
printf("2. Free memory\n");
printf("3. Display status\n");
printf("4. Exit\n\n");
printf("Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1 : system("cls");
printf("\n\nAllocate Memory: \nEnter pid : ");
scanf("%d",&pid);
printf("Enter size of memory : ");
scanf("%d",&progsize);
allocatememory(pid,progsize);
dispalloclist( );
dispfreelist();
printf("\nPress any key & ENTER to continue : ");
scanf("%s",s);
break;
case 2 : system("cls");
printf("\n\nFreeing Memory: \nEnter pid : ");
scanf("%d",&pid);
freememory(pid);
dispalloclist( );
dispfreelist();
printf("\nPress any key & ENTER to continue : ");
scanf("%s",s);
break;
case 3 : system("cls");
printf("\nMemory Allocation Status\n");
dispalloclist( );
dispfreelist();
printf("\nPress any key & ENTER to continue : ");
scanf("%s",s);
break;
case 4 : printf("\n");
exit(0);
default : printf("Incorrect choice.\n\n");
break;
}
}
}
void allocatememory(int pid, int progsize)
{
FreeList *fp,*prev;
AllocList *ap;
int holesize;
if( freelist == 0 )
{ printf("\nMemory not available\n");
return;
}
fp = freelist;
prev=fp;
holesize = fp->end - fp->start +1 ; // size of first hole
while(1)
{
if( holesize < progsize)
{
if( fp->next == 0 ) // last node
{ printf("\nMemory not available\n");
return;
}
else // go to next holesize
{ prev = fp;
fp = fp->next;
holesize = fp->end - fp->start +1 ;
continue;
}
}
else // allocate memory
{
ap = (AllocList*) malloc(sizeof(AllocList));
ap->pid = pid;
ap->start = fp->start;
ap->end = ap->start+progsize-1;
ap->next = 0;
insertinAlloclist(ap);
updatefreelist(fp,prev,progsize);
return;
}
}
}
void insertinAlloclist( AllocList *p)
{
AllocList *ap, *nextp;
ap = alloclist;
if(ap == 0) // null list
{
alloclist = p;
return;
}
if(p->start <= ap->start) // insert in front
{ p->next = ap;
alloclist = p;
return;
}
while(ap->next != 0 ) // insert in middle
{
nextp = ap->next;
if( p->start <= nextp->start )
{ p->next = nextp;
ap->next = p;
return;
}
else
ap=ap->next;
}
ap->next = p; // insert at end
}
void dispfreelist( )
{
FreeList *p;
p=freelist;
printf("\n-----------------Free List---------\n");
if( p == 0 )
{ printf("Null List\n\n");
return;
}
printf("start end size\n");
printf("----- --- ----\n");
while(p != 0)
{
printf("%3d %3d %3d\n",p->start,p->end,1+p->end-p->start);
p=p->next;
}
}
void dispalloclist( )
{
AllocList *p;
p=alloclist;
printf("\n--------------------");
printf("Allocation List---------------\n");
if( p == 0 )
{ printf("Null List\n\n");
return;
}
printf("PID start end size\n");
printf("--- ----- --- ----\n");
while(p != 0)
{
printf("%3d %3d %3d %3d\n", p->pid,p->start,p->end,1+p->end-p->start);
p=p->next;
}
}
void freememory( int pid ) // node goes from Alloclist to Freelist
{
FreeList *fp;
AllocList *ap,*prev;
ap = alloclist;
while( ap != 0 ) // list not NULL
{
if( ap->pid == pid ) // pid matches
{
if( ap == alloclist) // first node
{
alloclist = ap->next;
}
else if(ap->next == 0 ) // last node
{
prev->next = 0;
}
else // middle node
{
prev->next = ap->next;
}
fp = (FreeList*) malloc(sizeof(FreeList));
fp->start = ap->start;
fp->end = ap->end;
insertinFreelist(fp);
return;
}
else // go to next node
{
prev = ap;
ap = ap->next;
}
}
printf("\npid=%d not found\n\n",pid);
}
void insertinFreelist( FreeList *p) // insert free node in Freelist
{
FreeList *fp, *nextp;
fp = freelist;
if(fp == 0) // null list
{
freelist = p;
return;
}
if(p->start < fp->start) // insert in front
{
if( p->end - fp->start == -1) //p & fp are adjacent
{
fp->start = p->start; // combine p & fp
}
else // p & fp are not adj
{
freelist = p;
p->next = fp;
}
return;
}
while(fp->next != 0 )
{
nextp = fp->next;
if( p->start < nextp->start )
{
// fp & p & nextp are adj
if( fp->end - p->start == -1 && p->end - nextp->start == -1 )
{
fp->end = nextp->end;
fp->next = nextp->next;
free(nextp);
}
// fp & p are adj
else if( fp->end - p->start == -1)
{
fp->end = p->end; // merge fp & p
free(p);
}
// p & nextp are adj
else if( p->end - nextp->start == -1)
{
nextp->start = p->start; //merge p & nextp
free(p);
}
else // add node to list
{
fp->next = p;
p->next = nextp;
}
return;
}
else
fp=fp->next; // go to next node
}
// insert at the end
if( fp->end - p->start == -1) // fp & p are adj
{
fp->end = p->end; // merge fp & p
free(p);
}
else
fp->next = p;
}
void updatefreelist(FreeList *p1, FreeList* p2, int progsize)
{
if( p1->end-p1->start == progsize-1) // progsize == holesize
{
if(p1 == freelist ) // first node
freelist = p1->next;
else if ( p1->next == 0 ) // last node
p2->next = 0;
else // middle node
p2->next = p1->next;
free(p1);
}
else // holesize != progsize
{
p1->start = p1->start+progsize; // update start value
}
}
SAMPLE OUTPUT:
[it65@AntiViruS ~]$ cc firstfit.c
[it65@AntiViruS ~]$ ./a.out
-----------------------------
Memory Management First Fit
-----------------------------
1. Allocate memory
2. Free memory
3. Display status
4. Exit
Enter your choice : 1
Allocate Memory:
Enter pid : 1
Enter size of memory : 40
--------------------Allocation List---------------
PID start end size
--- ----- --- ----
1 1 40 40
-----------------Free List---------
start end size
----- --- ----
41 100 60
Press any key & ENTER to continue : k
-----------------------------
Memory Management First Fit
-----------------------------
1. Allocate memory
2. Free memory
3. Display status
4. Exit
Enter your choice : 2
Freeing Memory:
Enter pid : 1
--------------------Allocation List---------------
Null List
-----------------Free List---------
start end size
----- --- ----
1 100 100
Press any key & ENTER to continue : 3
-----------------------------
Memory Management First Fit
-----------------------------
1. Allocate memory
2. Free memory
3. Display status
4. Exit
Enter your choice : 4
RESULT:
Thus C program for implementing first fit algorithm for memory management has been executed successfully.
