C Program for Optimal Page Replacement Algorithm

OUTPUT :
2 -1 -1
2 3 -1
2 3 -1
2 3 1
2 3 5
2 3 5
4 3 5
4 3 5
4 3 5
2 3 5
2 3 5
2 3 5

no of page faults : 3

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93   #include<stdio.h> #include<conio.h> int fr[3]; void main() { void display(); int p[12]={2,3,2,1,5,2,4,5,3,2,5,2},i,j,fs[3]; int max,found=0,lg[3],index,k,l,flag1=0,flag2=0,pf=0,frsize=3; clrscr(); for(i=0;i<3;i++) { fr[i]=-1; } for(j=0;j<12;j++) { flag1=0; flag2=0; for(i=0;i<3;i++) { if(fr[i]==p[j]) { flag1=1; flag2=1; break; } } if(flag1==0) { for(i=0;i<3;i++) { if(fr[i]==-1) { fr[i]=p[j]; flag2=1; break; } } }   if(flag2==0) { for(i=0;i<3;i++) lg[i]=0; for(i=0;i<frsize;i++) { for(k=j+1;k<12;k++) { if(fr[i]==p[k]) { lg[i]=k-j; break; } } } found=0; for(i=0;i<frsize;i++) { if(lg[i]==0) { index=i; found=1; break; } } if(found==0) { max=lg[0]; index=0; for(i=1;i<frsize;i++) { if(max<lg[i]) { max=lg[i]; index=i; } } } fr[index]=p[j]; pf++; } display(); } printf("\n no of page faults:%d",pf); getch(); } void display() { int i; printf("\n"); for(i=0;i<3;i++) printf("\t%d",fr[i]); }```

OUTPUT :
2 -1 -1
2 3 -1
2 3 -1
2 3 1
2 3 5
2 3 5
4 3 5
4 3 5
4 3 5
2 3 5
2 3 5
2 3 5

no of page faults : 3

20 Responses to “C Program for Optimal Page Replacement Algorithm”

1. Thank you very much sir i struggled for 3 weeks to get the logic for this program…. thank you… thank you..

2. Yes plz help us==> guess some thing wrong !! Number of faults is not true even i
tryed an other pages’s refenerement but DOESn’t mutch

3. Uday Sagar

//****this works fine****
#include
#include
void main()
{
int x,n,q2[10],i,f,j=0,k,pf=0,c=0,h,m,b=0;
char q[10],s[20] ;
clrscr();
printf(“\nenter :\n”);
scanf(“%s”,&s);
n=strlen(s);
printf(“enter the no. of frames:\n”);
scanf(“%d”,&f);
s[n+1]=”;
for(i=0;i<f;i++)
{
q[i]='';
q2[i]=0;
}

for(i=0;i<n;i++)
{
c=0;
for(k=0;k<f;k++)
if(s[i]==q[k])
c++;
if(c==0)
{ if(q[f-1]=='')
{
q[j]=s[i];
pf++;
j++;
if(j==f)
j=0;
}
else
{
for(k=0;k<f;k++)
{b=0;
for(x=i+1;x<n;x++)
{
if(b==0)
if(q[k]==s[x])
{q2[k]=x;
b++;
}
}
if(q2[k]==0)
q2[k]=n;
}
j=0;
for(k=1;k<f;k++)
if(q2[j]<q2[k])
j=k;
for(k=0;k<f;k++)
q2[k]=0;
q[j]=s[i];
pf++;
}
}
for(m=0;m<f;m++)
printf("%c ",q[m]);
printf("\n");
}
printf("\nfinal queue is:\n\t\t");

for(m=0;m<f;m++)
printf("\n%c",q[m]);

printf("\ntotal pf is: %d",pf);
printf("\npf due to replacement is: %d",pf-f);
getch();
}

4. AKSHAY SAXENA

Pllzz lemme know whether the original post can be used for the implementation or not???

5. kamakukka

orei chetta na kodakallara , telvakapothe madda musukuni gudda denginchukondi. ante gani me sullilu maa notlo pettalani try cheyadhu..

6. this program work fine
#include
#include
void main()
{
int a[5],b[20],p=0,q=0,m=0,h,k,i,q1=1,j,n;
char f=’F’;
clrscr();
printf(“Enter the number of page:”);
scanf(“%d”,&n);
printf(“enter the number”);
for(i=0;i<n;i++)
scanf("%d",&b[i]);
for(i=0;i=3)
q=0;
a[q]=b[i];
q++;
if(q1<3)
{
q1=q;
}
}
printf("\n%d",b[i]);
printf("\t");
for(h=0;h%c”,f);
m++;
}
p=0;
for(k=0;k<q-1;k++)
{
if(b[i+1]==a[k])
p=1;
}
}
printf("\nNo of faults:%d",m);
getch();
}

7. i love you..you really saved my life..you know this really helped me alot

8. than q for the code……………..
and no of page faults is not correct………….hav to check
3 is no of frames

9. the no. of page faults is actually 6….but in the code the initial faults are not counted ie the code is correct thats all i wanna say

10. no of page fault is wrong…..
u have to increment pf in first if condition{if (flag1==0)}…
then it will fine
the no of pf is 6…………
thank you…….

11. increment pf in first if condition{if (flag1==0)}…
page fault is 6
thank you

12. Hello, can anyone give the C or C++ code for MRU page replacement algorithm? I couldn’t find it anywhere. Please help

13. DaoNguyen

Hello, can anyone give the source code C, C++, Java for optimal mst algorithm? I couldn’t find it anywhere. Please help

14. Marshal Truman

#include
int n,nf;
int in[100];
int p[50];
int hit=0;
int i,j,k;
int pgfaultcnt=0;

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;
for(i=0;i<nf;i++)
p[i]=9999;
}

int isHit(int data)
{
hit=0;
for(j=0;j<nf;j++)
{
if(p[j]==data)
{
hit=1;
break;
}

}

return hit;
}

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)
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)
{

for(k=0;k<nf-1;k++)
p[k]=p[k+1];

p[k]=in[i];
pgfaultcnt++;
dispPages();
}
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)
{

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;
}
else
found=0;
}
if(!found)
near[j]=9999;
}
int max=-9999;
int repindex;
for(j=0;jmax)
{
max=near[j];
repindex=j;
}
}
p[repindex]=in[i];
pgfaultcnt++;

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=0;k–)
{
if(pg==in[k])
{
least[j]=k;
found=1;
break;
}
else
found=0;
}
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,bn;
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]=usedcnt[bn]+1;
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=sofarcnt+1;
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;
}
}
}

Projects

Free email signup

Get latest projects, articles in your mail box, subscribe to electrifriends

Email: