FIFO页面置换算法C程序错误排查：输出结果异常问题

问题描述 #

输入页框数3、页面序列41245时，程序出现两个核心问题：

1. 页面5未正确替换页框1的内容
2. 页错误数（Page Faults）和页面命中数（Page Hits）计算错误

错误点分析 #

1. 页错误数无差别累加

原代码中无论页面是否命中，都会执行pFaults++;，导致命中时页错误数也被错误增加。正确逻辑是仅当页面未命中时才递增页错误数。

2. FIFO替换索引逻辑混乱

原代码依赖错误累加的pFaults计算替换位置，同时初始化阶段的pFaults <= frameno && pHits == 0条件不合理——若中间出现命中，该条件会失效，无法正常填充页框。正确做法是用独立指针跟踪FIFO替换位置。

3. 初始化阶段判断冗余

原代码中额外判断pHits == 0完全不必要，只需判断页框是否有空位即可完成初始化填充。

修正后的代码 #

#include <stdio.h>

int main() {
    int frameno, pageno, pHits = 0, pFaults = 0;
    int fifo_ptr = 0; // 独立指针跟踪FIFO替换位置

    printf("\nEnter Page Frame: ");
    scanf("%d", &frameno);

    printf("\nEnter Pages: ");
    scanf("%d", &pageno);

    printf("Enter string: ");

    int p, i;
    char temp[frameno], pageref[pageno];

    // 初始化页框为占位符'-'
    for (i = 0; i < frameno; i++) {
        temp[i] = '-';
    }

    // 读取页面序列
    for (p = 0; p < pageno; p++) {
        scanf(" %c", &pageref[p]);
    }

    // 打印表头
    printf("\nPage Requested \t ");
    for (i = 0; i < frameno; i++) {
        printf("Page Frame %d \t", i + 1);
    }

    for (p = 0; p < pageno; p++) {
        int pageFound = 0;

        // 检查当前页面是否命中
        for (i = 0; i < frameno; i++) {
            if (pageref[p] == temp[i]) {
                pHits++;
                pageFound = 1;
                break;
            }
        }

        // 处理页错误逻辑
        if (!pageFound) {
            pFaults++;
            // 判断页框是否已满
            int isFull = 1;
            for (i = 0; i < frameno; i++) {
                if (temp[i] == '-') {
                    isFull = 0;
                    break;
                }
            }
            if (!isFull) {
                // 页框未满，填充到当前指针位置
                temp[fifo_ptr] = pageref[p];
                fifo_ptr++;
            } else {
                // 页框已满，执行FIFO替换
                temp[fifo_ptr] = pageref[p];
                fifo_ptr = (fifo_ptr + 1) % frameno;
            }
        }

        // 打印当前页面请求与页框状态
        printf("\n%c\t", pageref[p]);
        for (i = 0; i < frameno; i++) {
            if (temp[i] != '-') {
                printf("\t\t %c", temp[i]);
            } else {
                printf(" \t\t");
            }
        }
    }

    printf("\nPage Faults: %d\t", pFaults);
    printf("\nPage Hits: %d\t", pHits);

    return 0;
}

修正后输出示例 #

Enter Page Frame: 3

Enter Pages: 5
Enter string: 41245

Page Requested 	 Page Frame 1 	 Page Frame 2 	 Page Frame 3 
4			 4
1			 4		 	 1
2			 4		 	 1		 	 2
4			 4		 	 1		 	 2
5			 5		 	 1		 	 2
Page Faults: 4	
Page Hits: 1	

内容的提问来源于stack exchange，提问作者kd yoon