LRU algorithm implementation 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&lt;iostream&gt;
using namespace std;

int max(int r[],int n)
{
    int pos,i,l,max=0;
    for(i=0;i&lt;n;i++)
    {
        if(r[i]&gt;max)
        {
            l=r[i];
            max=r[i];
            pos=i;
        }
    }
    return pos;
}

void read(int a[],int n)
{
    int i;
    for(i=0;i&lt;n;i++)
    {
        cin&gt;&gt;a[i];
    }
}

void display(int b[],int n)
{
    int i;
    for(i=0;i&lt;n;i++)
    {
        cout&lt;&lt;b[i]&lt;&lt;" ";
    }
}

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&lt;&lt;"Enter number of frames: ";
    cin&gt;&gt;n;
    for(i=0;i&lt;20;i++)
    {
        pg[i]=-1;
    }
    cout&lt;&lt;"Enter the number of pages:";
    cin&gt;&gt;m;
    cout&lt;&lt;"Enter the reference string: ";
    read(rs,m);
    int pos;
    tmr[0]=2;
    tmr[1]=1;
    tmr[2]=0;
    for(i=0;i&lt;m;i++)
    {
        for(j=0;j&lt;n;j++)
        {
            if(pg[j]==-1)
            {
                pg[j]=rs[i];
                avail=1;
                pf++;
                cout&lt;&lt;"This page "&lt;&lt;rs[i]&lt;&lt;" is PLACED in the frame "&lt;&lt;j&lt;&lt;endl;
                break;  
            }
            else
            {
                if(pg[j]==rs[i])
                {
                    pos=j;
                    timer_confg(tmr,pos);
                    avail=1;
                    cout&lt;&lt;"This page "&lt;&lt;rs[i]&lt;&lt;" is already in the frame "&lt;&lt;j&lt;&lt;endl;
                    break;
                }

                else
                {
                    if(avail==0 || j==(n-1))
                    {
                        pos=max(tmr,n);
                        pg[pos]=rs[i];
                        pf++;
                        timer_confg(tmr,pos);
                        cout&lt;&lt;"The page "&lt;&lt;rs[i]&lt;&lt;" is replaced with frame "&lt;&lt;pos&lt;&lt;endl;
                        break;  
                    }
                }   
            }   
        }
    }
    cout&lt;&lt;"The total number of page fault is:"&lt;&lt;pf;
    return 0;
}
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(...)