LRU缓存模拟器运行异常求助：仅显示首个输入值，其余为0

我正在实现一个基于LRU替换策略的简易缓存模拟器，但输入引用字符串后，缓存仅显示第一个输入的数值，其余位置均为0，无法按照LRU策略正确添加数据。

代码 #

package cacheProject;

import java.util.Scanner;
public class cacheProject {

   private int numBlocks;
   private int setAssoc;
   private String replacementPolicy;
   public cacheProject(int numBlocks, int setAssoc, String replacementPolicy) {
       this.numBlocks = numBlocks;
       this.setAssoc = setAssoc;
       this.replacementPolicy = replacementPolicy;
   }
   public void simulate(int[] references) {
       int missRate = 0;
       int hits = 0;
       int[] cache = new int[numBlocks];
       for (int i = 0; i < references.length; i++) {
           int block = references[i];
           // check if block is in cache
           boolean inCache = false;
           for (int j = 0; j < cache.length; j++) {
               if (cache[j] == block) {
                   inCache = true;
                   hits++;
                   break;
               }
           }
           // if not in cache, add it
           if (!inCache) {
               missRate++;
               // if cache is full, remove LRU block
               if (cache[numBlocks - 1] != 0) {
                   int lruBlock = findLRUBlock(cache);
                   cache[lruBlock] = 0;
               }
               // add new block to cache
               for (int j = 0; j < cache.length; j++) {
                   if (cache[j] == 0) {
                       cache[j] = block;
                       break;
                   }
               }
           }
       }
       System.out.println("Miss rate: " + (double) missRate / references.length);
       System.out.println("Hits: " + hits);
       System.out.println("Cache contents:");
       for (int i = 0; i < cache.length; i++) {
           System.out.print(cache[i] + " ");
       }
       System.out.println();
   }
   public int findLRUBlock(int[] cache) {
       if (replacementPolicy.equals("LRU")) {
           int lruBlock = 0;
           int lruTime = Integer.MAX_VALUE;
           for (int i = 0; i < cache.length; i++) {
               int time = 0;
               for (int j = 0; j < cache.length; j++) {
                   if (cache[i] == cache[j]) {
                       time++;
                   }
               }
               if (time < lruTime) {
                   lruBlock = i;
                   lruTime = time;
               }
           }
           return lruBlock;
       }
       return -1;
   }
   public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       System.out.print("Enter number of cache blocks: ");
       int numBlocks = in.nextInt();
       System.out.print("Enter set associativity (1=direct mapped, 2=2-way, 4=4-way): ");
       int setAssoc = in.nextInt();
       System.out.print("Enter replacement policy (FIFO or LRU): ");
       String replacementPolicy = in.next();
       cacheProject cache = new cacheProject(numBlocks, setAssoc, replacementPolicy);
       System.out.println("Enter reference string:");
       String input = in.next();
       String[] references = input.split(" ");
       int[] refs = new int[references.length];
       for (int i = 0; i < references.length; i++) {
           refs[i] = Integer.parseInt(references[i]);
       }
       cache.simulate(refs);
   }
}

实际输出 #

Enter number of cache blocks: 5
Enter set associativity (1=direct mapped, 2=2-way, 4=4-way): 1
Enter replacement policy (FIFO or LRU): LRU
Enter reference string:
3 4 3 5 4 3 5
Miss rate: 1.0
Hits: 0
Cache contents:
3 0 0 0 0

预期输出 #

Enter number of cache blocks: 5
Enter set associativity (1=direct mapped, 2=2-way, 4=4-way): 1
Enter replacement policy (FIFO or LRU): LRU
Enter reference string:
3 4 3 5 4
Miss rate: 1.0
Hits: 0
Cache contents:
3 4 3 5 4

问题原因与修复 #

1. 引用字符串读取错误 #

Scanner.next()只会读取空格前的第一个字符串，导致输入的多值引用串仅被读取第一个数值，后续数据全部丢失。修改main方法中的读取逻辑：

System.out.println("Enter reference string:");
in.nextLine(); // 消耗之前nextInt()留下的换行符
String input = in.nextLine();
String[] references = input.split(" ");

2. LRU核心逻辑错误 #

原findLRUBlock方法通过统计缓存块值的重复次数判断LRU，完全违背了LRU（最近最少使用）的核心逻辑——需要跟踪每个缓存块的最近使用时间戳。修复后的simulate方法：

public void simulate(int[] references) {
    int missCount = 0;
    int hitCount = 0;
    int[] cache = new int[numBlocks];
    int[] lastUsedTime = new int[numBlocks]; // 记录每个块的最后使用时间
    int currentTime = 0;

    for (int i = 0; i < references.length; i++) {
        currentTime++;
        int block = references[i];
        boolean inCache = false;
        int hitIndex = -1;

        // 检查缓存命中
        for (int j = 0; j < cache.length; j++) {
            if (cache[j] == block) {
                inCache = true;
                hitCount++;
                hitIndex = j;
                break;
            }
        }

        if (inCache) {
            // 命中时更新该块的使用时间
            lastUsedTime[hitIndex] = currentTime;
        } else {
            missCount++;
            int emptyIndex = -1;
            // 寻找空缓存块
            for (int j = 0; j < cache.length; j++) {
                if (cache[j] == 0) {
                    emptyIndex = j;
                    break;
                }
            }

            if (emptyIndex != -1) {
                // 有空位直接放入
                cache[emptyIndex] = block;
                lastUsedTime[emptyIndex] = currentTime;
            } else {
                // 无空位时找LRU块（时间戳最小的）
                int lruIndex = 0;
                int minTime = Integer.MAX_VALUE;
                for (int j = 0; j < lastUsedTime.length; j++) {
                    if (lastUsedTime[j] < minTime) {
                        minTime = lastUsedTime[j];
                        lruIndex = j;
                    }
                }
                // 替换LRU块
                cache[lruIndex] = block;
                lastUsedTime[lruIndex] = currentTime;
            }
        }
    }

    // 输出结果
    System.out.println("Miss rate: " + (double) missCount / references.length);
    System.out.println("Hits: " + hitCount);
    System.out.println("Cache contents:");
    for (int val : cache) {
        System.out.print(val + " ");
    }
    System.out.println();
}

3. 缓存满的判断逻辑错误 #

原代码通过cache[numBlocks - 1] != 0判断缓存是否已满，仅适用于顺序填充场景，若中间有空位（替换后）会判断错误。修复后改为先寻找空位，找不到再执行替换逻辑，无需额外判断缓存状态。

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