Fifo页面置换无限循环问题

huangapple go评论66阅读模式
英文:

Fifo page replacement infinite loop issue

问题

我正在尝试在C中执行页面替换算法。我编写了下面的代码。我曾经编写过类似的代码,它曾经能够正常工作。但是现在当我尝试重现这段代码时,它进入了一个无限循环。

我检查了用于命中和未命中的for循环,发现它在当前增量无限制的情况下变得稳定。我已经调整了程序一段时间,但似乎没有任何效果。

#include <stdio.h>
#include <stdlib.h>
int n, table[20], fsize, i, j, request[20], arr2[20], current, miss;

void initialize(int arr[], int n) { //将帧条目设置为-1
    for (i = 0; i < n; i++) {
        arr[i] = -1;
    }
}

int isavailable(int arg) { //检查帧表(数组)中是否有可用的条目
    int present = 0;
    for (i = 0; i < fsize; i++) {
        if (table[i] == arg) {
            present = 1;
            break;
        }
    }
    return present;
}

void fifo() { //先进先出
    miss = 0;
    current = -1;
    initialize(table, fsize);
    for (i = 0; i < n; i++) {
        arr2[i] = request[i];
    }
    for (i = 0; i < n; i++) {
        if (isavailable(arr2[i]) == 1) { //命中条件
            printf("命中");
            continue;
        }
        current = (current + 1) % fsize; //在未命中时循环迭代
        table[current] = arr2[i]; //放置在首次输入位置
        miss++;
    }
    printf("总未命中次数:%d", miss);
}

void main() {
    printf("输入请求次数:");
    scanf("%d", &n);
    printf("输入表格大小:"); //读取帧表大小
    scanf("%d", &fsize);
    printf("输入请求:");
    for (i = 0; i < n; i++) {
        scanf("%d", &request[i]); //读取数组中的请求序列
    }
    printf("FIFO:");
    fifo();
    printf("LRU:");
    //lru();
    printf("最佳替换算法:");
    //optimal();
}

编辑:
我提供的输入是:

  • 请求次数:7
  • 表格大小:3
  • 请求:1,3,0,3,5,6,3
英文:

I am trying to do page replacement algorithm in C. I wrote the code below. I have written similar code that had worked below. But now when I try to reproduce the code enters an infinite loop.

I checked the for loop for hit and miss and it becomes stationary while current increments are unlimited. I have been tweaking the program for some time but nothing seems to work.

#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
int n,table[20],fsize,i,j,request[20],arr2[20],current,miss;

void initialize(int arr[],int n){ //set frame entries to -1
    for(i=0;i&lt;n;i++){
        arr[i]=-1;
    }
}

int isavailable(int arg){ //checks if entry is available in frame table (array)
    int present=0;
    for(i=0;i&lt;fsize;i++){
        if(table[i]==arg){
            present=1;
            break;
        }
    }
    return present;
}

void fifo(){ //first in first out
    miss=0;
    current=-1;
    initialize(table,fsize);
    for(i=0;i&lt;n;i++){
        arr2[i]=request[i];
    }
    for(i=0;i&lt;n;i++){
            if(isavailable(arr2[i])==1){ //hit condition
                printf(&quot;Hit&quot;);
                continue;
            }
            current=(current+1)%fsize; //interates in a cycle during miss
            table[current]=arr2[i]; //places in first entered location
            miss++;
    }
    printf(&quot;Total misses: %d&quot;,miss);
}

void main(){
    printf(&quot;Enter number of requests: &quot;);
    scanf(&quot;%d&quot;,&amp;n);
    printf(&quot;Enter table size: &quot;); //reads frame table size
    scanf(&quot;%d&quot;,&amp;fsize);
    printf(&quot;Enter requests: &quot;);
    for(i=0;i&lt;n;i++){
        scanf(&quot;%d&quot;,&amp;request[i]); //reads request sequence in array
    }
    printf(&quot;FIFO: &quot;);
    fifo();
    printf(&quot;LRU: &quot;);
    //lru();
    printf(&quot;Optimal: &quot;);
    //optimal();
    
}

Edit:-
The input i gave are:-

  • no of requests: 7
  • sizeoftable: 3
  • request: 1,3,0,3,5,6,3

答案1

得分: 1

以下是已翻译的内容:

输入

```lang-none
1,3,0,3,5,6,3

将导致 scanf("&quot;%d&quot;,&amp;request[i]); 在第二次迭代时失败,因为它读取了一个无效的逗号字符“,”。此字符将保留在输入缓冲区中,并导致后续迭代也失败。

只有 request 的第一个元素被赋予用户提交的值,其余元素保持初始化为零(由于静态分配)。

您必须检查 scanf 的返回值是否是期望的转换数。在这里,我们要转换一个整数(%d),所以我们检查返回值是否为 1(或取反来检查错误)。

if (1 != scanf("&quot;%d&quot;, &amp;request[i])) {
   /* 处理这个问题。
    * 一个基本的方法:
    fprintf(stderr, "无效的输入!\n");
    exit(1);
    */
}

%d 跳过前导空格,因此输入

1 3 0 3 5 6 3

更适合于这个格式符。


fifo函数和对isavailable的嵌套调用中都使用全局变量i作为循环条件,这会导致该值在10之间来回跳动(给定的输入),因此永远不会达到n

解决方法是使用更多具有局部作用域的变量,以便函数不会相互干扰。

下面是一个重构后的示例。

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_ALLOC 32

static void panic(const char *fmt, ...)
{
	va_list args;
	va_start(args, fmt);
	vfprintf(stderr, fmt, args);
	va_end(args);
	exit(EXIT_FAILURE);
}

static int contains(int *array, size_t length, int value)
{
	for (size_t i = 0; i < length; i++)
		if (value == array[i])
			return 1;

	return 0;
}

static size_t fifo(size_t tsize, const int *requests, size_t rsize)
{
	int pages[tsize];

	for (size_t i = 0; i < tsize; i++)
		pages[i] = -1;

	size_t miss = 0;

	for (size_t i = 0, offset = 0; i < rsize; i++) {
		if (contains(pages, tsize, requests[i]))
			continue;

		pages[offset++ % tsize] = requests[i];
		miss++;
	}

	return miss;
}

int main(void)
{
	size_t rsize = 0;
	size_t tsize = 0;

    printf("输入请求的数量:");
    if (1 != scanf("%zu", &rsize))
		panic("无效的 `rsize` 格式。\n");

    printf("输入表格大小:");
    if (1 != scanf("%zu", &tsize))
		panic("无效的 `tsize` 格式。\n");

	if (!rsize || rsize > MAX_ALLOC || !tsize || tsize > MAX_ALLOC)
		panic("不良大小(`rsize`:%zu)(`tsize`:%zu)[1,%d]\n",
				rsize, tsize, MAX_ALLOC);

	int requests[rsize];

    printf("输入请求:");
	for (size_t i = 0; i < rsize; i++)
        if (1 != scanf("%d", &requests[i]))
			panic("无效的请求(%zu)", i + 1);

    printf("FIFO: %zu misses\n", fifo(tsize, requests, rsize));
}
输入请求的数量:7
输入表格大小:3
输入请求:1 3 0 3 5 6 3
FIFO: 6 misses
英文:

An input of

1,3,0,3,5,6,3

will cause scanf(&quot;%d&quot;,&amp;request[i]); to fail on the second iteration when it reads an invalid character of ,. This character will be left in the input buffer, and will cause subsequent iterations to also fail.

Only the first element of request is given a user-submitted value, the rest remain zero-initialized (due to static allocation).

You must check the return value of scanf is the expected number of conversions. Here we want to convert one integer (%d), so we check for a return value of 1 (or the inverse to check for error).

if (1 != scanf(&quot;%d&quot;, &amp;request[i])) {
   /* Handle this problem.
    * A basic way:
    fprintf(stderr, &quot;Invalid input!\n&quot;);
    exit(1);
    */
}

%d skips leading whitespace, so the input

1 3 0 3 5 6 3

is more appropriate for the specifier.


Using the global variable i as a for the loop condition in both fifo and the nested call to isavailable causes the value to ping-pong between 1 and 0 (with the given input), thus never reaching n.

The solution is to use more locally scoped variables, so that functions do not interfere with each other.

Here is a refactored example.

#include &lt;stdarg.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_ALLOC 32

static void panic(const char *fmt, ...)
{
	va_list args;
	va_start(args, fmt);
	vfprintf(stderr, fmt, args);
	va_end(args);
	exit(EXIT_FAILURE);
}

static int contains(int *array, size_t length, int value)
{
	for (size_t i = 0; i &lt; length; i++)
		if (value == array[i])
			return 1;

	return 0;
}

static size_t fifo(size_t tsize, const int *requests, size_t rsize)
{
	int pages[tsize];

	for (size_t i = 0; i &lt; tsize; i++)
		pages[i] = -1;

	size_t miss = 0;

	for (size_t i = 0, offset = 0; i &lt; rsize; i++) {
		if (contains(pages, tsize, requests[i]))
			continue;

		pages[offset++ % tsize] = requests[i];
		miss++;
	}

	return miss;
}

int main(void)
{
	size_t rsize = 0;
	size_t tsize = 0;

    printf(&quot;Enter number of requests: &quot;);
    if (1 != scanf(&quot;%zu&quot;, &amp;rsize))
		panic(&quot;Invalid `rsize` format.\n&quot;);

    printf(&quot;Enter table size: &quot;);
    if (1 != scanf(&quot;%zu&quot;, &amp;tsize))
		panic(&quot;Invalid `tsize` format.\n&quot;);

	if (!rsize || rsize &gt; MAX_ALLOC || !tsize || tsize &gt; MAX_ALLOC)
		panic(&quot;Bad size(s) (`rsize`: %zu) (`tsize`: %zu) [1, %d]\n&quot;,
				rsize, tsize, MAX_ALLOC);

	int requests[rsize];

    printf(&quot;Enter requests: &quot;);
	for (size_t i = 0; i &lt; rsize; i++)
        if (1 != scanf(&quot;%d&quot;, &amp;requests[i]))
			panic(&quot;Invalid `request` (%zu)&quot;, i + 1);

    printf(&quot;FIFO: %zu misses\n&quot;, fifo(tsize, requests, rsize));
}
Enter number of requests: 7  
Enter table size: 3
Enter requests: 1 3 0 3 5 6 3
FIFO: 6 misses

huangapple
  • 本文由 发表于 2023年7月17日 19:32:03
  • 转载请务必保留本文链接:https://go.coder-hub.com/76704033.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定