LRU algorithm implementation

Question

In this code:

• tmr represents timer array
• n represents number of frames in memory
• m represents number of pages
• rs represents the reference string

There are many functions in this program, but the important one is the timer_confg. This is the function that tests the particular page refereed is least refereed or just refereed. It is used to calculate the timing of the pages. I have designed the function for 3 frames, but if the frames are increased then the cases in the switch statement can be increased. Here 0 means just refereed page and max means maximum from the timer array tmr[] is the least refereed page.

There are other functions for read and display. The max function is used for finding the maximum from the timer which will be used to determine the least refereed page.

This code implements the algorithm using the timer which is maintained by the array tmr[]. The pg[] array denotes the frames in the memory and rs[] denotes the reference string. The rest of the code is about the conditions that will be encountered like:

• when frames are empty
• when the page is already in the memory
• which page needs to be replaced

---

#include<iostream>
using namespace std;
int max(int r[],int n)
{
 int pos,i,l,max=0;
 for(i=0;i<n;i++)
 {
 if(r[i]>max)
 {
 l=r[i];
 max=r[i];
 pos=i;
 }
 }
 return pos;
}
void read(int a[],int n)
{
 int i;
 for(i=0;i<n;i++)
 {
 cin>>a[i];
 }
}
void display(int b[],int n)
{
 int i;
 for(i=0;i<n;i++)
 {
 cout<<b[i]<<" ";
 }
}
void timer_confg(int tmr[],int pos)
{
 int j=pos;
 switch(pos)
 {
 case 0:
 tmr[j]=0;
 tmr[j+1]=tmr[j+1]++;
 tmr[j+2]=tmr[j+2]++;
 break;
 case 1:
 tmr[j]=0;
 tmr[j-1]=tmr[j-1]++;
 tmr[j+1]=tmr[j+1]++;
 break;
 case 2:
 tmr[j]=0;
 tmr[j-1]=tmr[j-1]++;
 tmr[j-2]=tmr[j-2]++;
 break;
 }
}
int main()
{
 int pg[20],tmr[20],i,j,n,pf=0,rs[20],m,avail=0;
 cout<<"Enter number of frames: ";
 cin>>n;
 for(i=0;i<20;i++)
 {
 pg[i]=-1;
 }
 cout<<"Enter the number of pages:";
 cin>>m;
 cout<<"Enter the reference string: ";
 read(rs,m);
 int pos;
 tmr[0]=2;
 tmr[1]=1;
 tmr[2]=0;
 for(i=0;i<m;i++)
 {
 for(j=0;j<n;j++)
 {
 if(pg[j]==-1)
 {
 pg[j]=rs[i];
 avail=1;
 pf++;
 cout<<"This page "<<rs[i]<<" is PLACED in the frame "<<j<<endl;
 break; 
 }
 else
 {
 if(pg[j]==rs[i])
 {
 pos=j;
 timer_confg(tmr,pos);
 avail=1;
 cout<<"This page "<<rs[i]<<" is already in the frame "<<j<<endl;
 break;
 }
 else
 {
 if(avail==0 || j==(n-1))
 {
 pos=max(tmr,n);
 pg[pos]=rs[i];
 pf++;
 timer_confg(tmr,pos);
 cout<<"The page "<<rs[i]<<" is replaced with frame "<<pos<<endl;
 break; 
 }
 } 
 } 
 }
 }
 cout<<"The total number of page fault is:"<<pf;
 return 0;
}

• Incomputable: It seems like your algorithm is part of the user code, is it?
• Nitish Kumar: It is the Lru page replacement algorithm
• Incomputable: Raise compiler warnings level and try to follow guidelines that it gave you. The idea about user code is that user just calls the function or a few of them, and then waits for the output. It seems really strange that user have to iterate through pages, may be you could give it as input and do tricks to maintain lifetime of the array. Try to generalize the code, because for now it has very limited use.

Answer 1

I don't know the LRU Algorithm. So I can't criticize the implementation. The most glaring problems are:

• Undescriptive variable names, like "tmr", "n" and "m".
• Undescriptive procedures, like "max" (max of what? The return value is not the maximum value of the array, but the position).
• The use of "magic" numbers. Like the number 20 for example. Store that number in a descriptive constant.
• The logic of the main procedure.

For example

 else
 {
 if(...)

could be written as such

else if(...)

• Nitish Kumar: Both the ways of declaring else if does two different things. The way it is written is because of the logic.
• tungsten: No, the two ways are exactly identical. See this answer: stackoverflow.com/a/1439944/1237896
• Nitish Kumar: There's a way of doing things and that differs from logic to logic

Answer 2

• Don't pass C-style arrays in C++. They will decay to pointers, which is probably not what you want.

  Instead, replace them with a storage container, such as an std::vector:

  std::vector<int> pg(20);
  

  // pass by const reference
  // r doesn't get modified in the function
  int max(std::vector<int> const& r, int n)
  

  This will also help your code look more C++-like, which is something that is still quite needed here.

• This is quite hard to read:

  int pg[20],tmr[20],i,j,n,pf=0,rs[20],m,avail=0;
  

  You can eliminate i and j by initializing them in the for loops. Since you're still doing this outside of the loops, you really need to transition away from older C programming practices such as these.

  You should also strongly consider declaring or initializing the variables as close their first usages as possible. This will especially make it easier to keep track of variables in the event that any are no longer used and should then be removed.

• You may need to make this more modular so that main() can have much less work to do. It should mostly gather input from the user, call the necessary functions, then display the final results returned by those functions.

  It may also help with simplifying all those conditionals, which do look quite unattractive. With all of that, along with the poor naming, I have no idea what that aspect of the code is supposed to do.