并发与同步

四个线程各自给同一个计数器加一百万次，结果应该是四百万。在这台 Mac 上跑两次：

plain   cnt=1670359 acnt=0 (expect 4000000)
plain   cnt=1530290 acnt=0 (expect 4000000)

不到一半，而且每次都不一样。没有报错，没有崩溃，只是答案错了。这篇从这四百万里丢掉的两百多万次讲起：它们去了哪里，锁为什么能把它们找回来，以及锁本身又会带来什么新问题。

前置：进程异常与信号、虚拟内存

C 例子在 macOS（Apple Silicon，Apple clang 21，pthread）上运行，Python 例子用 /usr/bin/python3（3.9）。

线程：共享地址空间的控制流

进程异常与信号 里的进程有两样东西：一条控制流、一个私有地址空间。线程把它们拆开：一个进程里可以有多条控制流，共享同一个地址空间。每个线程有自己的寄存器、PC 和栈；代码、全局变量、堆、打开的文件都是共享的。

为什么要这样拆？因为进程之间共享数据很麻烦（管道、共享内存都要显式设置），切换还要换页表、冲掉 TLB（虚拟内存）。同一进程的线程切换不换页表，通信只需读写同一个变量。代价正是这篇的主题：共享得太容易了。

在 Linux 上，线程和进程在内核里是同一种东西（task_struct），区别只是 clone 时传了”共享地址空间”的标志。内核调度的单位是线程。xv6 的用户程序没有线程，但内核本身是多核并发运行的，它的锁和 sleep/wakeup 是最干净的教学实现。

Python 有一个特殊情况：CPython 的 GIL 让同一时刻只有一个线程执行字节码，多线程跑纯 Python 计算没有并行加速，但下面讲的竞态在 Python 里一样存在，因为解释器可以在任意两条字节码之间切换线程。GIL 和 free-threaded CPython 的细节在 Python 并发与性能。

竞态：一行 cnt++ 其实是三步

丢掉的计数在汇编里一目了然。让编译器输出 void inc(void){ cnt++; } 的 ARM64 代码：

	adrp	x8, _cnt@GOTPAGE
	ldr	x8, [x8, _cnt@GOTPAGEOFF]
	ldr	x9, [x8]
	add	x9, x9, #1
	str	x9, [x8]
	ret

前两行算出 cnt 的地址，接下来三条才是 cnt++：从内存读到寄存器（ldr）、寄存器加一（add）、写回内存（str）。两个线程交错执行时可能是这样：

时刻	线程 A	线程 B	内存中的 cnt
1	ldr 读到 5		5
2		ldr 读到 5	5
3	add 得 6	add 得 6	5
4	str 写 6		6
5		str 写 6	6

两次加一，结果只多了一。这种”结果取决于线程交错顺序”的 bug 叫竞态条件（race condition）。多个线程同时访问同一内存、至少有一个在写、又没有同步，叫数据竞争（data race）；在 C/C++ 标准里数据竞争直接是未定义行为，编译器可以假设它不存在并做任何优化。

竞态难缠在于它依赖时机：单核上切换不频繁可能跑一千次才错一次，加一行 printf 改变了时序它就消失了。所以不能靠测试证明没有竞态，只能靠设计。

GIL 救不了它。Python 的 n += 1 编译成读、加、写几条字节码，解释器可以在它们之间切换线程。把切换间隔调到很小来放大效果，跑两次：

import threading, sys
sys.setswitchinterval(1e-6)       # 让解释器更频繁地切换线程，放大竞态
n = 0
def work():
    global n
    for _ in range(200000):
        n += 1                    # LOAD / ADD / STORE 三条字节码，中间可被切走
ts = [threading.Thread(target=work) for _ in range(4)]
for t in ts: t.start()
for t in ts: t.join()
print(n, "expected", 800000)

302543 expected 800000
317458 expected 800000

GIL 保证的是解释器内部数据结构不坏，不是你的 Python 代码的原子性。默认切换间隔（5 ms）下丢更新更少见，但不会消失；不同 Python 版本的字节码和切换点也不同，结果会有差异。

关键概念是临界区（critical section）：访问共享数据、必须不被别的线程插进来的那段代码。目标是互斥：同一时刻最多一个线程在临界区里。

停一下，检查理解单选

上面的计数实验里，如果把 4 个线程换成 1 个线程跑 400 万次，结果会是？

一定是 4000000仍然可能少，因为 cnt++ 不是原子的可能少，因为定时器中断会打断 ldr 和 str 之间取决于编译器优化级别

检查答案

互斥锁：先把门关上

最朴素的想法是用一个标志变量当锁：

while (locked) ;     // 等别人释放
locked = 1;          // 自己拿锁

它坏在同一个地方：检查 locked 和设置 locked 之间可以被插进来，两个线程都看到 0、都设成 1、都进了临界区。用软件修补”检查后设置”是一条死胡同（Peterson 算法在现代 CPU 上还会被内存重排打破），真正的解法要硬件帮忙：提供一条原子的读-改-写指令，在一次不可分割的操作里读出旧值并写入新值。x86 的 xchg/lock cmpxchg、ARM 的 ldxr/stxr 对或 swp/cas、RISC-V 的 amoswap 都是这一类。

有了它，自旋锁就是一行：

while (atomic_exchange(&locked, 1) == 1) ;   // 换出来的旧值是 1，说明别人占着
// 临界区
atomic_store(&locked, 0);

xv6 的 acquire() 正是这样，用 __sync_lock_test_and_set 编译成 amoswap。它还做了两件事：拿锁前关中断，因为如果中断处理程序也要拿同一把锁，而中断恰好打在持锁的代码上，处理程序会永远自旋；以及调用 __sync_synchronize() 插内存屏障，阻止编译器和 CPU 把临界区里的读写挪到锁外面（下一节细说）。

自旋锁的问题是等待者一直占着 CPU 空转。临界区很短、持锁者确实在另一个核上跑时，这是最快的；但如果持锁者被调度走了，自旋者就白白烧掉整个时间片。所以用户态程序用的 mutex（pthread_mutex_t、std::mutex、threading.Lock）通常先自旋一小会儿，拿不到就通过系统调用让内核把自己挂起，锁释放时再唤醒。Linux 的 futex 让没有竞争时的加锁解锁完全在用户态完成，只有真正要等待时才进内核。

把计数实验改成加锁，再对比用原子指令直接做加法：

void *locked(void *_){ for (int i=0;i<N;i++){ pthread_mutex_lock(&mu); cnt++; pthread_mutex_unlock(&mu);} return NULL; }
void *atom(void *_){ for (int i=0;i<N;i++) atomic_fetch_add(&acnt,1); return NULL; }

mutex   cnt=4000000 acnt=0 (expect 4000000)
atomic  cnt=0 acnt=4000000 (expect 4000000)

两个都对了。各自计时（4 线程 × 100 万次，-O1）：

mutex  92 ms
atomic 36 ms

原子加法更快，但它只能保护”一个字上的一次操作”。要同时改两个变量（比如从一个账户扣钱、给另一个加钱），或者维护一个链表的若干指针，就只能用锁把整段代码包起来。

锁也会成为瓶颈：所有线程都排队等同一把锁，并行就退化成串行。常见的缓解是缩小临界区、拆成多把细粒度的锁（每个哈希桶一把），或者每线程各自累加、最后合并。这和 分布式系统 里”能不协调就不协调”是同一个思路。

停一下，检查理解单选

xv6 的 acquire() 在自旋拿锁之前要先关闭当前 CPU 的中断，主要是为了防止什么？

防止别的 CPU 同时拿到这把锁防止持锁期间本 CPU 被中断，而中断处理程序又去拿同一把锁，导致自己等自己防止定时器中断导致上下文切换后锁被自动释放关中断能让 amoswap 执行得更快

检查答案

原子操作与内存可见性

上一节说锁要插”内存屏障”，因为现代硬件和编译器都不按你写的顺序执行内存操作。

编译器会重排、合并、甚至删掉它认为没有可见效果的读写。经典的坑：

int ready = 0, data = 0;
// 线程 A                    // 线程 B
data = 42;                   while (!ready) ;
ready = 1;                   printf("%d\n", data);

编译器看线程 B 的循环里没人改 ready，可以把它读一次放进寄存器，循环变成死循环；也可以把线程 A 的两条写换个顺序。CPU 也会重排：每个核有写缓冲区（store buffer），写操作先进缓冲区、稍后才对别的核可见；ARM 这样的弱内存模型还允许读写互相越过。结果是线程 B 可能看到 ready == 1 却读到 data == 0。在 x86 上这段代码碰巧多半”能用”，换到 Apple Silicon 或 ARM 服务器上就坏，这类 bug 经常在移植时才暴露。

volatile 只阻止编译器优化掉读写，不阻止 CPU 重排，也不提供原子性，所以它不是线程同步工具（它的正当用途是 进程异常与信号 里的信号标志和设备寄存器）。

正确的工具是语言提供的原子类型和内存序（C11 <stdatomic.h>、C++ std::atomic）：

• memory_order_relaxed：只保证这个变量本身的读写是原子的，不约束和其它变量的顺序。适合纯计数器，比如前面的 acnt。
• release/acquire：写端用 release 写 ready，保证它之前的所有写（data = 42）先对别人可见；读端用 acquire 读 ready，保证之后的读不会被提前。上面的例子把 ready 换成 atomic_int 并用这对内存序就对了。
• seq_cst（默认）：所有原子操作看起来有一个全局一致的顺序，最直观、开销也最大。

锁本身就内含 acquire/release 语义：lock 是 acquire，unlock 是 release，所以”凡是共享变量都在同一把锁里访问”的程序不需要再想内存序。这也是推荐的默认做法：先用锁，确有性能需要再考虑原子操作，因为无锁代码的正确性极难验证。

另一个和硬件有关的性能坑是伪共享（false sharing）：两个线程写的是不同变量，但它们落在同一个 cache 行里，cache 一致性协议会让这一行在两个核之间来回失效。表现是”没有共享却跑得像有锁”，解法是把每线程数据按 cache 行（64 或 128 字节）对齐隔开。cache 行的细节见 内存层次与缓存。

停一下，检查理解多选

线程 A 执行 data = 42; ready = 1;，线程 B 循环等 ready == 1 后读 data，两个变量都是普通 int。下面哪些说法是对的？

编译器可能把线程 B 对 ready 的读提到循环外，导致死循环在 ARM 上，线程 B 可能看到 ready == 1 但读到旧的 data把两个变量都声明为 volatile 就能在所有 CPU 上保证正确把 ready 改成原子变量，写用 release、读用 acquire，就能保证 B 读到 42

检查答案

条件变量与信号量：等某件事发生

锁解决了”别同时进来”，但线程之间还经常需要”等某个条件成立”：消费者等队列非空，生产者等队列不满，主线程等所有 worker 做完。用锁加轮询（拿锁、看条件、放锁、睡一会、再来）既浪费 CPU 又增加延迟。

条件变量（condition variable）提供两个操作：wait(cv, mutex) 原子地释放锁并睡眠，被唤醒后重新拿锁再返回；signal/notify 唤醒一个（或 broadcast/notify_all 唤醒全部）等待者。“释放锁并睡眠”必须是原子的，否则在放锁和睡下之间别人发的通知会丢失，这就是丢失唤醒问题。xv6 的 sleep(chan, lk) 也是这么设计的：它先拿进程表的锁，再放调用者的锁，保证 wakeup 不可能在两者之间溜过去。

有界缓冲区（生产者-消费者）是标准例子。容量为 2，生产者放 5 个，消费者取 5 个：

import threading, collections
buf, cap = collections.deque(), 2
cv = threading.Condition()
log = []
def producer():
    for i in range(5):
        with cv:
            while len(buf) == cap:      # while 而非 if：醒来时条件可能又被别人改掉
                cv.wait()
            buf.append(i); log.append(f"put {i} size={len(buf)}")
            cv.notify_all()
def consumer():
    for _ in range(5):
        with cv:
            while not buf:
                cv.wait()
            x = buf.popleft(); log.append(f"get {x}")
            cv.notify_all()
ts = [threading.Thread(target=producer), threading.Thread(target=consumer)]
for t in ts: t.start()
for t in ts: t.join()
print(max(int(s.split("size=")[1]) for s in log if "size" in s), "<= cap")
print([s for s in log if s.startswith("get")])

2 <= cap
['get 0', 'get 1', 'get 2', 'get 3', 'get 4']

缓冲区从未超过容量，取出顺序与放入顺序一致。代码里最该记住的是那个 while：被唤醒只代表”条件可能变了”，不代表”条件现在成立”。别的线程可能抢先拿锁把东西取走了，POSIX 也允许没有任何通知的虚假唤醒。所以 wait 永远放在检查条件的循环里。

信号量（semaphore）是 Dijkstra 提出的更早的原语：一个非负整数，P（wait/down）在值为 0 时阻塞、否则减一，V（post/up）加一并唤醒一个等待者。初值为 1 的信号量就是一把锁；初值为 N 则表示”最多 N 个线程同时进入”，适合限制并发数，比如同时最多 8 个下载、连接池最多 16 个连接。有界缓冲区也可以用两个信号量（空槽数、满槽数）加一把锁写出来。条件变量更通用，信号量在”计数资源”上更顺手。

停一下，检查理解单选

生产者-消费者代码里把 while not buf: cv.wait() 改成 if not buf: cv.wait()，在有两个消费者时可能出什么问题？

不会有问题，notify_all 保证被唤醒时缓冲区一定非空两个消费者都被唤醒，第一个取走唯一的元素，第二个醒来后不再检查，对空队列 popleft 报错消费者永远不会被唤醒，程序死锁if 版本更快，因为少检查一次条件

检查答案

死锁：每个人都在等别人

有了多把锁，新的失败方式出现了。线程 1 先拿 A 再拿 B，线程 2 先拿 B 再拿 A，中间各自停顿一下：

void *t1(void *_){ pthread_mutex_lock(&A); usleep(100000); printf("t1 holds A, wants B\n"); pthread_mutex_lock(&B); printf("t1 done\n"); return NULL; }
void *t2(void *_){ pthread_mutex_lock(&B); usleep(100000); printf("t2 holds B, wants A\n"); pthread_mutex_lock(&A); printf("t2 done\n"); return NULL; }

t2 holds B, wants A
t1 holds A, wants B
main: still stuck after 1s -> deadlock

两个 done 永远不会打印。这就是死锁。它的发生需要四个条件同时成立（Coffman 条件）：资源互斥、持有并等待、不可抢占、循环等待。打破任意一个就能避免。实践中最常用的是打破循环等待：给所有锁规定一个全局顺序，每个线程都按这个顺序加锁。上例只要两个线程都先拿 A 再拿 B 就不会死锁。xv6 的文件系统代码就在注释里写明了锁的获取顺序；Linux 内核有 lockdep 工具在运行时检查加锁顺序是否出现环。

其它手段：trylock 拿不到就放掉已持有的锁重试（打破持有并等待，但可能活锁）；一次性申请所有需要的锁；或者干脆重新设计，让一个线程只持有一把锁。

同一类问题在更大尺度上反复出现：数据库系统 的事务互相等行锁，用等待图检测环再杀掉一个事务；并行训练 里不同 rank 以不同顺序进入集合通信，整个作业挂起不动，本质也是循环等待。

停一下，检查理解单选

一个程序有三把锁 A、B、C。下面哪种规定能保证不会因为这三把锁出现死锁？

每个线程最多同时持有两把锁所有线程需要多把锁时，都按 A、B、C 的顺序获取每次加锁前先 sleep 一个随机时间把所有锁都换成自旋锁

检查答案

三种写并发程序的方式

CSAPP 第 12 章用同一个任务（一个能同时服务多个客户端的 echo 服务器）对比了三种构造并发的方法，它们的取舍至今仍是选型的依据。

多进程：每来一个连接 fork 一个子进程处理。地址空间天然隔离，一个子进程崩溃不影响别人，也不存在共享变量的竞态。代价是进程创建和切换贵，进程间要共享状态（比如统计总请求数）必须借助管道、共享内存等显式机制。早期的 Apache、今天的 PostgreSQL（每连接一个后端进程）都是这种结构。

IO 多路复用：只有一个进程一个线程，用 select/poll/epoll（macOS 上是 kqueue）同时盯着很多 fd，哪个可读就处理哪个，每个连接的进度保存在一个状态机里。没有线程切换，没有锁，单线程就能处理上万个连接。代价是代码要拆成一个个不能阻塞的回调或状态转移，任何一个处理步骤卡住（比如一次慢的磁盘读、一段长计算）整个服务器都停住，而且一个线程用不上多核。Nginx、Redis、Node.js 和 Python 的 asyncio 都是这种模型，后者的细节在 Python 并发与性能，socket 部分在 网络：TCP 与应用层。

多线程：每个连接（或每个任务）一个线程，代码按顺序写，阻塞了也只停自己这一个线程，还能用满多核。代价就是这篇前面讲的所有东西：共享内存让竞态、可见性、死锁都成为可能。

	多进程	IO 多路复用	多线程
共享状态	难，需显式 IPC	天然共享，无竞态	天然共享，需加锁
利用多核	能	单线程不能	能
创建/切换开销	高	几乎没有	中
一处出错的影响	只坏一个进程	整个服务停住	可能拖垮整个进程

真实系统常常混用：每个核一个事件循环线程（多路复用 × 多线程），或者一个事件循环把阻塞的活丢给后台线程池。推理服务的典型结构就是前端 asyncio 接请求、后端一个调度线程驱动 GPU，见 推理系统。

线程池：别为每个任务造一个线程

最后看一个把前面所有原语组合起来的工程结构。一个服务器给每个请求创建一个线程，在请求多时会出问题：创建和销毁线程要进内核、分配栈；几万个线程同时存在，内存和上下文切换的开销压垮机器；而且没有任何上限来保护系统。

线程池的做法是：预先创建固定数量的 worker 线程，它们循环地从一个共享的任务队列里取任务执行；提交任务只是往队列里放一个对象。这个队列正是上一节的有界缓冲区，由一把锁和条件变量保护。

美团技术团队分析 Java ThreadPoolExecutor 的文章把它的设计拆得很清楚，几个决策点在任何语言里都通用：

• 核心线程数与最大线程数：任务来了先用核心线程，核心都忙就进队列，队列满了才扩到最大线程数。顺序反过来会让线程数在突发流量下暴涨。
• 队列是否有界：无界队列永远不会拒绝任务，代价是积压时内存无限增长、延迟无限变大。
• 拒绝策略：队列和线程都满时怎么办，抛异常、丢弃、还是让提交者自己执行（相当于反压）。
• 线程数怎么定：CPU 密集型任务大约等于核数，更多只是增加切换；IO 密集型可以多很多，因为大部分时间在阻塞等待。这些参数难以事先算准，所以那篇文章的结论是让它们能在运行时动态调整并配监控。

Java 并发包里各种锁和同步器的底层（AQS）本质是一个状态整数加一个等待线程队列：用 CAS 原子地修改状态，拿不到的线程进队列挂起，释放时唤醒队首。这和上面”先在用户态原子操作、要等待时才进内核”的 mutex 是同一个结构。

Python 的 concurrent.futures.ThreadPoolExecutor、PyTorch DataLoader 的 worker、推理引擎里的请求调度循环，形状都一样：固定的 worker、一个队列、一个限流点。

记住这三件事

1. cnt++ 是读、改、写三步，多个线程不加同步地交错就会丢更新；竞态取决于时序，测不出来，只能靠设计避免。
2. 锁建立在硬件原子指令之上，并自带内存屏障；条件变量用来等条件，wait 要放在 while 循环里；能用锁就别手写无锁代码。
3. 多把锁按统一顺序获取可以避免死锁；线程池用固定 worker 加有界队列，把并发数控制在机器扛得住的范围内。

延伸阅读

• Bryant & O’Hallaron, Computer Systems: A Programmer’s Perspective, 3rd ed., 第 12 章 Concurrent Programming
• Russ Cox, Frans Kaashoek, Robert Morris, xv6 book 第 6 章 Locking、第 7 章 Scheduling（sleep/wakeup）
• Remzi & Andrea Arpaci-Dusseau, OSTEP, Concurrency 部分（Locks、Condition Variables、Semaphores、Common Concurrency Problems）
• 美团技术团队，《Java 线程池实现原理及其在美团业务中的实践》《从 ReentrantLock 的实现看 AQS 的原理及应用》
• Hans Boehm, Threads Cannot Be Implemented as a Library, PLDI 2005；cppreference 的 std::memory_order 页面