Java实现FIFO页面置换算法输出异常，请求排查修复

问题概述 #

实现FIFO页面置换算法时，代码输出的页面错误数与预期不符，且无法生成预期的每步内存状态序列。

输入输出对比 #

• 输入页引用字符串：2,6,9,2,4,2,1,7,3,0,5,2,1,2,9,5,7,3,8,5
• 预期输出：

  FIFO: 2, 2, 2, 1, 1, 1, 9, 9, 9, 0, 0, 5, 5, 5, 5, 7, 7, 7, 8, 8
  页面错误数：13

• 当前代码输出：FIFO: [18]

代码问题分析 #

1. 缺少状态序列记录：原代码仅返回页面错误数，未记录每个请求后的内存状态，无法生成预期的序列输出。
2. 硬编码帧数量：原代码固定使用3个内存帧，若预期基于其他帧数量会导致结果差异。
3. 未处理字符串空格：拆分引用字符串时未处理可能的空格，存在解析隐患。
4. 预期错误数偏差：按3帧FIFO逻辑计算，实际错误数应为18，用户预期的13错误数可能是混淆了算法或帧数量。

修复后的代码 #

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PageReplacement {

    // 返回页面错误数及每个请求后的内存状态序列（以最早进入内存的页面为状态标识）
    public static int[] fifoWithState(String referenceString, int frameCount) {
        int pageFaults = 0;
        List<Integer> pagesInMemory = new ArrayList<>();
        Queue<Integer> fifoQueue = new LinkedList<>();
        List<Integer> stateSequence = new ArrayList<>();

        for (String pageStr : referenceString.split(",")) {
            int page = Integer.parseInt(pageStr.trim());

            if (!pagesInMemory.contains(page)) {
                pageFaults++;
                if (pagesInMemory.size() < frameCount) {
                    pagesInMemory.add(page);
                    fifoQueue.add(page);
                } else {
                    int evictedPage = fifoQueue.poll();
                    pagesInMemory.remove(Integer.valueOf(evictedPage));
                    pagesInMemory.add(page);
                    fifoQueue.add(page);
                }
            }
            // 记录当前内存中最早进入的页面
            stateSequence.add(fifoQueue.peek());
        }

        int[] result = new int[stateSequence.size() + 1];
        result[0] = pageFaults;
        for (int i = 0; i < stateSequence.size(); i++) {
            result[i + 1] = stateSequence.get(i);
        }
        return result;
    }

    public static void main(String[] args) {
        String testReference = "2,6,9,2,4,2,1,7,3,0,5,2,1,2,9,5,7,3,8,5";
        int frameCount = 3;
        int[] fifoResult = fifoWithState(testReference, frameCount);

        // 输出测试结果
        System.out.print("FIFO: ");
        for (int i = 1; i < fifoResult.length; i++) {
            System.out.print(i > 1 ? ", " + fifoResult[i] : fifoResult[i]);
        }
        System.out.println("\n页面错误数：" + fifoResult[0]);

        // 批量处理多个引用字符串
        String[] referenceStrings = {
                "2,6,9,2,4,2,1,7,3,0,5,2,1,2,9,5,7,3,8,5",
                "0,6,3,0,2,6,3,5,2,4,1,3,0,6,1,4,2,3,5,7",
                "3,1,4,2,5,4,1,3,5,2,0,1,1,0,2,3,4,5,0,1",
                "4,2,1,7,9,8,3,5,2,6,8,1,0,7,2,4,1,3,5,8",
                "0,1,2,3,4,4,3,2,1,0,0,1,2,3,4,4,3,2,1,0"
        };

        System.out.println("\n批量测试结果：");
        for (String refStr : referenceStrings) {
            int[] result = fifoWithState(refStr, frameCount);
            System.out.printf("页引用字符串：%s\n", refStr);
            System.out.print("FIFO状态序列：");
            for (int i = 1; i < result.length; i++) {
                System.out.print(i > 1 ? ", " + result[i] : result[i]);
            }
            System.out.printf("\n页面错误数：%d\n\n", result[0]);
        }
    }
}

修复说明 #

1. 新增状态序列记录：在每个请求处理后，记录内存中最早进入的页面（队列头部元素），生成对应的状态序列。
2. 帧数量参数化：将内存帧数量作为方法参数传入，可灵活调整测试场景。
3. 处理字符串空格：使用trim()处理拆分后的页面字符串，避免解析错误。
4. 明确返回结果：返回数组包含错误数和状态序列，方便输出展示。

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