IMPLEMENTATION OF PAGE REPLACEMENT ALGORITHMS

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


struct page
{
int refstr,index;
struct page *next;
}*h,*p,*ptr,*t,*node;


struct queue
{
int qpage,qpos;
struct queue *q;
}*hq,*f,*r,*qptr,*qtr;


int size,n,i,j,k,fault=0;


void get_string()
{
printf("\n Enter the length of the transverse string:-");
scanf("%d",&size);
printf("\n Enter the string:-");
for(i=0;i<size;i++)
{
node=(struct page*)malloc(sizeof(struct page));
scanf("%d",&node->refstr);
node->index=i+1;
node->next=NULL;
if(h==NULL)
{
h=node;
}
else
{
ptr->next=node;

}
ptr=node;
}
}


void lru()
{
fault=0;
printf("\n Enter the number of frames:-");
int fr,min;
i=0;
scanf("%d",&fr);
for(ptr=h;ptr!=NULL;ptr=ptr->next)
{
 i++;
 qptr=(struct queue*)malloc(sizeof(struct queue));
 qptr->qpage=ptr->refstr;
 qptr->qpos=0;
 qptr->q=NULL;
 if(hq==NULL)
{
hq=qptr;
f=qptr;
}
else
{
r->q=qptr;
}
r=qptr;
fault++;
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
printf("%d\t",qtr->qpage);
}
printf("\n");
if(i==fr)
break;
}
i=j=k=0;

for(ptr=h;ptr!=NULL;ptr=ptr->next)
{
i++;
if(i<=fr)
{
continue;
}
else
{
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
if(qtr->qpage==ptr->refstr)
{
j=1;
}
}
if(j==0)
{
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
k=0;
for(p=h;p!=ptr;p=p->next)
{
k++;
if(p->refstr==qtr->qpage)
{
qtr->qpos=k;
}
}
}
min=f->qpos;
for(qtr=f->q;qtr!=NULL;qtr=qtr->q)
{
if(min>qtr->qpos)
{
min=qtr->qpos;
}
}
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
if(min==qtr->qpos)
{
qtr->qpage=ptr->refstr;
fault++;
}
}
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
printf("%d\t",qtr->qpage);
}
printf("\n");
}
}
j=0;
}
printf("\n Number of page faults:-%d\n",fault);
}


void optimal()
{
fault=0;
printf("\n Enter the number of frames:-");
int fr,max;
i=0;
scanf("%d",&fr);
for(ptr=h;ptr!=NULL;ptr=ptr->next)
{
i++;
qptr=(struct queue*)malloc(sizeof(struct queue));
qptr->qpage=ptr->refstr;
qptr->qpos=0;
qptr->q=NULL;
if(hq==NULL)
{
hq=qptr;
f=qptr;
}
else
{
r->q=qptr;
}
r=qptr;
fault++;
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
printf("%d\t",qtr->qpage);
}
printf("\n");
if(i==fr)
break;
}
i=j=k=0;
int s=0;
for(ptr=h;ptr!=NULL;ptr=ptr->next)
{
i++;
if(i==fr)
{continue;}
else
{
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
if(ptr->refstr==qtr->qpage)
{
j=1;
}
}
if(j==0)
{
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
k=0;
for(p=ptr->next;p!=NULL;p=p->next)
{
k++;
if(p->refstr==qtr->qpage)
{
qtr->qpos=k;
break;
}
}
if(p==NULL)
{
qtr->qpage=ptr->refstr;
fault++;
s=1;
break;
}
}
if(s==0)
{
qtr=f;
max=qtr->qpos;
for(qtr=f->q;qtr!=NULL;qtr=qtr->q)
{
if(max<qtr->qpos)
{max=qtr->qpos;}
}
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
if(max==qtr->qpos)
{
qtr->qpage=ptr->refstr;
fault++;
}
}
}
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
printf("%d\t",qtr->qpage);
}
printf("\n");
}
}
j=s=0;
}
printf("\n Number of page faults:- %d\n",fault);
}


void fifo()
{
fault=0;
printf("\n Enter the number of frames:-");
int fr,min;
i=0;
scanf("%d",&fr);
for(ptr=h;ptr!=NULL;ptr=ptr->next)
{
i++;
qptr=(struct queue*)malloc(sizeof(struct queue));
qptr->qpage=ptr->refstr;
qptr->qpos=ptr->index;
qptr->q=NULL;
if(hq==NULL)
{
hq=qptr;
f=qptr;
}
else
{
r->q=qptr;
}
r=qptr;
fault++;
printf("\nCYCLE %d\n",i);
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
printf("%d\t",qtr->qpage);
}
printf("\n");
if(i==fr)
{
break;
}
}
i=j=0;
for(ptr=h;ptr!=NULL;ptr=ptr->next)
{
i++;

if(i<=fr)
{
continue;
}
else
{
for(qptr=f;qtr!=NULL;qtr=qtr->q)
{
if(ptr->refstr==qptr->qpage)
{
j=1;
}
}
if(j==0)
{
min=f->qpos;
for(qtr=f->q;qtr!=NULL;qtr=qtr->q)
{
if(min>qtr->qpos)
{
min=qtr->qpos;
}
}
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
if(min==qtr->qpos)
{
qtr->qpage=ptr->refstr;
qtr->qpos=ptr->index;
fault++;
}
}
for(qtr=f;qtr!=NULL;qtr=qtr->q)
{
printf("%d\t",qtr->qpage);
}
printf("\n");
}
}
j=0;
}
printf("\n Number of page faults:- %d\n",fault);
}




int main()
{
int ch,op;
get_string();
menu:
printf("\nPAGE REPLACEMENT ALGORITHMS:-");
printf("\nMenu:-\n1.FIFO\n2.Optimal\n3.LRU\n4.Exit\n");
printf("\nEnter your choice:-");
scanf("%d",&op);
switch(op)
{
case 1:
fifo();
break;

case  2:
optimal();
break;


case 3:
lru();
break;


case 4:
exit(0);
}


hq=NULL;
printf("\n 1.Continue\n 2.Exit");
printf("\nEnter your choice:-");
scanf("%d",&ch);
switch(ch)
{
case 1:
goto menu;
case 2:
break;
}
}