C语言Cache模拟器运行异常：命中数过低求排查

我为学习需求用C语言实现了一款Cache模拟器，无需实际存储数据，仅需统计hit（命中）、miss（未命中）和eviction（驱逐）次数。输入参数包括s（组索引位数）、E（每组行数）、b（块偏移位数），输入的trace文件格式为“操作符 地址, 大小”，操作符分为“L”（加载）、“S”（存储）、“M”（加载+存储）。

给定示例：

L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evicts:3

我的模拟器始终输出错误结果，多数情况下命中数远低于预期。请问我的计算逻辑是否存在问题？

附上实现代码：

#include "cache lab.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <getopt.h>

// Cache line structure
typedef struct {
    int valid;   // Valid bit
    int tag;     // Tag field
    int lru;     // LRU counter
    // Additional fields for data, depending on the cache structure
} CacheLine;

// Cache structure
typedef struct {
    int sets;        // Number of sets
    int lines;       // Number of lines per set
    int block_size;  // Block size (in bytes)
    CacheLine *cache; // Cache array
} Cache;

// Initialize the cache
void initCache(Cache *cache) {
    // Allocate memory for the cache array
    cache->cache = (CacheLine *)malloc(cache->sets * cache->lines * sizeof(CacheLine));

    // Initialize cache lines
    for (int i = 0; i < cache->sets * cache->lines; i++) {
        cache->cache[i].valid = 0;
        cache->cache[i].tag = 0;
        cache->cache[i].lru = 0;
    }
}

// Simulate a cache access
void accessCache(Cache *cache, char operation, unsigned address, int size, int *hits, int *misses, int *evicts) {
    int set_index = (address / cache->block_size) % cache->sets;
    int tag = address / (cache->block_size * cache->sets);

    // Check for a cache hit
    for (int i = 0; i < cache->lines; i++) {
        int index = set_index * cache->lines + i;

        if (cache->cache[index].valid && cache->cache[index].tag == tag) {
            // Cache hit
            (*hits)++;
            cache->cache[index].lru = 0;  // Reset LRU counter

            // For modify (M) operations, we count it as a hit and a miss
            if (operation == 'M') {
                (*misses)++;
            }

            return;
        }
    }

    // Cache miss
    (*misses)++;

    // Find an empty line or evict the least recently used line
    int lru_index = set_index * cache->lines;
    for (int i = 1; i < cache->lines; i++) {
        int index = set_index * cache->lines + i;
        if (!cache->cache[index].valid) {
            lru_index = index;
            break;
        } else if (cache->cache[index].lru > cache->cache[lru_index].lru) {
            lru_index = index;
        }
    }

    // Check if eviction is needed
    if (cache->cache[lru_index].valid) {
        (*evicts)++;
    }

    // Update the cache line
    cache->cache[lru_index].valid = 1;
    cache->cache[lru_index].tag = tag;
    cache->cache[lru_index].lru = 0;  // Reset LRU counter

    // Update LRU counters
    for (int i = 0; i < cache->lines; i++) {
        int index = set_index * cache->lines + i;
        if (index != lru_index) {
            cache->cache[index].lru++;
        }
    }
}

int main(int argc, char *argv[]) {
    int opt;
    int s = 0, b = 0, E = 0;
    char *t;

    // Parse command-line options
    while ((opt = getopt(argc, argv, "s:b:E:t:")) != -1) {
        switch (opt) {
            case 's':
                s = atoi(optarg);
                break;
            case 'b':
                b = atoi(optarg);
                break;
            case 'E':
                E = atoi(optarg);
                break;
            case 't':
                t = optarg;
                

                break;
            default:
                fprintf(stderr, "Usage: %s -s <s> -b <b> -E <E> -t <t>\n", argv[0]);
                exit(EXIT_FAILURE);
        }
    }

    FILE *pfile = fopen(t, "r");
    char operation;
    unsigned address;
    int size;

    // Check if required options are provided
    if (s == 0 || b == 0 || E == 0) {
        fprintf(stderr, "Missing required options. Usage: %s -s <s> -b <b> -E <E>\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    // Calculate the number of lines in each set (cache associativity)
    int lines_per_set = 1 << E;

    // Cache configuration
    Cache cache;
    cache.sets = 1 << s;
    cache.lines = lines_per_set;
    cache.block_size = 1 << b;

    // Cache statistics
    int hits = 0;
    int misses = 0;
    int evicts = 0;

    // Initialize the cache
    initCache(&cache);

    // Simulate cache accesses based on the trace file
    while (fscanf(pfile, " %c %x, %d", &operation, &address, &size) > 0) {
        accessCache(&cache, operation, address, size, &hits, &misses, &evicts);
    }
    fclose(pfile);

    // Output cache statistics
    printSummary(hits, misses, evicts);

    // Free allocated memory
    free(cache.cache);

    return 0;
}

核心问题分析 #

你的代码存在几个关键逻辑错误，直接导致命中数统计异常：

1. M操作统计逻辑完全错误 #

M操作代表加载+存储，正确规则是：

• 若加载命中，存储必然命中，应统计为2次hit
• 若加载miss，加载触发1次miss，后续存储命中，应统计为1次miss + 1次hit

但你的代码在hit分支中对M操作执行(*misses)++，把本该统计为hit的操作算成miss，直接拉低命中数。

2. 组内行数计算错误 #

E参数本身就是每组行数，你却用int lines_per_set = 1 << E;左移计算，导致每组行数翻倍，缓存结构完全错误，大量命中被误判为miss。正确写法应为int lines_per_set = E;。

3. Hit后的LRU更新不完整 #

发生hit时，你仅重置当前行的LRU为0，但未对同组内其他有效行的LRU进行递增，导致LRU顺序混乱，后续替换时错误选择非最久未使用的行，引发不必要的eviction和miss。

4. LRU更新未过滤无效行 #

在miss后的LRU更新中，你对同组所有行（包括未使用的无效行）递增LRU，这会导致无效行的LRU值异常，干扰后续空行判断和替换逻辑。

修正后的关键代码片段 #

修正M操作统计与Hit后的LRU更新 #

// Check for a cache hit
for (int i = 0; i < cache->lines; i++) {
    int index = set_index * cache->lines + i;

    if (cache->cache[index].valid && cache->cache[index].tag == tag) {
        // Cache hit
        (*hits)++;
        // M操作额外统计一次hit
        if (operation == 'M') {
            (*hits)++;
        }
        // 更新LRU：重置当前行，其他有效行递增
        cache->cache[index].lru = 0;
        for (int j = 0; j < cache->lines; j++) {
            int j_index = set_index * cache->lines + j;
            if (j_index != index && cache->cache[j_index].valid) {
                cache->cache[j_index].lru++;
            }
        }
        return;
    }
}

修正每组行数计算 #

// 原错误代码
// int lines_per_set = 1 << E;
// 修正后
int lines_per_set = E;

修正Miss后的LRU更新逻辑 #

// Update LRU counters
for (int i = 0; i < cache->lines; i++) {
    int index = set_index * cache->lines + i;
    if (index != lru_index && cache->cache[index].valid) {
        cache->cache[index].lru++;
    }
}

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