Student Projects > Software Development > C > C Programs > C Program for Optimal Page Replacement Algorithm

C Program for Optimal Page Replacement Algorithm

Editorial Team C Programs

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

Editorial Team
Editorial Team

We are a group of young techies trying to provide the best study material for all Electronic and Computer science students. We are publishing Microcontroller projects, Basic Electronics, Digital Electronics, Computer projects and also c/c++, java programs.

20 thoughts on “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..

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

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

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

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

  11. #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;
    }
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

Get the latest updates on your inbox

Be the first to receive the latest updates from Codesdoc by signing up to our email subscription.

    StudentProjects.in