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..

    Reply
  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

    Reply
  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();
    }

    Reply
  4. AKSHAY SAXENA

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

    Reply
  5. kamakukka

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

    Reply
  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();
    }

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

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

    Reply
  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

    Reply
  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…….

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

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

    Reply
  13. DaoNguyen

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

    Reply
  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;
    }
    }
    }

    Reply

Leave a Reply