LRU页面置换算法C＃ [英] LRU Page Replacement algorithm C#
问题描述
我试图写一个函数来模拟LRU页面替换。我的理解LRU pretty的很好，但我有问题对其进行编码。下面的事情被传递到LRU功能。用户指定的＃的1-9存储在称为用户输入的帧的数目（1-7）尺寸20的refString的阵列存储在变量numFrames的20字符引用字符串。最后，大小7称为帧的阵列中传递。
下面是code我有，而我得到一个接近一些，但不大。也许有人可以帮帮忙！
私有静态无效LRU（INT numFrames，INT [] refString，INT []帧）
{
INT I，J = 0，K，M，标志= 0，计数= 0，顶端= 0;
对于（I = 0; I＆小于20;我+ +）
{
对于（K = 0; K＆LT; numFrames; k ++）
{
如果（帧[K] == refString [I]）
{
标志= 1;
打破;
}
}
如果（J = numFrames和放大器;！＆安培;！标志= 1）
{
框架[顶] = refString [I]
J ++;
如果（j！= numFrames）
{
顶级++;
}
}
其他
{
如果（旗！= 1）
{
对于（K = 0; K＆LT;顶; k ++）
{
框架[K] =帧[K + 1];
}
框架[顶] = refString [I]
}
如果（标志== 1）
{
对于（M = K，M＆LT;顶; M +）
{
框架[M] =帧[M + 1];
}
框架[顶] = refString [I]
}
}
如果（旗== 0）
{
算上++;
}
其他
{
标志= 0;
}
}
Console.WriteLine（页面错误与LRU的\ n此号码是：+计）;
}
有在code几个误区： -
如果（前＆LT; numFrames）
{
框架[顶++] = refString [I]
故障++;
}
在这里，你从来不检查，如果目前的refString [我]已经在帧[]因为在你DONOT得到过错，不应在帧中添加它。这种情况下，
下面是一个伪code可以帮助你清楚你的疑惑： -
无效LRU（INT numframes，INT refString []，int的帧[]）{
INT顶= 0，故障= 0;
INT *计数=新INT [numframes]
的for（int i = 0; I＆LT; refString.length;我++）{
INT K = findmax（refString [我]，框架，计数，顶部，numframes）;
如果（K＆小于0）{
算上[顶] = 0;
帧[顶++] = refString [I]
故障++;
}
否则如果（帧[k]的！= refString [I]）{
算上[K] = 0;
帧[K] = refString [I];
故障++;
}
否则算[K] = 0;
对于（INT J = 0; J＆LT;顶; J ++）{
算上[J] ++;
}
}
返回（故障）;
}
INT findmax（INT关键帧，诠释帧[]，诠释计数，诠释之上，诠释numframes）{
INT最大= 0;
的for（int i = 0; I＆LT;顶;我++）{
如果（帧[我] ==关键帧）{
返回（我）;
}
如果（计数[MAX]＆LT;计数[我]）
最大=我;
}
如果（前＆LT; numframes）
返程（-1）;
返回（最大）;
}
编辑：
伪code解释： -
1。检查当前请求的帧缓存中，如果是，则获得它的索引
2.如果帧是present然后将其计数到零，以指示它是用来最近，更高的计数越最近最少帧被使用。
3.如果帧不是present在高速缓存中，然后
一个。检查缓存已满，如果新的框架不会增加缓存的结束并增加故障和缓存的顶部
湾否则，如果蔡斯客满，得到帧最大计数（LRU帧），并用新的框架替换和复位计数为零和增量故障。
4.增量的种种罪状
5.做1到4，直到所有的请求的结束
6.输出无故障
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);
}
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
这篇关于LRU页面置换算法C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
