英文:
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<stdio.h>
#include<stdlib.h>
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<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<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<n;i++){
arr2[i]=request[i];
}
for(i=0;i<n;i++){
if(isavailable(arr2[i])==1){ //hit condition
printf("Hit");
continue;
}
current=(current+1)%fsize; //interates in a cycle during miss
table[current]=arr2[i]; //places in first entered location
miss++;
}
printf("Total misses: %d",miss);
}
void main(){
printf("Enter number of requests: ");
scanf("%d",&n);
printf("Enter table size: "); //reads frame table size
scanf("%d",&fsize);
printf("Enter requests: ");
for(i=0;i<n;i++){
scanf("%d",&request[i]); //reads request sequence in array
}
printf("FIFO: ");
fifo();
printf("LRU: ");
//lru();
printf("Optimal: ");
//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(""%d",&request[i]);
在第二次迭代时失败,因为它读取了一个无效的逗号字符“,”。此字符将保留在输入缓冲区中,并导致后续迭代也失败。
只有 request
的第一个元素被赋予用户提交的值,其余元素保持初始化为零(由于静态分配)。
您必须检查 scanf
的返回值是否是期望的转换数。在这里,我们要转换一个整数(%d
),所以我们检查返回值是否为 1
(或取反来检查错误)。
if (1 != scanf(""%d", &request[i])) {
/* 处理这个问题。
* 一个基本的方法:
fprintf(stderr, "无效的输入!\n");
exit(1);
*/
}
%d
跳过前导空格,因此输入
1 3 0 3 5 6 3
更适合于这个格式符。
在fifo
函数和对isavailable
的嵌套调用中都使用全局变量i
作为循环条件,这会导致该值在1
和0
之间来回跳动(给定的输入),因此永远不会达到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("%d",&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("%d", &request[i])) {
/* Handle this problem.
* A basic way:
fprintf(stderr, "Invalid input!\n");
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 <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("Enter number of requests: ");
if (1 != scanf("%zu", &rsize))
panic("Invalid `rsize` format.\n");
printf("Enter table size: ");
if (1 != scanf("%zu", &tsize))
panic("Invalid `tsize` format.\n");
if (!rsize || rsize > MAX_ALLOC || !tsize || tsize > MAX_ALLOC)
panic("Bad size(s) (`rsize`: %zu) (`tsize`: %zu) [1, %d]\n",
rsize, tsize, MAX_ALLOC);
int requests[rsize];
printf("Enter requests: ");
for (size_t i = 0; i < rsize; i++)
if (1 != scanf("%d", &requests[i]))
panic("Invalid `request` (%zu)", i + 1);
printf("FIFO: %zu misses\n", 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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论