All the programmes below are in "C" and use file handling.There will be sub headings related to the Page replacement algorithms and below them are the corresponding code snippets.The code once compiled runs automatically using the data from text file and displays the output.Tested for DevCPP and codeblocks in Windows.Just be careful to keep the input text file in the same folder as programmes and change the name of the input file in the programme to correspond to the text file.If you have doubts, comment, will clarify them, with in at max two days.
Input file (Input.txt – same for all algorithms)
20
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
1.FIFO
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21];//To take the input of reference string
int frame[SIZE];//This is for frames
int repptr=0;//The pointer for the page that needs to be replaced
int count=0;//For counting number of page faults
int display()//To display the elements of the frame
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Pagerep(int ele)
{
int temp;
temp=frame[repptr];
frame[repptr]=ele;
repptr++;//The pointer moves to the next frame since the current frame became the newest
if(repptr==SIZE)
repptr=0;
return temp; //Returns the victim page
}
int Pagefault(int ele)
{if(full!=SIZE)
frame[full++]=ele;//Untill all the frames fill, there is no call for page replacement
else
printf("The page replaced is %d",Pagerep(ele));//Displaying of victim page
}
int Search(int ele)//This would search and return the flag that tells whether the page is already //present in the frame or not
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;
break;
}}
return flag;
}
int main()
{int n,i;
FILE *fp;//For taking input from a file
//Start
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
fclose(fp);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
//End
for(i=0;i<n;i++)
{
if(Search(a[i])!=1)
{Pagefault(a[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n",count);
getche();//For waiting
return 0;
}
2.Optimal Page Replacement Algorithm
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
static int f=0;
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Longestopt()
{int temp[SIZE]={0};/*This is for checking the occurence of nearest possible future pages, considering no page is nearest in the beginning*/
int c=0;//Counter to break the loop once we get two nearest future pages
int id,i,k,j=SIZE;
id=0;
for(i=f+1;i<n;i++)//Checking from the current time of use till the end of string for future references
{ for(k=0;k<j;k++) //Checking whether a page occurs in future or not
{ if(a[i]==frame[k])
{if(temp[k]!=1)
{temp[k]=1;
c++;
}
break;}}
if(c==2)
break;//Once we get two future pages then we may break
}
id=2;
while(id!=0)
{if(temp[id]==0)//Checking for the page which is not the nearest future reference
break;
id--;
}
repptr=id;
return repptr;//Returning the replacement pointer with the value of victim page
}
int Pagerep(int ele)
{
int temp;
repptr=Longestopt();
temp=frame[repptr];
frame[repptr]=ele;
return temp;
}
int Pagefault(int ele)
{if(full!=SIZE)
frame[full++]=ele;
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;
break;
}}
return flag;
}
int main()
{int i;
FILE *fp;
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
for(i=0;i<n;i++)
{f=i;
if(Search(a[i])!=1)
{Pagefault(a[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n",count);
getche();
return 0;
}
3.LRU using Stack
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int stk[SIZE];//Stack for storing the page numbers as per their reference criteria
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",stk[i]);
}
/* A function for removing the referenced element from the stack and keeping it in the top, while moving all
the elements up or down corresepondingly*/
int LRstackopt(int p)//The input to this function is the referenced page
{int temp;
int i;
for(i=0;i<n;i++)
if(stk[i]==p)
break;
temp=stk[i];//Storing the referenced value in temp
while(i!=SIZE-1)//Moving the other elements so that the TOP is empty
{stk[i]=stk[i+1];i++;
}
stk[i]=temp;//Storing the element in the TOP from temp
}
int Pagerep(int ele)
{
int temp;
repptr=stk[0];//Always the victim page is selected as the first element of stack
temp=frame[repptr];
frame[repptr]=ele;
LRstackopt(repptr);//Now the page that is brought is the latest referenced one, so it is moved to TOP
return temp;
}
int Pagefault(int ele)
{if(full!=SIZE)
{stk[full]=full;//First stack is populated till all the pages are full
frame[full++]=ele;}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;LRstackopt(i);//When ever reference is made, but pae fault doesn't occur, the referenced page is moved to TOP
break;
}}
return flag;
}
int main()
{int i;
FILE *fp;
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
if(Search(a[i])!=1)
{Pagefault(a[i]);
count++;
}
display();
}
printf("\nThe number of page faults are %d\n",count);
getche();
return 0;
}
4.LRU using Counter
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int ctr[SIZE]={0};
static int f=0;//This is a counter that keeps track of current time
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Longestopt()//Fucntion for discivering the least recently used page using their corresponding counter values
{int i,min;
min=0;
for(i=0;i<SIZE;i++)
if(ctr[min]>ctr[i])
min=i;
repptr=min;
return repptr;
}
int Pagerep(int ele)
{
int temp;
repptr=Longestopt();//Gets the LRU page from a function
temp=frame[repptr];
frame[repptr]=ele;
ctr[repptr]=f;//When ever a page is brought it's counter is kept as per the current time of use
return temp;
}
int Pagefault(int ele)
{if(full!=SIZE)
{ctr[full]=f;//Setting the counter as per current time of use
frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;ctr[i]=f;//If page fault doesn't occur, but the element is referenced, it's counter is set to the current time of use
break;
}}
return flag;
}
int main()
{int i;
FILE *fp;
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
for(i=0;i<n;i++)
{f++;//Time of use is incremented
if(Search(a[i])!=1)
{Pagefault(a[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n",count);
getche();
return 0;
}
5.LFU
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int ctr[SIZE]={0};//Counter to know the frequency, intially all have zero frequency of use
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Longestopt()
{int i,min;
min=0;
for(i=0;i<SIZE;i++)//The page with least frequency is selected as victim
if(ctr[min]>ctr[i])
min=i;
repptr=min;
return repptr;
}
int Pagerep(int ele)
{
int temp;
repptr=Longestopt();//The victim page is selected with the help of a function
temp=frame[repptr];
frame[repptr]=ele;
ctr[repptr]=1;//A new page is brought, hence it's counter is set to 1
return temp;
}
int Pagefault(int ele)
{if(full!=SIZE)
{ctr[full]++;//The counters will increase initially for all frames till they are full
frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;ctr[i]++;//Whenever a reference is made the counter is incremented
break;
}}
return flag;
}
int main()
{int i;
FILE *fp;
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
if(Search(a[i])!=1)
{Pagefault(a[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n",count);
getche();
return 0;
}
6.MFU
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int ctr[SIZE]={0};
static int f;
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Longestopt()
{int i,max;
max=0;//The increment of counter value here is same as that for of LFU
for(i=0;i<SIZE;i++)//The page with maximum frequency is selected
if(ctr[max]<ctr[i])
max=i;
repptr=max;
return repptr;
}
int Pagerep(int ele)
{
int temp;
repptr=Longestopt();
temp=frame[repptr];
frame[repptr]=ele;
ctr[repptr]=1;
return temp;
}
int Pagefault(int ele)
{if(full!=SIZE)
{ctr[full]++;
frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;ctr[i]++;
break;
}}
return flag;
}
int main()
{int i;
FILE *fp;
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
for(i=0;i<n;i++)
{f=i;
if(Search(a[i])!=1)
{Pagefault(a[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n",count);
getche();
return 0;
}
7.Second Chance Algorithm
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21];//To take the input
int ref[SIZE];//This is for reference bits for each frame
int frame[SIZE];
int repptr=0;//Initialised to first frame
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Pagerep(int ele)
{
int temp;
/*When ever a page needs to be replaced the repptr moves from page to page checking whether it's reference bit is 0 or not, if it is 0 it
coomes out of the while loop and if it is one, it gives a second chance setting the reference bit to 0*/
while(ref[repptr]!=0)
{ ref[repptr++]=0;
if(repptr==SIZE)
repptr=0;
}
temp=frame[repptr];
frame[repptr]=ele;
ref[repptr]=1;//The latest page reference, hence it is set to 1
return temp;
}
int Pagefault(int ele)
{if(full!=SIZE)
{ref[full]=1;//All the ref bits are set to 1 as each frame is being filled firstly
frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;ref[i]=1;//When ever page reference occurs, it's rference bit is set to 1
break;
}}
return flag;
}
int main()
{int n,i;
FILE *fp;
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
if(Search(a[i])!=1)
{Pagefault(a[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n",count);
getche();
return 0;
}
8.Additional Reference Bits Algorithm
#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21];//To take the input
int ref[SIZE];
char r=1;
int frame[SIZE];
unsigned char addref[SIZE]={0};
int repptr=0;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
//For showing bits
int bitrep(char f)//Program for showing the bits
{char p,fl;
int j;
char i=1;
for(j=7;j>=0;j--)
{p=i<<j;
fl=p&f;
if(fl==0)
printf("0");
else
printf("1");
}
printf("\n");
}
//For showing bit wise
int additionalreference()
{
int i,min;
min=0;
for(i=1;i<SIZE;i++)
if(addref[min]>addref[i])//Finding the smallest decimal value from all the strings available
min=i;
repptr=min;
return repptr;
}
int Pagerep(int ele)
{
int temp;
repptr=additionalreference();
temp=frame[repptr];
frame[repptr]=ele;
ref[repptr]=1;
return temp;
}
int Pagefault(int ele)
{if(full!=SIZE)
{ref[full]=1;
frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
flag=0;
if(full!=0)
{
for(i=0;i<full;i++)
if(ele==frame[i])
{ flag=1;ref[i]=1;
break;
}}
return flag;
}
int main()
{int n,i,k;
r=r<<7;
bitrep(r);
FILE *fp;
fp=fopen("Input.txt","r");
printf("The number of elements in the reference string are :");
fscanf(fp,"%d",&n);
printf("%d",n);
for(i=0;i<n;i++)
fscanf(fp,"%d",&a[i]);
printf("\nThe elements present in the string are\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n\n");
for(i=0;i<n;i++)
{
if(Search(a[i])!=1)
{Pagefault(a[i]);
display();
count++;
}
printf("\nThe values in shift registers related to three frames are\n");
//Shifing of registers
for(k=0;k<SIZE;k++)
{
addref[k]=addref[k]>>1;//Shifting all the shift registers by one bit
if(ref[k]==1)
{ addref[k]=(r|addref[k]);//Bit OR operation for shifting
ref[k]=0;
}
bitrep(addref[k]);
}
//End of shifting
}
printf("\nThe number of page faults are %d\n",count);
getche();
return 0;
}
Which one is inexpensive implementation of LRU, stack or counter?
ReplyDelete#include
ReplyDeleteint 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;imax)
{
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=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;
}
}
}
RSA Algorithm
ReplyDeleteRequirements for Message Authentication Codes
Socket Class and ServerSocket Class
Specular Reflection
Types of thread
Thread modes
Testing Object-Oriented Applications
Operating System
.Net Technology
ReplyDeleteWhat is Symbol Table
What is Subroutine
Bit Stuffing and Byte Stuffing
80386 Special Register
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
ReplyDeletewebsite: geeksforgeeks.org
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
ReplyDeletewebsite: geeksforgeeks.org
A Computer Science portal for geeks. It contains well written, well thought and well
ReplyDeleteexplained computer science and programming articles, quizzes and practice/competitive
programming/company interview Questions.
website: geeksforgeeks.org
A Computer Science portal for geeks. It contains well written, well thought and well
ReplyDeleteexplained computer science and programming articles, quizzes and practice/competitive
programming/company interview Questions.
website: geeksforgeeks.org