C 训练营教程

主题

Lesson 57: 缓存模拟器 LRU 2路组相联 ​

练习任务 ​

难度：中

实现一个 2 路组相联 (2-way set-associative) 缓 缓存模拟器，使用 LRU (Least Recently Used) 替换策略。你需要完成六个核心函数：

  1. init_cache() — 初始始化所有 8 个缓存行为无效状态，重置全局时间戳
  2. find_lru(set) — 在指定组内找 LRU 行，优先返回空行，否则返回时间戳最小的有效行
  3. access(addr) — 模拟一次次缓存访问，返回 "hit" / "miss" / "evict"
  4. 主循环调用 init_cache() — 初始化缓存
  5. 主循环遍历地址序列 — 输出每次访问的 set/tag/result，统计命中次数
  6. 命中率统计 — 输出总访问次数、命中数、未命中数、命中率

get_set(addr) 和 get_tag(addr) 地址分解函数已提供。

本课共有 1 组测试用例，通过 make test 编译运行后用 diff 比对预期输出：

make test

提示：缓存的本质是一个"记忆"系统——记住最近访问过的数据。2路组相联 = 每个数据块按 set 索引"分宿舍楼"，每个宿舍楼只有 2 个床位。LRU 决定踢谁：踢那个"最久没回来"的同学。思考方向：find_lru 为什么必须先检查无效行？access 中 timestamp 递增的位置为什么必须在函数开头？

核心知识点 ​

  • 缓存层次与局部性原理 — CPU-缓存-主存的速度鸿沟，时间局部性与空间局部性如何弥合差距
  • 三种映射方式对比 — 直接映射(专属行位)、全相联(任意放置)、组相联(折中方案)，各自的硬件代价与缺失率权衡
  • 2路组相联缓存结构 — CacheLine 三个字段(valid/tag/lru_ts)的语义，静态二维数组 cache[4][2] 的物理布局
  • 地址划分公式推导 — 8位地址 [tag:2b|set:2b|offset:4b] 的完整推导：从地址 → 块号 → set/tag 的两步整数运算
  • LRU时间戳替换策略 — 全局 timestamp 每次访问递增，lru_ts 记录最后一次访问时刻，替换时选组内最小时间戳
  • find_lru 的两步优先逻辑 — 先扫描无效行(优先利用空位) → 再比较时间戳(找真正最久未用的)，避免不必要的驱逐
  • access 命中/缺失/冲突缺失三分法 — 命中忘记更新 lru_ts、缺失填充空行(miss)、缺失替换有效行(evict)的完整判断流程
  • 冷缺失 vs 冲突缺失 — miss 和 evict 的本质区别：前者是第一次访问(不可避免)，后者是容量限制导致的争用(可通过增加相联度优化)
  • 命中率浮点计算陷阱 — (100.0 * hits) / n 而非 (100 * hits) / n，整数除法的截断问题

代码框架 ​

57_cache_sim_lru.c
c
#include <stdbool.h>
#include <stdio.h>

#define NUM_SETS 4
#define WAYS 2
#define BLOCK_SIZE 16

/* ─── Cache line structure ─── */
typedef struct {
    bool valid; /* 有效位：该行是否包含有效数据 */
    int tag;    /* 标记：标识数据块的高位地址 */
    int lru_ts; /* 时间戳：最后一次访问的全局时间 */
} CacheLine;

static CacheLine cache[NUM_SETS][WAYS];
static int timestamp = 0;

/* ─── 地址分解 (已提供) ─── */
static int get_set(int addr) { return (addr / BLOCK_SIZE) % NUM_SETS; }
static int get_tag(int addr) { return (addr / BLOCK_SIZE) / NUM_SETS; }

/* ──── TODO 1: 初始化缓存 ─── */
#error TODO: Implement init_cache()
/*
 * static void init_cache(void) { ... }
 *
 * 遍历 NUM_SETS × WAYS:
 *   将每个 cache[s][w].valid 设为 false
 *   将 tag 和 lru_ts 设为 0
 * 将全局 timestamp 重置为 0
 */

/* ─── TODO 2: 在组内找 LRU 行 ─── */
#error TODO: Implement find_lru(int set)
/*
 * static int find_lru(int set) { ... }
 *
 * 1. 先扫描无效行 (valid == false) → 直接返接返回该 way 索引
 * 2. 若所有行都有效 → 扫描找 lru_ts 最小的行 → 返回其 way 索引
 */

/* ─── TODO 3: 一次缓存访问 ─── */
#error TODO: Implement access(int addr)
/*
 * static const char *access(int addr) { ... }
 *
 * 1. set = get_set(addr), tag = get_tag(addr)
 * 2. timestamp++        ← 全局时间戳递增
 * 3. 遍历组内 WAYS, 若 valid && tag == tag 匹配:
 *      cache[set][w].lru_ts = timestamp; return "hit"
 * 4. 未命中: victim = find_lru(set)
 *    结果 = cache[set][victim].valid ? "evict" : "miss"
 *    填充: valid=true, tag=tag, lru_ts=timestamp
 *    return 结果
 */

int main(void) {
    int addrs[] = {
        0,   16, 32, 48,
        0,   64, 16, 80,
        128, 0,  32, 144
    };
    int n = sizeof(addrs) / sizeof(addrs[0]);

    /* ─── TODO 4: 调用 init_cache() ─── */
#error TODO: Call init_cache() before the main loop.

    printf("=== Cache Simulator (2-way, 4 sets, 16B block) ===\n");
    printf("Address: [tag:2b|set:2b|offset:4b]\n\n");

    /* ─── TODO 5: 主循环 ─── */
#error TODO: Complete the main loop.
    /*
     * int hits = 0;
     * for (int i = 0; i < n; i++) {
     *     int set = get_set(addrs[i]);
     *     int tag = get_tag(addrs[i]);
     *     const char *result = access(addrs[i]);
     *     printf("Access #%2d: addr=%3d  set=%d  tag=%d  %s\n",
     *            i + 1, addrs[i], set, tag, result);
     *     if (result[0] == 'h') hits++;
     * }
     */

    /* ─── TODO 6: 命中率计算 ─── */
#error TODO: Print final statistics.
    /*
     * printf("\n--- Final Stats ---\n");
     * printf("Total accesses: %d\n", n);
     * printf("Hits: %d\n", hits);
     * printf("Misses: %d\n", n - hits);
     * printf("Hit rate: %.1f%%\n", (100.0 * hits) / n);
     */

    return 0;
}

阅读骨架后，尝试自己填充 TODO 1 到 TODO 6 标记的部分。核心挑战在于：access 中何时递增 timestamp？find_lru 为什么必须先检查空行？"evict" 和 "miss" 的判断条件是什么？主循环中如何用 result[0] == 'h' 判断命中？

TIP

先不要往下翻看参考解答。拿纸笔完整追踪地址序列 0, 16, 32, 48, 0, 64, 16, 80, 128, 0, 32, 144 在 2路×4组 缓存中的状态变化。重点关注 Set 0 上 tag 0、1、2 三个地址(0, 64, 128)如何争夺仅有的 2 路。

深度讲解 ​

1. 为什么需要缓存——CPU与主存的速度鸿沟 ​

1.1 存储层次的金字塔 ​

现代计算机系统中，CPU 和内存之间存在巨大的速度差距：

┌─────────┐     ~0.3 ns      ┌─────────┐    ~1 ns       ┌─────────┐    ~50 ns      ┌─────────┐
│  CPU    │ ←──────────→    │  L1 Cache│ ←──────────→   │ L2 Cache │ ←┌───────────→   │  主存   │
│  寄存器  │   寄存器访问     │  (32KB)  │   L1 命中       │  (256KB) │    L2 命中      │  (DRAM) │
└──────────┘                 └─────────┘                 └─────────┘                 └─────────┘
                                  ↑
                            本模拟器的建模对象

如果不使用缓存，CPU 每次取指令和数据都要等待 ~50-100 ns 的内存访问——CPU 大部分时间在"空转"。缓存通过利用程序的访问模式特征来弥合这一差距。

1.2 局部性原理——缓存有效的前提 ​

缓存之所以有效，根本原因是程序行为表现出两种局部性：

时间局部性 (Temporal Locality):
  刚被访问过数据，很可能会再次被访问。
  例子：循环中的变量 i, sum 被反复使用

  for (int i = 0; i < 1000000; i++) {
      sum += arr[i];  // i 和 sum 每次都访问——时间局部性
  }

空间局部性 (Spatial Locality):
  刚被访问的数据附近的数据，很可能即将被访问。
  例子：数组 arr 按顺序遍历

  for (int i = 0; i < 1000000; i++) {
      sum += arr[i];  // arr[0]之后访问arr[1]——空间局部性
  }
缓存在"预测"程序的下一步：
  时间局部性 → 缓存记住最近用过的数据（LRU 的核心动机）
  空间局部性 → 缓存以"块"为单位加载（16B 一次加载）

IMPORTANT

没有局部性原理，缓存完全无效。如果程序随机跳跃访问内存，缓存命中率接近 0%。幸运的是，绝大多数程序（编译器、浏览器、数据库、游戏）都表现出强烈的局部性——这是计算机体系结构设计的"免费午餐"。

2. 缓存的三种映射方式——数据放在哪里？ ​

2.1 直接映射 (Direct-Mapped)：一行专位 ​

每个内存块只能映射到唯一的一个缓存行。

直接映射 (8 行缓存，1 路 × 8 组):

    内存块号          缓存行
   ─────────        ────────
     0, 8,16,24,... →  Set 0 (行 0)
     1, 9,17,25,... →  Set 1 (行 1)
     2,10,18,26,... →  Set 2 (行 2)
     ...

  同组不同 tag 的块访问 → 互相踢出 (冲突缺失!)
优点缺点
硬件简单相联只需 1 个比较器冲突缺失多：同一行的多个块争用
查找快：定位到行后直接比 tag极端情况：交替访问两个同组块 → 100%缺失

2.2 全相联 (Fully Associative)：任意放置 ​

任何内存块可以放在任意缓存行。

全相联 (8 行缓存，8 路 × 1 组):

   所有块映射到同一个大组，可以放在 8 行中任意位置。

   ┌───────────────────────────────────────────┐
   │ Set 0: [Way0] [Way1] [Way2] ... [Way7]   │
   └───────────────────────────────────────────┘

   8 路 × 1 组 = 任意块可放入任意行
优点缺点
冲突缺失最少需要 8 个并行比较器——硬件昂贵
缓存利用率最高查找时需要比较所有行的 tag——功耗大

2.3 组相联 (Set-Associative) —— 本题方案 ​

内存块映射到特定组，组内可以放在任意行。这是直接映射和全相联的折中。

2路组相联 (8 行缓存，2 路 × 4 组):

  ┌───────────────┬───────────────┬───────────────┬───────────────┐
  │    Set 0      │    Set 1      │    Set 2      │    Set 3      │
  │  [Way0][Way1] │  [Way0][Way1] │  [Way0][Way1] │  [Way0][Way1] │
  └───────────────┴───────────────┴───────────────┴───────────────┘
        ↑               ↑               ↑               ↑
   块号 % 4 == 0   块号 % 4 == 1   块号 % 4 == 2   块号 % 4 == 3

  每组 2 路 → 可以同能同时容纳 2 个不同 tag 的块
  第 3 个不同 tag 的块进入同组 → 触发 evict
三种映射方式的关系：

  直接映射                    组相联 (本题)               全相联
  1 路 × 8 组       →        2 路 × 4 组       →        8 路 × 1 组
  ┌─┬─┬─┬─┬─┬─┬─┬─┐     ┌───┬───┬───┬───┐     ┌─────────────────────┐
  │0│1│2│3│4│5│6│7│     │W0W1│W0W1│W0W1│W0W1│     │W0 W1 W2 ... W7    │
  └─┴─┴─┴─┴─┴─┴─┴─┘     └─── └───┴───┴───┘     └─────────────────────┘
  硬件简单              折中：硬件+缺失率平衡          硬件复杂
  冲突缺| 最多                                       冲突缺失少

NOTE

2 路组相联是实际 CPU 中最常见的设计。Intel Core 系列的 L1 数据缓存通常是 8 路组相联，L2 是 16 路——相联度越高，冲突缺失越少，但硬件越贵。2 路是入门级的折中选择。

3. 缓存结构与地址划分——本题的核心数据模型 ​

3.1 CacheLine 结构体的三个字段 ​

cacheline_struct.c
c
typedef struct {
    bool valid; /* 有效位：true=包含有效数据, false=空行 */
    int tag;    /* 标记：标识该行的数据来自哪个内存块(高位地址) */
    int lru_ts; /* 时间戳：最后一次访问的全局时间(LRU排序依据) */
} CacheLine;

static CacheLine cache[NUM_SETS][WAYS];  /* 4 组 × 2 路 = 8 行 */
static int timestamp = 0;                /* 全局时间戳，每次访问+1 */

每个字段的语义：

字段类型初始值何时更新何时读取
validboolfalse填充行时设为 true查找命中时判断空行、判断 evict/miss
tagint0填充行时写入新 tag查找命中：与当前地址的 tag 比较
lru_tsint0每次命中或填充时更新为当前 timestampfind_lru: 比较找最小时间戳

3.2 2路组相联的物理布局 ​

cache_layout.c
c
/* cache[4][2] 的内存视图 */
/*
 * cache[0] = {Way0, Way1}   ← Set 0: 容纳块号 % 4 == 0 的块
 * cache[1] = {Way0, Way1}   ← Set 1: 容纳块号 % 4 == 1 的块
 * cache[2] = {Way0, Way1}   ← Set 2: 容纳块号 % 4 == 2 的块
 * cache[3] = {Way0, Way1}   ← Set 3: 容纳块号 % 4 == 3 的块
 *
 * 寻址方式: cache[s][w]
 *   s = 组号 (0~3)
 *   w = 路号 (0 或 1)
 */
ASCII 可视化：

  Set 0                 Set 1                 Set 2                 Set 3
┌──────┬──────┐  ┌──────┬──────┐  ┌──────┬──────┐  ┌──  ┌───┬──────┐
│Way 0 │Way 1 │  │Way 0 │Way 1 │  │Way 0 │Way 1 │  │Way 0 │Way 1 │
├──────┼──────┤  ├────────┼──────┤  ├──────┼──────┤  ├──────┼──────┤
│v:?   │v:?   │  │v:?   │v:?   │  │v:?   │v:?   │  │v:?   │v:?   │
│tag:? │tag:? │  │tag:? │tag:? │  │tag:? │tag:? │  │tag:? │tag:? │
│ts:?  │ts:?  │  │ts:?  │ts:?  │  │ts:?  │ts:?  │  │ts:?  │ts:?  │
└──────┴──────┘  └──────┴──────┘  └──  └───┴──────┘  └──────┴──────┘

3.3 地址划分公式完整推导 ​

本题使用 8 位地址 (0-255)，被划分为三个字段：

   7   6   5   4   3   2   1   0
┌───┬───┬───┬───┬───┬───┬───┬───┐
│     tag     │    set    │ offset │
│    (2b)     │   (2b)    │  (4b)  │
└─────────────┴───────────┴────────┘

推导过程方式：

步骤 1: 确定 offset 位数
  块大小 BLOCK_SIZE = 16 字节
  需要 log₂(16) = 4 位来区分块内 16 个字节
  → offset 占地址的低 4 位

步骤 2: 确定 set 位数
  组数 NUM_SETS = 4
  需要 log₂(4) = 2 位来区分 4 个组
  → set 占地址的第 4-5 位 (紧接 offset 之后))

步骤 3: 确定 tag  │
  剩余位数 = 8 - 4 - 2 = 2 位
  → tag 占地址的第 6-7 位 (最高 2 位)

代码中的公式验证：

address_decomp.c
c
/* get_set: 提取组索引 */
int set = (addr / BLOCK_SIZE) % NUM_SETS;
// = (addr / 16) % 4
// = (addr >> 4) & 0b11     ← 位操作视角

/* get_tag: 提取标记 */
int tag = (addr / BLOCK_SIZE) / NUM_SETS;
// = (addr / 16) / 4
// = addr / 64
// = addr >> 6               ← 位操作视角
完整示例：
  addr = 128 → 二进制 10000000
                ┌──┬──┬──────┐
                │10│00│ 0000 │
                └──┴──┴──────┘
                tag=2 set=0 offset=0

  验证公式:
    (128 / 16) % 4 = 8 % 4 = 0 → set = 0 ✓
    (128 / 16) / 4 = 8 / 4 = 2 → tag = 2 ✓

3.4 地址映射示例表 ​

地址二进制块号settag映射到
000 00 0000000Set 0
1600 01 0000110Set 1
3200 10 0000220Set 2
4800 11 0000330Set 3
6401 00 0000401Set 0
8001 01 0000511Set 1
12810 00 0000802Set 0
14410 01 0000912Set 1

IMPORTANT

关键观察：地址 0、64、128 都映射到 Set 0，但 tag 分别为 0、1、2。因为 Set 0 只有 2 路，当第三个地址 (tag=2) 访问 Set 0 时必然发生冲突缺失 (evict)。块号 / NUM_SETS 的除法操作使得不同块号产生不同的 tag——这就是为什么 tag 被称为"标记"。

4. LRU 替换策略——踢谁？ ​

4.1 LRU 的核心思想 ​

LRU = Least Recently Used = "最近最少使用"

如果某行很久没有被访问了，它很可能在未来也不会被访问。

这是时间局部性的直接应用：最近被访问的数据将更频繁地被再次访问。

4.2 时间戳实现的完整机制 ​

lru_mechanism.c
c
/*
 * LRU 的时间戳实现：
 *
 * 全局变量 timestamp 在每次 access() 调用时递增。
 * 每个缓存行的 lru_ts 记录该行最后一次被访问(命中或填充)的时刻。
 *
 * 需要替换时，选择组内 lru_ts 最小的行。
 * lru_ts 越小 → 离现在越久 → 最"不近"被用 → 最应该被替换。
 */
时间戳跟踪示例 (Set 0 的演化):

timestamp=1: 访问 addr=0 (tag=0) → 填充 Way0
  Set 0: [Way0: v=1, tag=0, ts=1] [Way1: empty]

timestamp=2: 访问 addr=64 (tag=1) → 填充 Way1
  Set 0: [Way0: v=1, tag=0, ts=1] [Way1: v=1, tag=1, ts=2]

timestamp=3: 访问 addr=0 (tag=0) → 命中 Way0!
  Set 0: [Way0: v=1, tag=0, ts=3] [Way1: v=1, tag=1, ts=2]
  ↑ ts 更新为 3                       ↑ ts 保持 2 ← LRU!

timestamp=4: 访问 addr=128 (tag=2) → 未命中, 找 LRU
  Way0 ts=3, Way1 ts=2 → Way1 是 LRU → 替换 Way1
  Set 0: [Way0: v=1, tag=0, ts=3] [Way1: v=1, tag=2, ts=4]

4.3 find_lru 的两步优先算法 ​

find_lru_algorithm.c
c
/*
 * find_lru(set) — 在组内找要替换的目标行
 *
 * 第一步: 扫描空行 (valid == false)
 *   为什么优先空行？
 *   - 空行没有任何有效数据，填充它不损失信息
 *   - 如果先比较时间戳，可能在空行存在时替换有效行 → 浪费
 *   - "先填满空行，再谈替换"是最优策略
 *
 * 第二步: 所有行都有效 → 扫描找最小 lru_ts
 *   - 记录 min_ts 和对应的 way 索引
 *   - 返回 lru_ts 最小的 way (最久未被访问)
 */
static int find_lru(int set) {
    int victim = 0;
    int min_ts = cache[set][0].lru_ts;

    for (int w = 0; w < WAYS; w++) {
        // 第一步：优先空行
        if (!cache[set][w].valid) {
            return w;  // 直接返回，不比较时间戳
        }
        // 第二步：记录最小时间戳
        if (cache[set][w].lru_ts < min_ts) {
            min_ts = cache[set][w].lru_ts;
            victim = w;
        }
    }
    return victim;
}

CAUTION

如果 find_lru 不先检查无效行，可能会在有空行时错误地替换有效行。例如 Set 中有 Way0 已填充、Way1 为空，若不先检查空行，可能会找 Way0 的时间戳并替换 Way0——而 Way1 明明是空的！

4.4 为什么 timestamp++ 必须在 access 开头？ ​

timestamp_order.c
c
/*
 * ❌ 错误: timestamp++ 放在函数末尾
 */
const char *access_wrong(int addr) {
    /* ... 查找命中 ... */
    if (hit) {
        cache[set][w].lru_ts = timestamp;  // 用的是旧 timestamp!
        timestamp++;  // 太晚了——已经赋值了
        return "hit";
    }
}

/*
 * ✓ 正确: timestamp++ 放在函数开头
 */
const char *access_correct(int addr) {
    timestamp++;  // 先递增，保证本次访问的时间戳比之前都大
    /* ... 查找命中 ... */
    if (hit) {
        cache[set][w].lru_ts = timestamp;  // 用的是新 timestamp ✓
        return "hit";
    }
}
时间戳顺序错误导致的问题：

timestamp=0, 缓存为空

访问 A: timestamp++ → ts=1, 填充 Way0, Way0.ts=1 ✓

如果先填充再 timestamp++:
访问 A: 填充 Way0, Way0.ts=0; timestamp++ → ts=1
  → Way0.ts=0 比真实情况小 → LRU 判断被扭曲

5. access() —3.2 缓存访问的完整流程 ​

5.1 访问流程图 ​

                ┌──────────────────┐
                │  access(addr)    │
                └────────┬─────────┘
                         │
                  ┌──────▼──────┐
                  │ timestamp++ │  ← 全局时间戳递增
                  │ set=get_set │
                  │ tag=get_tag │
                  └──────┬──────┘
                         │
              ┌──────────▼──────────┐
              │ 遍历组内 WAYS        │
              │ if (valid &&        │
              │     tag == tag)     │
              └──────┬─────┬───────┘
                     │     │
                  找到   未找到
                     │     │
              ┌──────▼──┐  │
              │ 更新     │  │
              │ lru_ts   │  │
              │ return   │  │
              │  "hit"   │  │
              └──────────┘  │
                     ┌──────▼──────┐
                     │ find_lru()  │
                     │ → victim    │
                     └──────┬──────┘
                            │
                   ┌────────▼────────┐
                   │ cache[victim]   │
                   │ .valid == true? │
                   └──────────────┬───┘
                       │         │
                      true     false
                       │         │
                 ┌─────▼──┐  ┌──▼────┐
                 │ result │  │result │
                 │"evict" │  │"miss" │
                 └─────┬──┘  └──┬─────┘
                       │         │
                       └────┬────┘
                            │
                   ┌────────▼────────┐
                   │ 填充 victim 行   │
                   │ valid = true    │
                   │ tag = tag       │
                   │ lru_ts=timestamp│
                   │ return result   │
                   └─────────────────┘

5.2 三种返回值的判断逻辑 ​

返回值条件含义性能影响
"hit"组内找到 valid && tag 匹配的nt)缓存命中，数据已在缓存中最佳，~1 cycle
"miss"未命中 + victim 行 valid == false冷缺失，组内还有空位可接受，首次加载
"evict"未命中 + victim 行 valid == true冲突缺失，必须替换有效行最差，有用的数据被踢出
access_return_values.c
c
/*
 * "miss" 和 "evict" 的本质区别：
 *
 * miss  (冷缺失):
 *  - 组内有空行 → 直接填充 → 不损失任何有效数据
 *  - 不能通过增加相联度来消除(第一次访问该块必然缺失)
 *  - 可通过预取(prefetch)缓解
 *
 * evict (冲突缺失):
 *  - 组已满 → 必须踢出一个有效行 → 该行的数据丢失
 *  - 该行将来再次被访问时必定缺失 → 二次惩罚
 *  - 可通过增加相联度来减少
 */

const char *result;
if (cache[set][victim].valid) {
    result = "evict";  /* 替换有效行 → 冲突缺失 */
} else {
    result = "miss";   /* 填充空行 → 冷缺失 */
}

5.3 命中判断的常见陷阱 ​

hit_detection.c
c
/*
 * 主循环中判断命中的正确方式：
 */

/* ✓ 正确: 比较首字母 */
if (result[0] == 'h') hits++;

/* ❌ 错误: 比较整个字符串 */
if (result == "hit") hits++;  // 比较地址，而非内容!
if (strcmp(result, "hit") == 0) hits++;  // 可以，但更慢

/*
 * "hit" 的首字母是 'h'，而 "miss" 和 "evict" 的首字母分别是 'm' 和 'e'
 * 比较 result[0] == 'h' 足以区分命中与非命中
 * 这是一种轻量级的 C 字符串判断技巧
 */

WARNING

在 C 中，result == "hit" 比较的是指针地址而非字符串内容。access() 返回的 "hit" 是字符串字面量的地址，与 "hit"(编译器可能合并同一字面量)的地址相同纯属巧合——依赖这种行为是错误的。始终用 result[0] == 'h' 或 strcmp。

6. 完整逐步追踪——12 次访问的状态演化 ​

6.1 访问序列 ​

access_sequence.c
c
int addrs[] = {
    0,   16, 32, 48,   /* 4 different sets, all cold miss */
    0,   64, 16, 80,   /* hits on 0 and 16, miss on 64 and 80 */
    128, 0,  32, 144   /* evicts on 128, 0, 144; hit on 32 */
};

6.2 逐步状态变化 ​

初始状态 (timestamp = 0):

Set 0: [---: empty] [---: empty]
Set 1: [---: empty] [---: empty]
Set 2: [---: empty] [---: empty]
Set 3: [---: empty] [---: empty]

访问 #1: addr=0, set=0, tag=0 → miss

timestamp=1
Set 0: [tag0 ts=1] [---: empty]  ← 填充 Way0

访问 #2: addr=16, set=1, tag=0 → miss

timestamp=2
Set 1: [tag0 ts=2] [---: empty]

访问 #3: addr=32, set=2, tag=0 → miss

timestamp=3
Set 2: [tag0 ts=3] [---: empty]

访问 #4: addr=48, set=3, tag=0 → miss

timestamp=4
Set 3: [tag0 ts=4] [---: empty]

至此，4 个 set 各有一个 Way0 被填充。前 4 次全部是冷缺失。

访问 #5: addr=0, set=0, tag=0 → hit

timestamp=5
Set 0 Way0 命中 → 更新 ts=5
Set 0: [tag0 ts=5] [---: empty]

访问 #6: addr=64, set=0, tag=1 → miss

timestamp=6
Set 0 Way1 为空 → 填充 Way1
Set 0: [tag0 ts=5] [tag1 ts=6]

访问 #7: addr=16, set=1, tag=0 → hit

timestamp=7
Set 1: [tag0 ts=7] [---: empty]  ← ts 从 2 更新为 7

访问 #8: addr=80, set=1, tag=1 → miss

timestamp=8
Set 1 Way1 为空 → 填充 Way1
Set 1: [tag0 ts=7] [tag1 ts=8]

访问 #9: addr=128, set=0, tag=2 → evict

timestamp=9
Set 0 已满:
  Way0: tag0 ts=5  ← LRU (ts 最小)
  Way1: tag1 ts=6
→ 替换 Way0 → 改为 tag2 ts=9
Set 0: [tag2 ts=9] [tag1 ts=6]

访问 #10: addr=0, set=0, tag=0 → evict

timestamp=10
Set 0 已满:
  Way0: tag2 ts=9
  Way1: tag1 ts=6  ← LRU (ts 最小)
→ 替换 Way1 → 改为 tag0 ts=10
Set 0: [tag2 ts=9] [tag0 ts=10]

访问 #11: addr=32, set=2, tag=0 → hit

timestamp=11
Set 2: [tag0 ts=11] [---: empty]  ← ts 从 3 更新为 11

访问 #12: addr=144, set=1, tag=2 → evict

timestamp=12
Set 1 已满:
  Way0: tag0 ts=7  ← LRU (ts 最小)
  Way1: tag1 ts=8
→ 替换 Way0 → 改为 tag2 ts=12
Set 1: [tag2 ts=12] [tag1 ts=8]

6.3 访问追踪总表 ​

#addr块号settag结果Set 状态变化说明
10000missS0W0←tag0冷缺失：填充空行
216110missS1W0←tag0冷缺失
332220missS2W0←tag0冷缺失
448330missS3W0←tag0冷缺失
50000hitts 更新时间局部性
664401missS0W1←tag1冷缺失：同组不同 tag
716110hitts 更新时间局部性
880511missS1W1←tag1冷缺失
9128802evictS0W0 tag0→tag2冲突缺失：Set 0 第 3 个 tag
100000evictS0W1 tag1→tag0冲突缺失：tag0 回来踢走 tag1
1132220hitts 更新Set 2 未受干扰
12144912evictS1W0 tag0→tag2冲突缺失：Set 1 第 3 个 tag

6.4 最终缓存状态与统计 ​

Set 0: [Way0: tag2 ts=9 ] [Way1: tag0 ts=10]
Set 1: [Way0: tag2 ts=12] [Way1: tag1 ts=8 ]
Set 2: [Way0: tag0 ts=11] [Way1: ---:empty  ]
Set 3: [Way0: tag0 ts=4 ] [Way1: ---:empty  ]

统计:
  Hit:    3 (访问 #5, #7, #11)
  Miss:   6 (访问 #1-#4, #6, #8)
  Evict:  3 (访问 #9, #10, #12)
  Total: 12
  Hit rate: 3/12 = 25.0%

NOTE

6 次冷缺失 + 3 次冲突缺失 + 3 次命中。冷缺失是不可避免的(每个块第一次访问)，冲突缺失是由于 Set 0 和 Set 1 各有 3 个不同 tag 争夺 2 路导致的。如果相联度从 2 增加到 4(4路×2组)，冲突缺失将全部消失，命中率提高到 50%(6/12)。

7. 替换策略对比——LRU vs FIFO vs Random ​

策略原理本题命中率实现复杂度硬件代价优点缺点
LRU替换最久未用的3/12 (25.0%)中需时间戳或链表利用时间局部性实现成本较高
FIFO替换最早进入的3/12 (25.0%)低环形队列实现简单可能替换热点数据
Random随机替换~2-4/12 (不稳定)最低无零状态，无开销命中率不稳定
OPT替换未来最远使用的更高(不可实现)——理论最优需要预知未来
为什么本题中 LRU 和 FIFO 结果相同？

  本题的访问模式恰恰是"先来先被踢"：
    Set 0: tag0(#1) → tag1(#6) → tag2(#9) → tag0(#10)
    
  在 tag0→tag1→tag2 依次进入的顺序中，
  LRU: tag0 的 ts=5, tag1 的 ts=6 → LRU 选 tag0
  FIFO: tag0 最早进入 → FIFO 也选 tag0
  
  两者一致是因为访问模式呈"流水线"式前进。

  但如果是循环访问 (A,B,C,A,B,C,...)：
  LRU 会保留 A,B，踢 C → 命中 A,B ✓
  FIFO 按入队顺序踢，可能踢 A → 再访问 A 时缺失 ✗
replacement_comparison.c
c
/*
 * 循环访问模式下的 LRU vs FIFO 差异：
 *
 * 序列: A, B, C, A, B, C  (2路组相联, 同一组)
 *
 * LRU:
 *   #1: A进入 → Way0: A(ts=1)
 *   #2: B进入 → Way1: B(ts=2)
 *   #3: C进入 → Lru=Way0(A,ts=1) → 替换 → Way0: C(ts=3)
 *           现在: Way0=C(ts=3), Way1=B(ts=2)
 *   #4: A进入 → Lru=Way1(B,ts=2) → 替换 → Way1: A(ts=4)
 *           现在: Way0=C(ts=3), Way1=A(ts=4)
 *   #5: B进入 → Lru=Way0(C,ts=3) → 替换 → Way0: B(ts=5)
 *           现在: Way0=B(ts=5), Way1=A(ts=4)
 *   #6: C进入 → Lru=Way1(A,ts=4) → 替换 → Way1: C(ts=6)
 *       命中: 0/6 = 0% — 即使 LRU 也全缺失 (3个tag争2路)
 *
 * 如果 2路 变 3路: 全部命中!
 */

8. 常见错误与调试 ​

错误后果正确做法
忘记 timestamp++所有行 lru_ts = 0, LRU 退化为"无优先级"每次 access() 开头必须 timestamp++
find_lru() 不先检查无效行可能在有空行时替换有效行先扫描 valid == false, 直接返回
命中后忘记更新 lru_ts热点数据被当成"最久未用"错误替换cache[set][w].lru_ts = timestamp
填充后忘记 valid = true该行视为无效，下次仍 miss填充时设置 valid = true
result == "hit" 字符串比较比较地址而非内容用 result[0] == 'h'
get_set 中先取模再除法得到错误组号先 addr / BLOCK_SIZE 再 % NUM_SETS
命中率 (100 * hits) / n整数除法截断，结果为 0(100.0 * hits) / n
init_cache() 忘记重置 timestamp时间戳从非零开始，干扰 LRUtimestamp = 0
printf 格式 %2d 对齐错误输出与 expected_output.txt 不匹配严格按骨架中的格式输出
common_bugs.c
c
/*
 * 调试技巧：在每次 access 后打印缓存状态
 *
 * 如果命中率不对，先检查以下几点：
 */

/* 调试 1: 验证 find_lru 是否优先空行 */
/* 在 find_lru 开头加 print */
printf("find_lru(set=%d): checking ways...\n", set);

/* 调试 2: 验证 access 是否更新了 lru_ts */
/* 在命中分支加 print */
printf("Hit! Updating cache[%d][%d].lru_ts = %d\n", set, w, timestamp);

/* 调试 3: 验证 evict/miss 判断 */
/* 在填充分支加 print */
printf("%s: filling cache[%d][%d] with tag=%d at ts=%d\n",
       result, set, victim, tag, timestamp);

TIP

如果输出与 expected_output.txt 不一致，用 diff 仔细比对空格和换行。注意 Access #%2d 的 %2d 会在序号为 1-9 时对齐空格。addr=%3d 会在地址小于 100 时在前面补空格。

参考解答 ​

练习1: init_cache )` 初始化缓存
solution_57_cache_sim_init.c
c
#include <stdbool.h>
#include <stdio.h>

#define NUM_SETS 4
#define WAYS 2

typedef struct {
    bool valid;
    int tag;
    int lru_ts;
} CacheLine;

static CacheLine cache[NUM_SETS][WAYS];
static int timestamp = 0;

static void init_cache(void) {
    for (int s = 0; s < NUM_SETS; s++) {
        for (int w = 0; w < WAYS; w++) {
            cache[s][w].valid = false;
            cache[s][w].tag = 0;
            cache[s][w].lru_ts = 0;
        }
    }
    timestamp = 0;
}

int main(void) {
    init_cache();
    /* 验证所有行都是无效的 */
    for (int s = 0; s < NUM_SETS; s++) {
        for (int w = 0; w < WAYS; w++) {
            printf("cache[%d][%d]: valid=%d tag=%d ts=%d\n",
                   s, w, cache[s][w].valid, cache[s][w].tag,
                   cache[s][w].lru_ts);
        }
    }
    printf("timestamp: %d\n", timestamp);
    return 0;
}
/* 预期输出: 所有 8 行的 valid=0, tag=0, ts=0; timestamp=0 */

要点：双重循环遍历所有组和路。timestamp = 0 很关键——如果忘记重置，时间戳会从非零开始。

练习2: find_lru — 找 LRU 行
solution_57_cache_sim_find_lru.c
c
#include <stdbool.h>
#include <stdio.h>

#define NUM_SETS 4
#define WAYS 2

typedef struct {
    bool valid;
    int tag;
    int lru_ts;
} CacheLine;

static CacheLine cache[NUM_SETS][WAYS];

static int find_lru(int set) {
    int victim = 0;
    int min_ts = cache[set][0].lru_ts;

    for (int w = 0; w < WAYS; w++) {
        /* 优先返回无效行 */
        if (!cache[set][w].valid) {
            return w;
        }
        /* 记录最小时间戳 */
        if (cache[set][w].lru_ts < min_ts) {
            min_ts = cache[set][w].lru_ts;
            victim = w;
        }
    }
    return victim;
}

/* 测试 */
int main(void) {
    /* 模拟: Set 0 有 Way0 有效(ts=5) 和 Way1 有效(ts=3) */
    cache[0][0].valid = true;  cache[0][0].lru_ts = 5;
    cache[0][1].valid = true;  cache[0][1].lru_ts = 3;
    printf("LRU in Set 0: Way %d (expected 1)\n", find_lru(0));

    /* 模拟: Set 1 有 Way0 有效(ts=2) 和 Way1 无效 */
    cache[1][0].valid = true;  cache[1][0].lru_ts = 2;
    cache[1][1].valid = false;
    printf("LRU in Set 1: Way %d (expected 1)\n", find_lru(1));
    return 0;
}
/* 预期: Set 0 → Way 1 (ts=3 < ts=5), Set 1 → Way 1 (空行优先) */

要点：先扫描空行直接返回，再比较有效行的时间戳。扫描空行的循环必须在前。

练习3: access — 一次缓存访问
solution_57_cache_sim_access.c
c
#include <stdbool.h>
#include <stdio.h>

#define NUM_SETS 4
#define WAYS 2
#define BLOCK_SIZE 16

typedef struct {
    bool valid;
    int tag;
    int lru_ts;
} CacheLine;

static CacheLine cache[NUM_SETS][WAYS];
static int timestamp = 0;

static int get_set(int addr) { return (addr / BLOCK_SIZE) % NUM_SETS; }
static int get_tag(int addr) { return (addr / BLOCK_SIZE) / NUM_SETS; }

static void init_cache(void) {
    for (int s = 0; s < NUM_SETS; s++)
        for (int w = 0; w < WAYS; w++)
            cache[s][w].valid = false;
    timestamp = 0;
}

static int find_lru(int set) {
    for (int w = 0; w < WAYS; w++)
        if (!cache[set][w].valid) return w;
    int victim = 0;
    for (int w = 1; w < WAYS; w++)
        if (cache[set][w].lru_ts < cache[set][victim].lru_ts)
            victim = w;
    return victim;
}

static const char *access(int addr) {
    int set = get_set(addr);
    int tag = get_tag(addr);
    timestamp++;

    /* 查找命中 */
    for (int w = 0; w < WAYS; w++) {
        if (cache[set][w].valid && cache[set][w].tag == tag) {
            cache[set][w].lru_ts = timestamp;
            return "hit";
        }
    }

    /* 缺失：找 victim 并填充 */
    int victim = find_lru(set);
    const char *result = cache[set][victim].valid ? "evict" : "miss";

    cache[set][victim].valid = true;
    cache[set][victim].tag = tag;
    cache[set][victim].lru_ts = timestamp;
    return result;
}

/* 测试 access 的返回值 */
int main(void) {
    init_cache();
    /* 前 4 次访问应该是 miss */
    printf("addr=0:   %s\n", access(0));
    printf("addr=16:  %s\n", access(16));
    printf("addr=32:  %s\n", access(32));
    printf("addr=48:  %s\n", access(48));
    /* 再次访问 0 应该是 hit */
    printf("addr=0:   %s\n", access(0));
    /* 访问 64(同组不同tag) 应该是 miss */
    printf("addr=64:  %s\n", access(64));
    /* 访问 128(同组第3个tag) 应该是 evict */
    printf("addr=128: %s\n", access(128));
    return 0;
}
/* 预期: miss, miss, miss, miss, hit, miss, evict */

核心逻辑：先递增 timestamp，再查找命中（更新 lru_ts），未命中则调用 find_lru 找 victim，根据 victim 的 valid 状态返回 "evict" 或 "miss"，最后填充 victim 行。

练习4-6: 完整主程序
solution_57_cache_sim_complete.c
c
#include <stdbool.h>
#include <stdio.h>

#define NUM_SETS 4
#define WAYS 2
#define BLOCK_SIZE 16

typedef struct {
    bool valid;
    int tag;
    int lru_ts;
} CacheLine;

static CacheLine cache[NUM_SETS][WAYS];
static int timestamp = 0;

/* 地址分解 */
static int get_set(int addr) { return (addr / BLOCK_SIZE) % NUM_SETS; }
static int get_tag(int addr) { return (addr / BLOCK_SIZE) / NUM_SETS; }

/* 初始化 */
static void init_cache(void) {
    for (int s = 0; s < NUM_SETS; s++)
        for (int w = 0; w < WAYS; w++) {
            cache[s][w].valid = false;
            cache[s][w].tag = 0;
            cache[s][w].lru_ts = 0;
        }
    timestamp = 0;
}

/* 找 LRU 行 */
static int find_lru(int set) {
    for (int w = 0; w < WAYS; w++)
        if (!cache[set][w].valid) return w;
    int victim = 0;
    for (int w = 1; w < WAYS; w++)
        if (cache[set][w].lru_ts < cache[set][victim].lru_ts)
            victim = w;
    return victim;
}

/* 缓存访问 */
static const char *access(int addr) {
    int set = get_set(addr);
    int tag = get_tag(addr);
    timestamp++;

    for (int w = 0; w < WAYS; w++) {
        if (cache[set][w].valid && cache[set][w].tag == tag) {
            cache[set][w].lru_ts = timestamp;
            return "hit";
        }
    }

    int victim = find_lru(set);
    const char *result = cache[set][victim].valid ? "evict" : "miss";

    cache[set][victim].valid = true;
    cache[set][victim].tag = tag;
    cache[set][victim].lru_ts = timestamp;
    return result;
}

int main(void) {
    int addrs[] = {
        0,   16, 32, 48,
        0,   64, 16, 80,
        128, 0,  32, 144
    };
    int n = sizeof(addrs) / sizeof(addrs[0]);

    /* TODO 4: 初始化缓存 */
    init_cache();

    printf("=== Cache Simulator (2-way, 4 sets, 16B block) ===\n");
    printf("Address: [tag:2b|set:2b|offset:4b]\n\n");

    /* TODO 5: 主循环 */
    int hits = 0;
    for (int i = 0; i < n; i++) {
        int addr = addrs[i];
        int set = get_set(addr);
        int tag = get_tag(addr);
        const char *result = access(addr);

        printf("Access #%2d: addr=%3d  set=%d  tag=%d  %s\n",
               i + 1, addr, set, tag, result);

        if (result[0] == 'h') hits++;
    }

    /* TODO 6: 命中率统计 */
    printf("\n--- Final Stats ---\n");
    printf("Total accesses: %d\n", n);
    printf("Hits: %d\n", hits);
    printf("Misses: %d\n", n - hits);
    printf("Hit rate: %.1f%%\n", (100.0 * hits) / n);

    return 0;
}

核心逻辑解析：

  1. 地址分解 get_set/get_tag：先除 BLOCK_SIZE 得块号，再取模/整除 NUM_SETS 得 set/tag。这是组相联的经典地址划分方式。
  2. init_cache: 将所有 valid 设为 false，tag 和 lru_ts 设为 0，timestamp 重置为 0。缓存从"空白"状态开始。
  3. find_lru：先找空行（优先利用空位），再找 lru_ts 最小的有效行。空行优先是性能关键——避免不必要的驱逐。
  4. access：先递增 timestamp（保证本次操作的时间戳比之前都大），再查命中，最后处理缺失（判断 evict/miss 并填充）。三种返回值的语义清晰。
  5. 命中率：(100.0 * hits) / n —— 用 100.0 而非 100 强制浮点除法。

对照检查：init_cache 中重置了 timestamp 吗？find_lru 先检查了无效行吗？access 中 timestamp++ 在函数开头吗？命中后更新了 lru_ts 吗？主循环用 result[0] == 'h' 判断命中吗？命中率用 100.0 而非 100 了吗？

课堂讨论 ​

  1. 如果把相联度从 2 增加到 4（4路×2组），本题的命中率会如何变化？代价是什么？
  2. find_lru 中如果写成"先比较时间戳、再检查空行"，结果会怎样？在什么场景下会产生错误？
  3. 假设地址序列中所有地址都是 16 的倍数（offset=0），那么 16B 的块大小还有意义吗？
  4. 真实 CPU 中的 LRU 如何高效实现？时间戳方案有什么工程问题？
  5. 如果地址宽度从 8 位扩展到 32 位（缓存其他参数不变），get_set 和 get_tag 公式需要修改吗？

讨论答案 ​

Q1: 相联度从 2 增加到 4 的影响

从 2路×4组 变为 4路×2组：

原配置(2路×4组):                   新配置(4路×2组):
┌───┬───┬───┬───┐                ┌─────────┬─────────┐
│S0 │S1 │S2 │S3 │                │   S0    │   S1    │
│W0W1│W0W1│W0W1│W0W1│                │W0W1W2W3│W0W1W2W3│
└───┴───┴───┴───┘                └─────────┴─────────┘

新的地址划分: [tag:3b|set:1b|offset:4b]

命中率变化：

  • 前 4 次：依然 miss（冷缺失不变）
  • 第 5 次 (addr=0): hit ✓（不变）
  • 第 6 次 (addr=64): miss，但此时 Set 0 有 4 路，可以容纳 tag 0 和 tag 1
  • 第 9 次 (addr=128): miss 而非 evict！Set 0 有 4 路，tag 0,1,2 各占一角
  • 第 10 次 (addr=0): hit！tag 0 在 Set 0 中 ✓
  • 第 12 次 (addr=144): miss 而非 evict！
  • 命中率: 6/12 = 50.0%（原来 25.0%）

代价：

  • 硬件：每组需要 4 个并行比较器（原来 2 个），功耗增加
  • 更长的 tag 比较延迟：4 路比较比 2 路慢（虽仍并行）
  • 不完全是"更好"——需要权衡性能提升和硬件成本
Q2: find_lru 顺序错误的影响

如果先比较时间戳，再检查空行：

c
/* ❌ 错误顺数取模 */
static int find_lru_wrong(int set) {
    int victim = 0;
    int min_ts = cache[set][0].lru_ts;

    for (int w = 0; w < WAYS; w++) {
        if (cache[set][w].lru_ts < min_ts) {
            min_ts = cache[set][w].lru_ts;
            victim = w;
        }
    }
    /* 后检查空行——太晚了！ */
    for (int w = 0; w < WAYS; w++) {
        if (!cache[set][w].valid) return w;
    }
    return victim;
}

错误场景：

Set 状态: [Way0: valid, tag=0, ts=5] [Way1: empty, ts=0]

先比较时间戳: Way1.ts=0 < Way0.ts=5 → victim=1
后检查空行: victim 恰好是空行 → "碰巧"对应

但如果不是碰巧：
Set 状态: [Way0: empty, ts=0] [Way1: valid, tag=1, ts=5]

先比较时间戳: Way0.ts=0 < Way1.ts=5 → victim=0
但如果是另一种情况时空行 ts 更大就不对了。

实际上空行的 ts 初始值是 0（init_cache 中设置），而有效行的 ts 都 ≥ 1（访问后才填充），所以空行的 ts=0 碰巧是最小的。

但这是"脏巧合"——如果先"装"了某个有效行填了 ts，再遇到另一个空行，空行 ts=0 仍是最小的，但语义上我们想优先空行。

关键：正确顺序（先空行后时间戳）在语义上是清晰的——"优先利用空位"是独立于时间戳的策略。

Q3: offset=0 时块大小的意义

即使所有地址的 offset 都是 0（是 16 的倍数），16B 的块大小仍然影响整个缓存的组织：

块大小 = 16B:
  block_number = addr / 16 → 块号 0,1,2,3,4,5,8,9
  set = block_number % 4
  tag = block_number / 4

如果块大小改为 8B:
  block_number = addr / 8 → 块号 0,2,4,6,8,10,16,18
  offset = 3b, set = 3b, tag = 2b
  → 地址划分完全不同！
  → set 的计算结果不同
  → 映射到不同的组
  → 可能导致原本不冲突的地址发生冲突（或反之）

根本原因：BLOCK_SIZE 是 get_set 和 get_tag 公式的一部分。块大小决定了块号的计算基址，进而影响 set 和 tag。改变块大小会重组整个缓存映射。

Q4: 真实 CPU 的 LRU 实现

时间戳方案（本题方法）的工程问题：

  1. 时间戳宽度：真实 CPU 处理数十亿次访问，时间戳需要 64 位——每个缓存行浪费 64 bit
  2. 比较开销：找 LRU 需要比较组内所有行的时间戳——O(WAYS) 比较器
  3. 溢出处理：时间戳总有溢出的一天——需要 wraparound 机制

真实方案：

二叉树 LRU (Tree-based LRU):
  对于 N 路组相联，只需 N-1 个 bit
  
  2路组相联: 只需 1 bit!
    bit=0 → Way0 是 LRU
    bit=1 → Way1 是 LRU
    每次访问 Way0 → bit=1 (Way1 变 LRU)
    每次访问 Way1 → bit=0 (Way0 变 LRU)
    
  4路组相联: 只需 3 个 bit
          [root]
         /      \
      [L]        [R]
     /   \      /   \
   W0    W1   W2    W3
   
   每个 bit 指向子 缓存中 LRU 的方向

伪 LRU (Pseudo-LRU)：对 4 路以上的实现，用近似 LRU 减少状态位。

NRU (Not Recently Used)：每一行 1 bit（"近期是否被访问"）"，只区分"用过"和"没用过"——极粗糙但最高效。

Q5: 32 位地址需要修改公式吗？

不需要修改公式，但需要理解变化：

c
/* 公式保持不变，只是数据类型可能改变 */
static int get_set(int addr) { return (addr / BLOCK_SIZE) % NUM_SETS; }
static int get_tag(int addr) { return (addr / BLOCK_SIZE) / NUM_SETS; }

变化的是地址划分方式：

8 位地址:  [tag:2b|set:2b|offset:4b]
32 位地址: [tag:26b|set:2b|offset:4b]

tag 从 2 位 → 26 位（因为地址中除了 set 和 offset 剩下的都是 tag）
但这不影响公式——公式由 BLOCK_SIZE 和 NUM_SETS 决定，与地址宽度无关。

需要注意的点：

  • int 类型足够存放 32 位地址的 tag（最大 2^26 = 67M，在 32 位 int 范围内）
  • 对于 64 位地址，int 可能溢出——需要用 long long
  • 逻辑完全相同——组相联的优雅之处：地址宽度不影响映射逻辑

课后练习 ​

  1. 修改块大小。将 BLOCK_SIZE 从 16 改为 8，重新计算地址划分（offset/set/tag 各占几位），预测命中率的变化。用修改后的代码验证你的预测。

    知识点提示：块大小改变 → 地址划分改变 → 不同的地址可能映射到不同 group。关注地址 0、64、128 的 set 和 tag 在新划分下各自是什么，以及它们是否仍然冲突。

    参考解答
    ex1_block_size_8.c
    c
    #define BLOCK_SIZE 8  /* 改为 8B/块 */

/* 新地址划分: [tag:3b|set:2b|offset:3b]
 * offset: log2(8) = 3 位
 * set:    log2(4) = 2 位
 * tag:    8-3-2 = 3 位
 */

    关键影响：addr=0, 16, 32, 48 的块号变化 set 变化 → 映射到不同 group。原本分散在 4 个组的地址现在可能集中到更少的组。预测需要逐地址重新计算 set/tag。

  2. 实现 FIFO 替换策略。修改 CacheLine 结构体，用 fifo_order 替换 lru_ts（记录该行进入缓存的顺序）。重写 find_lru 为 find_fifo（找最早进入的行），比较同一地址序列下 FIFO 和 LRU 的输出差异。

    知识点提示：FIFO 不需要全局时间戳，而是用一个递增的"入驻编号"。填充行时记录编号，替换时找最小编号。观察在循环访问模式 (A,B,C,A,B,C) 下 FIFO 和 LRU 的行为差异。

    参考解答
    ex2_fifo_replacement.c
    c
    /* FIFO 的 CacheLine 结构 */
typedef struct {
    bool valid;
    int tag;
    int fifo_order;  /* 入驻编号，越小=越早进入 */
} CacheLine;

static int order_counter = 0;  /* 全局入驻编号 */

/* FIFO 替换：找最早进入的行 */
static int find_fifo(int set) {
    for (int w = 0; w < WAYS; w++)
        if (!cache[set][w].valid) return w;

    int victim = 0;
    for (int w = 1; w < WAYS; w++)
        if (cache[set][w].fifo_order < cache[set][victim].fifo_order)
            victim = w;
    return victim;
}

/* access 中填充时记录入驻编号 */
cache[set][victim].fifo_order = order_counter++;

/* 注意：命中时不更新 fifo_order！这是与 LRU 的核心区别 */

  3. 缓存状态快照函数。编写 void print_cache(void) 函数，在每次访问后打印整个缓存的状态（所有 Set 的所有 Way 的 valid/tag/ts）。用于调试和可视化缓存行为。

    知识点提示：格式化输出每个 Set 的两个 Way，用分隔线区分组。关注输出格式的可读性——用 [#] 表示空行，用 [tag=N ts=M] 表示有效行。

    参考解答
    ex3_print_cache.c
    c
    static void print_cache(void) {
    for (int s = 0; s < NUM_SETS; s++) {
        printf("Set %d:", s);
        for (int w = 0; w < WAYS; w++) {
            if (cache[s][w].valid) {
                printf(" [tag=%-2d ts=%-2d]", cache[s][w].tag,
                       cache[s][w].lru_ts);
            } else {
                printf(" [----- empty -----]");
            }
        }
        printf("\n");
    }
    printf("timestamp: %d\n", timestamp);
}

/* 用法：在 access 的 return 之前调用 */
static const char *access(int addr) {
    /* ... 原有逻辑 ... */
    print_cache();  /* 每次访问后打印状态 */
    return result;
}

    这个函数是缓存调试的利器——有了它，你可以逐次观察访问如何改变缓存状态，验证 LRU 是否正确选择 victim。

  4. 实现缓存的性能统计增强。在现有命中率统计的基础上，单独统计 miss 和 evict 的次数（不合并为 Misses）。输出分为 "Cold misses" 和 "Conflict misses" 两行。

    知识点提示：在主循环中增加 misses 和 evicts 计数器，根据 result 的首字母判断并累加。注意："Cold miss" 不完全等于 miss（因为容量缺失也算 miss），但本题的简单模型中这已经足够。

    参考解答
    ex4_enhanced_stats.c
    c
    int main(void) {
    /* ... init_cache, printf header ... */

    int hits = 0, misses = 0, evicts = 0;
    for (int i = 0; i < n; i++) {
        /* ... access ... */

        if (result[0] == 'h') hits++;
        else if (result[0] == 'e') evicts++;
        else misses++;  /* "miss" starts with 'm' */
    }

    printf("\n--- Final Stats ---\n");
    printf("Total accesses: %d\n", n);
    printf("Hits: %d\n", hits);
    printf("Cold misses: %d\n", misses);     /* 填充空行 */
    printf("Conflict misses (evicts): %d\n", evicts); /* 替换有效行 */
    printf("Total misses: %d\n", misses + evicts);
    printf("Hit rate: %.1f%%\n", (100.0 * hits) / n);
    return 0;
}

    这种细分统计在实际缓存性能分析中非常有用：冷缺失多 → 增加块大小或预取；冲突缺失多 → 增加相联度。

  5. 不同相联度比较。扩展程序，通过修改 #define WAYS 为 1（直接映射）和 4（4路组相联），分别运行相同的地址序列，对比三种相联度下的命中率和缺失分布。

    知识点提示：直接映射(WAYS=1)时每组只有 1 路，同一 set 的不同 tag 必然相互冲突。4路(WAYS=4)时每组可以容纳 4 个不同 tag，理论上冲突缺失最少。注意组数也随之变化（总行数 8 固定）。

    参考解答
    ex5_way_comparison.c
    c
    /*
 * WAYS=1, NUM_SETS=8 (直接映射):
 *   Set = block_number % 8
 *   Tag  = block_number / 8
 *   预期: 更多 evict (每组只有 1 路)
 *
 * WAYS=2, NUM_SETS=4 (本题):
 *   命中率 25.0%
 *
 * WAYS=4, NUM_SETS=2 (4路组相联):
 *   Set = block_number % 2
 *   Tag  = block_number / 2
 *   预期: 更多 hit (每组 4 路)
 *
 * 核心修改: #define WAYS 和 #define NUM_SETS
 * 保持 WAYS * NUM_SETS = 8 (总行数不变)
 */

    这是理解组相联本质的最佳方式——在固定总容量的情况下，观察相联度和组数的权衡如何影响缺失率。

参考资料 ​

  • Hennessy & Patterson, Computer Architecture: A Quantitative Approach, 6th ed., Chapter 2 — 存储器层次设计：缓存、替换策略、缺失分类的完整理论框架
  • Bryant & O'Hallaron, Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 6 — 存储器层次结构：从程序员视角理解缓存的局部性原理与性能模型
  • Tanenbaum, Structured Computer Organization, 6th ed., Chapter 4 — 存储器层次：组相联缓存的硬件实现细节与设计权衡
  • Wikipedia: CPU cache — 缓存映射、替换策略、写策略的百科综述
  • Wikipedia: Cache replacement policies — LRU、FIFO、Random 等替换策略的详细对比
  • Agner Fog, The microarchitecture of Intel, AMD and VIA CPUs — 真实 CPU 缓存参数的测量数据与性能优化指南

"The memory hierarchy is the most important architectural innovation in the history of computing." — John L. Hennessy

Released under the MIT License.

Copyright © 2026-present OpenCamp C Team