实验四：并发——写一个线程安全的哈希表

先认识你的裁判

第 16 篇讲过：并发 bug 不确定、难复现、测试可能一百次都不出现。所以"跑通了"在这个实验里毫无意义。

ThreadSanitizer 不看你有没有崩，它看有没有发生"两个线程访问同一个地址、至少一个是写、而且没有同步关系”。 只要发生了，不管结果对不对，它都报。

先感受一下：

#include <pthread.h>
#include <stdio.h>
static int shared = 0;
void *w(void *_) { for (int i = 0; i < 1000; i++) shared++; return NULL; }
int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, w, NULL); pthread_create(&b, NULL, w, NULL);
    pthread_join(a, NULL); pthread_join(b, NULL);
    printf("shared = %d\n", shared);
}

gcc -fsanitize=thread -g -O1 -o tsan_demo tsan_demo.c -lpthread && ./tsan_demo

WARNING: ThreadSanitizer: data race (pid=12)
  Read of size 4 at 0xaaaab169007c by thread T2:
    #0 w /lab/tsan_demo.c:4
  Previous write of size 4 at 0xaaaab169007c by thread T1:
    #0 w /lab/tsan_demo.c:4
  Location is global 'shared' of size 4

⭐ 精确到第 4 行，而且告诉你是哪两个线程、谁读谁写。 这就是这个实验的裁判。

⚠️ 代价：TSan 让程序慢 5–15 倍、内存涨 5–10 倍。所以测性能的时候要关掉它，测正确性的时候必须开。两组编译，两个二进制。

环境

docker run --rm -it -v "$PWD:/lab" -w /lab oslab bash

任务

任务一：让它报错

写一个故意不加锁的哈希表（链地址法，1024 个桶，put / get / del），用 8 个线程猛插。

验收：TSan 必须报出竞态。 报不出来说明你的测试没真的并发上——加大线程数和操作数。

⭐ 顺带做一件事：把插入的总数和最后表里的元素数对一下。 你会看到第 16 篇那个"少了一半"的现象在链表上重演——而且这次丢的不是计数，是整条链。

任务二：一把大锁

加一把全局锁。

验收：

1. TSan 零告警。
2. 元素数正确。
3. ⭐ 关掉 TSan，测 1/2/4/8 线程的吞吐——你应该看到第 18 篇那条曲线：加线程反而变慢。 把你的数据和第 18 篇那组对比。

任务三：每桶一把锁

每个桶一把锁。

验收：

1. TSan 零告警。
2. ⭐ 吞吐应该接近线性扩展。如果没有，先想想 1024 个桶够不够 8 个线程分。

⚠️ 然后加一个 resize（扩容）。 这一步会逼出真问题：

• 扩容要动所有的桶——你得按顺序拿所有的锁（第 21 篇的规矩），否则死锁。
• 扩容进行到一半时，别的线程能不能访问？

⭐ 把你的选择和理由写下来。这一题没有标准答案，只有取舍。

任务四：读多写少

加一个"统计元素总数"的接口，被高频调用。

先用最直接的写法（拿锁，遍历所有桶数一遍），测吞吐。你会看到它把前面所有的优化都毁了——因为它要拿所有的锁。

然后用第 18 篇的近似计数器改造它：每线程一个局部计数，攒够阈值再合并。

验收：

1. TSan 零告警。
2. ⭐ 吞吐恢复到接近任务三的水平。
3. 量出你的误差上界，并验证它确实不超过 线程数 × 阈值。

任务五（挑战）：读的时候不加锁

用 stdatomic.h 让 get 完全不加锁。

⚠️ 这一步很难，而且特别容易写出"看起来对"的错代码：

• 你必须理解内存序（memory_order_acquire / release）。
• 你会遇到**“读者正在遍历一条链，写者把节点删了并 free 了”**——这就是 ABA 和内存回收问题。
• ⭐ 真实系统里解决它的办法叫 RCU（读拷贝更新），Linux 内核里到处都是。

验收：TSan 零告警。 ⚠️ 注意 TSan 认识原子操作——如果你用了错误的内存序，它会报出来。⭐ 这就是为什么必须用 TSan 而不是"跑几次试试"：错误的内存序在 arm64 上偶尔出错，在 x86 上可能永远不出错。

交上来的东西

1. 五个版本的代码。
2. 每个版本的 TSan 输出（任务一是有告警，其余是零告警）。
3. 一张吞吐对比表：1/2/4/8 线程 × 五个版本。
4. ⭐ 任务三扩容方案的取舍说明。
5. 任务四的误差实测和上界验证。

自查

• 测性能的二进制是不是关掉 TSan 编译的？（开着测的数字没有意义）
• 有没有跑够长时间？竞态是概率事件。
• ⭐ 有没有在一个核上跑一遍？（--cpuset-cpus=0）有些竞态在多核上很容易出现，有些反而只在单核抢占时出现。