LRU Page Replacement algorithm C#

Question

I am trying to write a function which simulates LRU page replacement. I understand LRU pretty well but am having problems coding it. The following things are being passed into the LRU function. The user specifies the 20 character reference string of #'s 1-9 which is stored in an array called refString of size 20. The number of frames the user enters (1-7) is stored in a variable numFrames. Finally, an array of size 7 called frame is passed in.

Here is the code I have, and I am getting a close number but not quite. Maybe someone can help out!

private static void LRU(int numFrames, int[] refString, int[] frame)
{
    int i, j = 0, k, m, flag = 0, count = 0, top = 0;

    for (i = 0; i < 20; i++)
    {
        for (k = 0; k < numFrames; k++)
        {
            if (frame[k] == refString[i])
            {
                flag = 1;
                break;
            }
        }

        if (j != numFrames && flag != 1)
        {
            frame[top] = refString[i];
            j++;

            if (j != numFrames)
            {
                top++;
            }
        }

        else
        {
            if (flag != 1)
            {
                for (k = 0; k < top; k++)
                {
                    frame[k] = frame[k + 1];
                }

                frame[top] = refString[i];
            }

            if (flag == 1)
            {
                for (m = k; m < top; m++)
                {
                    frame[m] = frame[m + 1];
                }

                frame[top] = refString[i];
            }
        }

        if (flag == 0)
        {
            count++;
        }
        else
        {
            flag = 0;
        }

    }

    Console.WriteLine("\nThe number of page faults with LRU is: " + count);
}

Answer 1

There are few errors in your code : -

if (top < numFrames)
        {
            frame[top++] = refString[i];
            fault++;
        }

Here you never check if current refString[i] is already in the frame[] because in that case you donot get fault and should not add it in frame.

Here is an pseudo code that might help you clear your doubts:-

void LRU(int numframes,int refString[],int frames[]) {

   int top = 0,fault=0;
   int* count = new int[numframes];

   for(int i=0;i<refString.length;i++) {

       int k = findmax(refString[i],frames,count,top,numframes);

       if(k<0) {
          count[top] = 0;
          frames[top++] = refString[i];
          fault++;   
       }

       else if(frames[k]!=refString[i]) {

           count[k] = 0;
           frames[k] = refString[i];
           fault++;

       }
      else count[k] = 0;

     for(int j=0;j<top;j++) {
          count[j]++;  

     }

   }

   return(fault);

}


int findmax(int keyframe,int frames[],int count,int top,int numframes) {

     int max = 0;
     for(int i=0;i<top;i++) {

        if(frames[i]==keyframe) {

             return(i);
        }
        if(count[max]<count[i])
            max = i;

     }

     if(top<numframes)
           return(-1);
     return(max);
}

Edit:

Explanation of pseudo code:-

1. check if current requested frame is in cache and if yes then get its index
2. if frame is present then set its count to zero so as to indicate it is used very recently, higher the count the more least recently frame is used.
3. if frame is not present in cache then
   a. check if cache is full if not add new frame to end of cache and increment the fault and top of cache
   b. else if chace is full then get frame with maximum count(LRU frame) and replace it with new frame and reset count to zero and increment fault.
4. increment all the counts
5. do 1 to 4 till end of all requests
6. output the no of faults