PAGE REPLACEMENT ALGORITHM
Page replacement comes into action when you have lesser physical memory(RAM) as compared to what is needed by the application to run.Your operating system can fool the application by using virtual memory.And only those pages are present in the physical memory which the application demands or may be needed soon by the application.Here we are using three algorithms to achieve that:
1) FCFS (First come first serve) : Here the latest page that is encountered is moved to the physical memory and it replaces the oldest page out there in the main memory.
2) Optimal : It basically checks what pages that are currently in the memory that may be required again in the future.The page that will not be required very soon is replaced by the new page.In real time scenario, it's difficult to implement because you don't know what's coming your way!!!
3) LRU (Least Recently Used) : In this case we check the past page references and the one that has been referenced the the least number of times and is present in main memory, then it will be replaced by the new page.
The following code illustrates the concept:
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,i,seq[40],page=0,ch,pgfault=0,pga[10],ptr=0,flag=0,cnt=0,j,temp,l,m,flag1=0,cnt1=0,cnt2=0,k,z;
//float hit;
char ans;
printf("\nENTER THE TOTAL NUMBER OF PAGE REFERENCES : ");
scanf("%d",&n);
printf("\nENTER THE SEQUENCE OF PAGE REFERENCES: ");
for(i=0;i<n;i++)
{
printf("\nENTER PAGE REFERENCE NO.%d: ",i);
scanf("%d",&seq[i]);
}
printf("\nENTER THE FRAME SIZE: ");
scanf("%d",&page);
for(i=0;i<page;i++)
{
pga[i]=-1;
}
do
{
printf("\n******MENU*******\n");
printf("\n1: FIFO\n2. LRU\n3. OPTIMAL\n");
printf("\nENTER YOUR CHOICE: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nWELCOME TO FIFO PAGE\n");
pgfault=0;cnt=0;ptr=0;
printf("\nPAGE\tFRAME\n");
for(i=0;i<page;i++)
{
pga[i]=-1;
}
for(i=0;i<n;i++)
{
flag=0;
for(j=0;j<page;j++)
{
if(seq[i]==pga[j])
{
flag=1;
break;
}
}
if(flag==1)
{
}
else
{
if(cnt==page)
{
pga[ptr]=seq[i];
ptr++;
pgfault++;
if(ptr==page)
{
ptr=0;
}
}
else if(cnt<page)
{
pga[cnt]=seq[i];
cnt++;
pgfault++;
}
}
printf("\n%d",seq[i]);
for(z=0;z<page;z++)
{
printf("\t%d",pga[z]);
}
}
printf("\nTHE NO. OF PAGE FAULTS ARE: %d\n\n",pgfault);
temp=n-pgfault;
printf("THE HIT RATIO IS: %d/%d\n\n",temp,n);
break;
case 2:
cnt=0,pgfault=0;
printf("\nWELCOME TO LRU PAGE\n");
for(i=0;i<page;i++)
{
pga[i]=-1;
}
printf("\nPAGE\tFRAME\n");
for(i=0;i<n;i++)
{
cnt1=0;cnt2=0,flag=0;
for(j=0;j<page;j++)
{
if(seq[i]==pga[j])
{
flag=1;
break;
}
}
if(flag==1)
{
}
else
{
if(cnt==page)
{
for(l=0;l<page;l++)
{
flag1=0;
for(m=i;m>=0;m--)
{
if(seq[m]==pga[l])
{
if(cnt1<(i-m))
{
cnt1=i-m;
cnt2=l;
}
flag1=1;
break;
}
}
}
pga[cnt2]=seq[i];
pgfault++;
}
else if(cnt<page)
{
pga[cnt]=seq[i];
cnt++;
pgfault++;
}
}
printf("\n%d",seq[i]);
for(z=0;z<page;z++)
{
printf("\t%d",pga[z]);
}
}
printf("\nTHE NO. OF PAGE FAULTS ARE: %d\n\n",pgfault);
temp=n-pgfault;
printf("THE HIT RATIO IS: %d/%d\n\n",temp,n);
break;
case 3:
cnt=0,pgfault=0;
printf("\nWELCOME TO OPTIMAL PAGE\n");
for(i=0;i<page;i++)
{
pga[i]=-1;
}
printf("\nPAGE\tFRAME\n");
for(i=0;i<n;i++)
{
cnt1=0;cnt2=0,flag=0;
for(j=0;j<page;j++)
{
if(seq[i]==pga[j])
{
flag=1;
break;
}
}
if(flag==1)
{
}
else
{
if(cnt==page)
{
for(l=0;l<page;l++)
{
flag1=0;
for(m=i;m<n;m++)
{
if(seq[m]==pga[l])
{
if(cnt1<(m-i))
{
cnt1=m-i;
cnt2=l;
}
flag1=1;
break;
}
}
if(flag1!=1)
{
cnt1=99;
cnt2=l;
}
}
pga[cnt2]=seq[i];
pgfault++;
}
else if(cnt<page)
{
pga[cnt]=seq[i];
cnt++;
pgfault++;
}
}
printf("\n%d",seq[i]);
for(z=0;z<page;z++)
{
printf("\t%d",pga[z]);
}
}
printf("\nTHE NO. OF PAGE FAULTS ARE: %d\n\n",pgfault);
temp=n-pgfault;
printf("THE HIT RATIO IS: %d/%d\n\n",temp,n);
break;
}
printf("Do You Want To Continue?(y/n)");
scanf("%c",&ans);
scanf("%c",&ans);
}while(ans=='y' || ans=='Y');
return 0;
}
Please note that I have implemented this code in Linux's text editor using gcc compiler.
Feel free to share if you think this post can be improved or you have some confusion regarding the code.
No comments:
Post a Comment
Thanks for your valuable comment