1

LRU ページ置換をシミュレートする関数を作成しようとしています。私は LRU をよく理解していますが、コーディングに問題があります。次のものが LRU 関数に渡されます。ユーザーは、サイズ 20 の refString という配列に格納されている # の 1 ～ 9 の 20 文字の参照文字列を指定します。ユーザーが入力したフレーム数 (1 ～ 7) は、変数 numFrames に格納されます。最後に、frame と呼ばれるサイズ 7 の配列が渡されます。

これが私が持っているコードです。近い数を取得していますが、完全ではありません。多分誰かが助けることができます！

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);
}
4

1 に答える 1

2

あなたのコードにはいくつかのエラーがあります: -

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

ここでは、現在の refString[i] がすでに frame[] にあるかどうかを確認することはありません。その場合、エラーが発生せず、フレームに追加しないでください。

疑問を解消するのに役立つ疑似コードを次に示します。

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);
}

編集：

擬似コードの説明:-

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
于 2013-11-22T04:57:13.883 に答える