WRITE A PROGRAM THAT IMPLEMENTS THE OPTIMAL AND LRU PAGE REPLACEMENT ALGORITHMS.

Question

WRITE A PROGRAM THAT IMPLEMENTS THE OPTIMAL AND LRU PAGE REPLACEMENT ALGORITHMS.

You may use any of the following languages for your program: C, C++, Java.

Write a program that implements the OPTIMAL and LRU page-replacement algorithms presented in this chapter. First, generate a random page reference string where page numbers range from 0 to 9. Apply the random page-reference string to each algorithm, and record the number of page faults incurred by each algorithm. Implement the replacement algorithms so that the number of page frames can vary as well. Assume that demand paging is used. Design and implement two classes—LRU and OPTIMAL—that extend ReplacementAlgorithm. Each of these classes will implement the insert() method, one class using the LRU page-replacement algorithm and the other using the OPTIMAL algorithm.

The random page-reference string should consist of at least 10000 numbers.Using the same reference string, obtain the number of faults for each algorithm (Optimal and LRU) for each of the following number of page frames:1, 2, 3, 4, 5, 6, 7, 8. Plot a graph of page fault frequency (y-axis) versus number of page frames (x-axis). Draw both plots on the same graph. Label each plot by the algorithm identifier (Optimal, LRU).Note: it is not expected that your program will produce the plot; rather, a separate application can be used to make the plot.

NEED TO HAVE

- program listing.

-table of results.

-graph

Explanation / Answer

A PROGRAM THAT IMPLEMENTS THE OPTIMAL AND LRU PAGE REPLACEMENT ALGORITHMS.

void lru(char [],char [],int,int);
void opt(char [],char [],int,int);

int main()
{
int ch,YN=1,i,l,f;
char F[10],s[25];
clrscr();
//system(“clear”);
printf(“ Enter the no of empty frames: “);
scanf(“%d”,&f);
printf(“ Enter the length of the string: “);
scanf(“%d”,&l);
printf(“ Enter the string: “);
scanf(“%s”,s);
for(i=0;i<f;i++)
F[i]=-1;
do
{
// system(“clear”);
printf(“ *********** MENU ***********”);
printf(“ 1:LRU 2:OPT 4:EXIT”);
printf(“ Enter your choice: “);
scanf(“%d”,&ch);
//system(“clear”);
switch(ch)
{
case 1:
for(i=0;i<f;i++)
{
F[i]=-1;
}
lru(s,F,l,f);
break;
case 2:
for(i=0;i<f;i++)
{
F[i]=-1;
}

opt(s,F,l,f);
break;
case 3:
exit(0);
}
printf(“ Do u want to continue IF YES PRESS 1 IF NO PRESS 0 : “);
scanf(“%d”,&YN);
}while(YN==1);return(0);
}

//LRU
void lru(char s[],char F[],int l,int f)
{
int i,j=0,k,m,flag=0,cnt=0,top=0;
printf(“ PAGE FRAMES FAULTS”);
for(i=0;i<l;i++)
{
for(k=0;k<f;k++)
{
if(F[k]==s[i])
{
flag=1;
break;
}
}

printf(“ %c ”,s[i]);
if(j!=f && flag!=1)
{
F[top]=s[i];
j++;

if(j!=f)
top++;
}
else
{
if(flag!=1)
{
for(k=0;k<top;k++)
{
F[k]=F[k+1];
}

F[top]=s[i];
}
if(flag==1)
{
for(m=k;m<top;m++)
{
F[m]=F[m+1];
}

F[top]=s[i];
}
}
for(k=0;k<f;k++)
{
printf(” %c”,F[k]);
}

if(flag==0)
{
printf(“ Page-fault%d”,cnt);
cnt++;
}
else
printf(“ No page fault”);
flag=0;
}

}

//optimal
void opt(char s[],char F[],int l,int f)
{
int i,j=0,k,m,flag=0,cnt=0,temp[10];

printf(“ PAGE FRAMES FAULTS”);
for(i=0;i<10;i++)
temp[i]=0;

for(i=0;i<f;i++)
F[i]=-1;

for(i=0;i<l;i++)
{
for(k=0;k<f;k++)
{
if(F[k]==s[i])
flag=1;
}

if(j!=f && flag==0)
{
F[j]=s[i];
j++;
}

else if(flag==0)
{
for(m=0;m<f;m++)
{
for(k=i+1;k<l;k++)
{
if(F[m]!=s[k])
{
temp[m]=temp[m]+1;
}
else
break;
}
}
m=0;
for(k=0;k<f;k++)
{
if(temp[k]>temp[m])
{
m=k;
}
}

F[m]=s[i];
}

printf(“ %c ”,s[i]);
for(k=0;k<f;k++)
{
printf(” %c”,F[k]);
}
if(flag==0)
{
printf(“ Page-fault %d”,cnt);
cnt++;
}
else
printf(“ No Page-fault”);
flag=0;

for(k=0;k<10;k++)
temp[k]=0;
}
}

For second part you can use any other application that plot grap for output

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.