Write a program that implements the FIFO and LRU page replacement algorithms pre
ID: 3765090 • Letter: W
Question
Write a program that implements the FIFO and LRU page replacement algorithms presented in Chapter 9 of the textbook. The implemented functions need to compute number of page faults as explained in detail below. Assume that demand paging is used. Using python to compile your code.
'''
Simple FIFO page replacement algorithm
'''
def FIFO(size, pages):
faults = 0 # just a value used in skeletal code to make it execute
return faults
'''
LRU algorithm
'''
def LRU(size, pages):
faults = 0 # just a value used in skeletal code to make it execute
return faults
def main():
pages = (7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1)
size = int(input('Enter number of frames: '))
print('The FIFO algorithm had', FIFO(size,pages), 'page faults.')
print('The LRU algorithm had', LRU(size,pages), 'page faults.')
main()
Explanation / Answer
Below is the program for page replacement algorithm. The output of the program is also provided. Please go through the program once.
You can just copy paste the program and execute. No need to edit the program, this program is running without any errors.
#include<stdio.h>
void FIFO();
void LRU();
void OPTIMAL();
int main()
{
int ch;
do
{
printf(" 1.FIFO 2.LRU 3.Optimal 4.Exit Enter Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
FIFO();
break;
case 2:
LRU();
break;
case 3:
OPTIMAL();
break;
}
}while(ch!=4);
}
void FIFO()
{
int frame[3]={-1,-1,-1},ref[20],cnt=0,i,j,no,flag;
float ratio,hitcnt=0.00;
printf(" Enter length of reference string : ");
scanf("%d",&no);
printf(" Enter reference String with giving space .... ");
for(i=0;i<no;i++)
scanf("%d",&ref[i]);
//printf(" Execution is started here .....");
for(i=0;i<no;i++)
{
flag=0;
for(j=0;j<3;j++)
if(frame[j]==ref[i])
{
printf(" Page Hit ");
hitcnt++;
flag=1;
break;
}
if(flag==0)
{
printf(" Page Miss");
printf(" Before : ");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
frame[cnt]=ref[i];
cnt++;
if(cnt>=3)
cnt=0;
printf(" After : ");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
}
}
ratio=hitcnt/no;
printf(" Hit ratio = %f ",ratio);
}
void LRU()
{
int frame[3]={-1,-1,-1},used[3]={-1,-1,-1},cnt=0,ref[20],i,j,flag,no,index,value;
float ratio,hitcnt=0;
printf(" Enter length of reference string : ");
scanf("%d",&no);
printf(" Enter reference String with giving space ");
for(i=0;i<no;i++)
scanf("%d",&ref[i]);
//printf(" Execution is started here ");
for(i=0;i<no;i++)
{
flag=0;
for(j=0;j<3;j++)
if(frame[j]==ref[i])
{
printf(" Page Hit ");
hitcnt++;
flag=1;
used[j]=cnt;
break;
}
if(flag==0)
{
printf(" Page Miss");
printf(" Before :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
//selection of victim for replacement
index=0;
value=used[0];
if(cnt!=0) {
for(j=0;j<3;j++)
if(value>used[j]&&value!=used[j])
{
index=j;
value=used[j];
}
}
//printf(" Victim is %d ",index);
frame[index]=ref[i];
used[index]=cnt;
printf(" After :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
}
cnt++;
}
ratio=hitcnt/no;
printf(" Hit ratio = %f ",ratio);
}
void OPTIMAL()
{
int frame[3]={-1,-1,-1},used[3]={-1,-1,-1},cnt=0,ref[20],i,j,flag,no,val1,val2,val3,index;
float ratio,hitcnt=0;
printf(" Enter length of reference string : ");
scanf("%d",&no);
printf(" Enter reference String with giving space ");
for(i=0;i<no;i++)
scanf("%d",&ref[i]);
//printf(" Execution is started here ");
for(i=0;i<no;i++)
{
flag=0;
for(j=0;j<3;j++)
if(frame[j]==ref[i])
{
flag=1;
printf(" Page Hit");
hitcnt++;
break;
}
if(flag==0)
{
printf(" Page Miss");
if(cnt<3)
{
frame[cnt]=ref[i];
printf(" Status :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
cnt++;
}
else
{
printf(" Before :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
//selection of victim
val1=frame[0];
flag=0;
for(j=i;j<no;j++)
if(ref[j]==val1)
{
val1=j;
flag=1;
break;
}
if(flag==0)
val1=no;
val2=frame[1];
flag=0;
for(j=i;j<no;j++)
if(ref[j]==val2)
{
val2=j;
flag=1;
break;
}
if(flag==0)
val2=no;
val3=frame[2];
flag=0;
for(j=i;j<no;j++)
if(ref[j]==val3)
{
val3=j;
flag=1;
break;
}
if(flag==0)
val3=no;
if(val1<val2)
if(val3<val2)
index=1;
else
index=2;
else
if(val3<val1)
index=0;
else
index=2;
frame[index]=ref[i];
printf(" After :");
for(j=0;j<3;j++)
printf(" %d",frame[j]);
}
}
}
ratio=hitcnt/no;
printf(" Hit ratio = %f ",ratio);
}
/* OUTPUT
prashant@prashant-OptiPlex-755:~$ gcc pgreplacement.c
prashant@prashant-OptiPlex-755:~$ ./a.out
1.FIFO
2.LRU
3.Optimal
4.Exit
Enter Choice : 1
Enter length of reference string : 12
Enter reference String with giving space ....
2 3 2 1 5 2 4 5 3 2 5 2
Page Miss Before : -1 -1 -1 After : 2 -1 -1
Page Miss Before : 2 -1 -1 After : 2 3 -1
Page Hit
Page Miss Before : 2 3 -1 After : 2 3 1
Page Miss Before : 2 3 1 After : 5 3 1
Page Miss Before : 5 3 1 After : 5 2 1
Page Miss Before : 5 2 1 After : 5 2 4
Page Hit
Page Miss Before : 5 2 4 After : 3 2 4
Page Hit
Page Miss Before : 3 2 4 After : 3 5 4
Page Miss Before : 3 5 4 After : 3 5 2
Hit ratio = 0.250000
1.FIFO
2.LRU
3.Optimal
4.Exit
Enter Choice : 2
Enter length of reference string : 12
Enter reference String with giving space
2 3 2 1 5 2 4 5 3 2 5 2
Page Miss Before : -1 -1 -1 After : 2 -1 -1
Page Miss Before : 2 -1 -1 After : 2 3 -1
Page Hit
Page Miss Before : 2 3 -1 After : 2 3 1
Page Miss Before : 2 3 1 After : 2 5 1
Page Hit
Page Miss Before : 2 5 1 After : 2 5 4
Page Hit
Page Miss Before : 2 5 4 After : 3 5 4
Page Miss Before : 3 5 4 After : 3 5 2
Page Hit
Page Hit
Hit ratio = 0.416667
1.FIFO
2.LRU
3.Optimal
4.Exit
Enter Choice : 3
Enter length of reference string : 12
Enter reference String with giving space
2 3 2 1 5 2 4 5 3 2 5 2
Page Miss Status : 2 -1 -1
Page Miss Status : 2 3 -1
Page Hit
Page Miss Status : 2 3 1
Page Miss Before : 2 3 1 After : 2 3 5
Page Hit
Page Miss Before : 2 3 5 After : 4 3 5
Page Hit
Page Hit
Page Miss Before : 4 3 5 After : 2 3 5
Page Hit
Page Hit
Hit ratio = 0.500000
1.FIFO
2.LRU
3.Optimal
4.Exit
Enter Choice : 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.