Write a program that implements the FIFO and LRU page-replacement algorithms pre
ID: 3774523 • Letter: W
Question
Write a program that implements the FIFO and LRU page-replacement algorithms presented in this chapter.
First, generate a random pagereference 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. Your algorithms will be based on the abstract class depicted in Figure 9.32. Design and implement two classes—LRU and FIFO—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 FIFO algorithm.
There are two classes available on WileyPLUS to test your algorithm:
a. PageGenerator—a class that generates page-reference strings with page numbers ranging from 0 to 9. The size of the reference string is passed to the PageGenerator constructor. Once a PageGenerator object is constructed, the getReferenceString() method returns the reference string as an array of integers.
b. Test—used to test your FIFO and LRU implementations of the ReplacementAlgorithm abstract class. Test is invoked as
java Test <# of page frames>
Once you have implemented the FIFO and LRU algorithms, experiment with a different number of page frames for a given reference string and record the number of page faults. Does one algorithm perform better than the other? For a given reference-string size, what is the optimal number of page frames?
Explanation / Answer
code to copy :
/* program that implements the FIFO and LRU page-replacement algorithms */
#include<stdio.h>
void FIFO();
void LEASTRECENTLYUSED();
void OPTIMAL();
int main()
{
int ch;
do
{
printf(" 1.FIFO 2.LEASTRECENTLYUSED 3.Optimal 4.Exit Enter Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
FIFO();
break;
case 2:
LEASTRECENTLYUSED();
break;
case 3:
OPTIMAL();
break;
}
}while(ch!=4);
}
void FIFO()
{
int frame[3]={-1,-1,-1},refer[20],ctn=0,i,j,number,flag;
float ratio,hitctn=0.00;
printf(" Enter length of refererence string : ");
scanf("%d",&number);
printf(" Enter refererence String with giving space .... ");
for(i=0;i<number;i++)
scanf("%d",&refer[i]);
//printf(" Execution is started here .....");
for(i=0;i<number;i++)
{
flag=0;
for(j=0;j<3;j++)
if(frame[j]==refer[i])
{
printf(" Page Hit ");
hitctn++;
flag=1;
break;
}
if(flag==0)
{
printf(" Page Miss");
printf(" Before : ");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
frame[ctn]=refer[i];
ctn++;
if(ctn>=3)
ctn=0;
printf(" After : ");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
}
}
ratio=hitctn/number;
printf(" Hit ratio = %f ",ratio);
}
void LEASTRECENTLYUSED()
{
int frame[3]={-1,-1,-1},used[3]={-1,-1,-1},ctn=0,refer[20],i,j,flag,number,index,value;
float ratio,hitctn=0;
printf(" Enter length of refererence string : ");
scanf("%d",&number);
printf(" Enter refererence String with giving space ");
for(i=0;i<number;i++)
scanf("%d",&refer[i]);
//printf(" Execution is started ");
for(i=0;i<number;i++)
{
flag=0;
for(j=0;j<3;j++)
if(frame[j]==refer[i])
{
printf(" Page Hit ");
hitctn++;
flag=1;
used[j]=ctn;
break;
}
if(flag==0)
{
printf(" Page Miss");
printf(" Before :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
//selection of Fault for replacement
index=0;
value=used[0];
if(ctn!=0) {
for(j=0;j<3;j++)
if(value>used[j]&&value!=used[j])
{
index=j;
value=used[j];
}
}
//printf(" Fault is %d ",index);
frame[index]=refer[i];
used[index]=ctn;
printf(" After :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
}
ctn++;
}
ratio=hitctn/number;
printf(" Hit ratio = %f ",ratio);
}
void OPTIMAL()
{
int frame[3]={-1,-1,-1},used[3]={-1,-1,-1},ctn=0,refer[20],i,j,flag,number,value1,value2,value3,index;
float ratio,hitctn=0;
printf(" Enter length of refererence string : ");
scanf("%d",&number);
printf(" Enter refererence String with giving space ");
for(i=0;i<number;i++)
scanf("%d",&refer[i]);
//printf(" Execution is started here ");
for(i=0;i<number;i++)
{
flag=0;
for(j=0;j<3;j++)
if(frame[j]==refer[i])
{
flag=1;
printf(" Page Hit");
hitctn++;
break;
}
if(flag==0)
{
printf(" Page Miss");
if(ctn<3)
{
frame[ctn]=refer[i];
printf(" Status :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
ctn++;
}
else
{
printf(" Before :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
//selection of Fault
value1=frame[0];
flag=0;
for(j=i;j<number;j++)
if(refer[j]==value1)
{
value1=j;
flag=1;
break;
}
if(flag==0)
value1=number;
value2=frame[1];
flag=0;
for(j=i;j<number;j++)
if(refer[j]==value2)
{
value2=j;
flag=1;
break;
}
if(flag==0)
value2=number;
value3=frame[2];
flag=0;
for(j=i;j<number;j++)
if(refer[j]==value3)
{
value3=j;
flag=1;
break;
}
if(flag==0)
value3=number;
if(value1<value2)
if(value3<value2)
index=1;
else
index=2;
else
if(value3<value1)
index=0;
else
index=2;
frame[index]=refer[i];
printf(" After :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
}
}
}
ratio=hitctn/number;
printf(" Hit ratio = %f ",ratio);
}
--------------****--------------------*****----------------------------
Q: Does one algorithm perform better than the other? For a given reference-string size, what is the optimal number of page frames?
There is no single cache calculation which will dependably do well since that requires consummate learning without bounds. (What's more, on the off chance that you know where to get that...) The predominance of LRU in VM store configuration is the aftereffect of a long history of measuring framework conduct.
With a specific end goal to be a powerful reserve, it needs to keep the things well on the way to be asked for in memory.
LRU keeps the things that were most as of late utilized as a part of memory. FIFO keeps the things that were most as of late included. LRU is, when all is said in done, more effective, on the grounds that there are by and large memory things that are included once and never utilized again, and there are things that are included and utilized as often as possible. LRU is a great deal more inclined to keep the much of the time utilized things as a part of memory.
It is difficult to decide an "optimal" page frames for any given framework. Current standards go from 4K to 4M, and tend towards bigger page sizes over the long haul.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.