This is a single c program which covers the 5 important page replacement algorithms in virtual memory chapter of operating system.
1.FIFO
2.Optimal
3.LRU
4.LFU
5.Second chance
SOURCE CODE:
#include<stdio.h>
int n,nf;
int in[100];
int p[50];
int hit=0;
int i,j,k;
int pgfaultcnt=0;
int bn;
void getData()
{
printf("\nEnter length of page reference sequence:");
scanf("%d",&n);
printf("\nEnter the page reference sequence:");
for(i=0;i<n;i++)
scanf("%d",&in[i]);
printf("\nEnter no of frames:");
scanf("%d",&nf);
}
void initialize()
{
pgfaultcnt=0;
bn=0;
for(i=0;i<nf;i++)
p[i]=9999; // 9999 is used to represent empty frame
}
//function to check whether page fault occurs or not
int isHit(int data)
{
hit=0;
for(j=0;j<nf;j++)
{
if(p[j]==data)
{
hit=1;
break;
}
}
return hit;
}
//function which returns the index of the page which is set
int getHitIndex(int data)
{
int hitind;
for(k=0;k<nf;k++)
{
if(p[k]==data)
{
hitind=k;
break;
}
}
return hitind;
}
void dispPages()
{
for (k=0;k<nf;k++)
{
if(p[k]!=9999) //display except 9999
printf(" %d",p[k]);
}
}
void dispPgFaultCnt(){
printf("\nTotal no of page faults:%d",pgfaultcnt);
}
void fifo()
{
initialize();
for(i=0;i<n;i++)
{
printf("\nFor %d :",in[i]);
if(isHit(in[i])==0)
{
p[bn]=in[i];
bn++;
pgfaultcnt++;
dispPages();
if(bn==nf) // to treat as a circular queue
bn=0;
}
else
printf("No page fault");
}
dispPgFaultCnt();
}
void optimal()
{
initialize();
int near[50];
for(i=0;i<n;i++)
{
printf("\nFor %d :",in[i]);
if(isHit(in[i])==0)
{
pgfaultcnt++;
if(bn<nf) // there are spaces to insert new pages
{
p[bn]=in[i];
bn++;
}
else // any page must be replaced
{
for(j=0;j<nf;j++)
{
int pg=p[j];
int found=0;
for(k=i;k<n;k++)
{
if(pg==in[k])
{
near[j]=k;
found=1;
break;
}
}
if(!found)
near[j]=9999;
}
int max=-9999;
int repindex;
for(j=0;j<nf;j++)
{
if(near[j]>max)
{
max=near[j];
repindex=j;
}
}
p[repindex]=in[i];
}
dispPages();
}
else
printf("No page fault");
}
dispPgFaultCnt();
}
void lru()
{
initialize();
int least[50];
for(i=0;i<n;i++)
{
printf("\nFor %d :",in[i]);
if(isHit(in[i])==0)
{
for(j=0;j<nf;j++)
{
int pg=p[j];
int found=0;
for(k=i-1;k>=0;k--)
{
if(pg==in[k])
{
least[j]=k;
found=1;
break;
}
}
if(!found)
least[j]=-9999;
}
int min=9999;
int repindex;
for(j=0;j<nf;j++)
{
if(least[j]<min)
{
min=least[j];
repindex=j;
}
}
p[repindex]=in[i];
pgfaultcnt++;
dispPages();
}
else
printf("No page fault!");
}
dispPgFaultCnt();
}
void lfu()
{
int usedcnt[100];
int least,repin,sofarcnt=0;
initialize();
for(i=0;i<nf;i++)
usedcnt[i]=0;
for(i=0;i<n;i++)
{
printf("\n For %d :",in[i]);
if(isHit(in[i]))
{
int hitind=getHitIndex(in[i]);
usedcnt[hitind]++;
printf("No page fault!");
}
else
{
pgfaultcnt++;
if(bn<nf)
{ p[bn]=in[i];
usedcnt[bn]++;
bn++;
}
else
{ least=9999;
for(k=0;k<nf;k++)
if(usedcnt[k]<least)
{ least=usedcnt[k]; repin=k; }
p[repin]=in[i];
sofarcnt=0;
for(k=0;k<=i;k++)
if(in[i]==in[k])
sofarcnt++;
usedcnt[repin]=sofarcnt;
}
dispPages();
}
}
dispPgFaultCnt();
}
void secondchance()
{
int usedbit[50];
int victimptr=0;
initialize();
for(i=0;i<nf;i++)
usedbit[i]=0;
for(i=0;i<n;i++)
{
printf("\nFor %d:",in[i]);
if(isHit(in[i]))
{
printf("No page fault!");
int hitindex=getHitIndex(in[i]);
if(usedbit[hitindex]==0)
usedbit[hitindex]=1;
}
else
{
pgfaultcnt++;
if(usedbit[victimptr]==1)
{
do
{
usedbit[victimptr]=0;
victimptr++;
if(victimptr==nf)
victimptr=0;
}while(usedbit[victimptr]!=0);
}
if(usedbit[victimptr]==0)
{
p[victimptr]=in[i];
usedbit[victimptr]=1;
victimptr++;
}
dispPages();
}
if(victimptr==nf)
victimptr=0;
}
dispPgFaultCnt();
}
int main()
{
int choice;
while(1)
{
printf("\nPage Replacement Algorithms\n1.Enter data\n2.FIFO\n3.Optimal\n4.LRU\n5.LFU\n6.Second Chance\n7.Exit\nEnter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
getData();
break;
case 2:
fifo();
break;
case 3:
optimal();
break;
case 4:
lru();
break;
case 5:
lfu();
break;
case 6:
secondchance();
break;
default:
return 0;
break;
}
}
}
1.FIFO
2.Optimal
3.LRU
4.LFU
5.Second chance
SOURCE CODE:
#include<stdio.h>
int n,nf;
int in[100];
int p[50];
int hit=0;
int i,j,k;
int pgfaultcnt=0;
int bn;
void getData()
{
printf("\nEnter length of page reference sequence:");
scanf("%d",&n);
printf("\nEnter the page reference sequence:");
for(i=0;i<n;i++)
scanf("%d",&in[i]);
printf("\nEnter no of frames:");
scanf("%d",&nf);
}
void initialize()
{
pgfaultcnt=0;
bn=0;
for(i=0;i<nf;i++)
p[i]=9999; // 9999 is used to represent empty frame
}
//function to check whether page fault occurs or not
int isHit(int data)
{
hit=0;
for(j=0;j<nf;j++)
{
if(p[j]==data)
{
hit=1;
break;
}
}
return hit;
}
//function which returns the index of the page which is set
int getHitIndex(int data)
{
int hitind;
for(k=0;k<nf;k++)
{
if(p[k]==data)
{
hitind=k;
break;
}
}
return hitind;
}
void dispPages()
{
for (k=0;k<nf;k++)
{
if(p[k]!=9999) //display except 9999
printf(" %d",p[k]);
}
}
void dispPgFaultCnt(){
printf("\nTotal no of page faults:%d",pgfaultcnt);
}
void fifo()
{
initialize();
for(i=0;i<n;i++)
{
printf("\nFor %d :",in[i]);
if(isHit(in[i])==0)
{
p[bn]=in[i];
bn++;
pgfaultcnt++;
dispPages();
if(bn==nf) // to treat as a circular queue
bn=0;
}
else
printf("No page fault");
}
dispPgFaultCnt();
}
void optimal()
{
initialize();
int near[50];
for(i=0;i<n;i++)
{
printf("\nFor %d :",in[i]);
if(isHit(in[i])==0)
{
pgfaultcnt++;
if(bn<nf) // there are spaces to insert new pages
{
p[bn]=in[i];
bn++;
}
else // any page must be replaced
{
for(j=0;j<nf;j++)
{
int pg=p[j];
int found=0;
for(k=i;k<n;k++)
{
if(pg==in[k])
{
near[j]=k;
found=1;
break;
}
}
if(!found)
near[j]=9999;
}
int max=-9999;
int repindex;
for(j=0;j<nf;j++)
{
if(near[j]>max)
{
max=near[j];
repindex=j;
}
}
p[repindex]=in[i];
}
dispPages();
}
else
printf("No page fault");
}
dispPgFaultCnt();
}
void lru()
{
initialize();
int least[50];
for(i=0;i<n;i++)
{
printf("\nFor %d :",in[i]);
if(isHit(in[i])==0)
{
for(j=0;j<nf;j++)
{
int pg=p[j];
int found=0;
for(k=i-1;k>=0;k--)
{
if(pg==in[k])
{
least[j]=k;
found=1;
break;
}
}
if(!found)
least[j]=-9999;
}
int min=9999;
int repindex;
for(j=0;j<nf;j++)
{
if(least[j]<min)
{
min=least[j];
repindex=j;
}
}
p[repindex]=in[i];
pgfaultcnt++;
dispPages();
}
else
printf("No page fault!");
}
dispPgFaultCnt();
}
void lfu()
{
int usedcnt[100];
int least,repin,sofarcnt=0;
initialize();
for(i=0;i<nf;i++)
usedcnt[i]=0;
for(i=0;i<n;i++)
{
printf("\n For %d :",in[i]);
if(isHit(in[i]))
{
int hitind=getHitIndex(in[i]);
usedcnt[hitind]++;
printf("No page fault!");
}
else
{
pgfaultcnt++;
if(bn<nf)
{ p[bn]=in[i];
usedcnt[bn]++;
bn++;
}
else
{ least=9999;
for(k=0;k<nf;k++)
if(usedcnt[k]<least)
{ least=usedcnt[k]; repin=k; }
p[repin]=in[i];
sofarcnt=0;
for(k=0;k<=i;k++)
if(in[i]==in[k])
sofarcnt++;
usedcnt[repin]=sofarcnt;
}
dispPages();
}
}
dispPgFaultCnt();
}
void secondchance()
{
int usedbit[50];
int victimptr=0;
initialize();
for(i=0;i<nf;i++)
usedbit[i]=0;
for(i=0;i<n;i++)
{
printf("\nFor %d:",in[i]);
if(isHit(in[i]))
{
printf("No page fault!");
int hitindex=getHitIndex(in[i]);
if(usedbit[hitindex]==0)
usedbit[hitindex]=1;
}
else
{
pgfaultcnt++;
if(usedbit[victimptr]==1)
{
do
{
usedbit[victimptr]=0;
victimptr++;
if(victimptr==nf)
victimptr=0;
}while(usedbit[victimptr]!=0);
}
if(usedbit[victimptr]==0)
{
p[victimptr]=in[i];
usedbit[victimptr]=1;
victimptr++;
}
dispPages();
}
if(victimptr==nf)
victimptr=0;
}
dispPgFaultCnt();
}
int main()
{
int choice;
while(1)
{
printf("\nPage Replacement Algorithms\n1.Enter data\n2.FIFO\n3.Optimal\n4.LRU\n5.LFU\n6.Second Chance\n7.Exit\nEnter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
getData();
break;
case 2:
fifo();
break;
case 3:
optimal();
break;
case 4:
lru();
break;
case 5:
lfu();
break;
case 6:
secondchance();
break;
default:
return 0;
break;
}
}
}
No comments:
Post a Comment