线程与同步

线程共享的数据

同一进程中的线程共享地址空间和许多进程资源，各自保留寄存器上下文、栈和调度状态。一个线程写入共享数组后，其他线程有机会读取新值；这种共享减少了数据复制，也要求程序协调访问顺序。线程局部变量通常位于各自栈中，但若把局部变量地址传给其他线程，该变量同样可能成为共享对象。

并发程序的结果取决于操作之间允许的顺序。源代码中的一条赋值或递增语句可能包含多次机器操作。编译器与处理器还会在语言内存模型允许的范围内调整执行。教学用的交错模型只覆盖这些行为中的一部分。在 C 或 C++ 中，无同步的非原子共享读写可能构成数据竞争并导致未定义行为，不能把某一种交错结果当成语言保证。

临界区与互斥

临界区是访问某项共享状态、要求与其他相关操作协调的一段代码。互斥保证同一时刻至多一个执行者进入受同一把锁保护的临界区。正确性还依赖所有相关读写遵守同一保护规则，并在离开临界区时恢复共享状态的不变量。

例如，共享队列需要同时维护元素、头尾位置和长度。只对长度加锁，却允许其他线程在锁外修改元素，会破坏这些数据之间的关系。设计锁之前，先写清保护对象与不变量，才能判断哪些操作必须在同一个临界区完成。锁的范围越大，并发度越低；范围过小又可能把应当整体执行的修改拆开。

读改写交错

两次递增的更新丢失

考虑明确规定的教学模型：一次递增分为读取共享整数、在私有寄存器中加一、写回三个步骤，各步均按给定次序执行。共享值初始为零。线程甲先读到零，线程乙也读到零；甲计算并写回一，乙随后把自己的结果一写回。两个线程各完成一次递增，最终值为一。

若先让甲完整执行三个步骤，再让乙执行，乙读到一并写回二。我们检查差异来自两个线程使用了相同旧值，第二次写回覆盖了第一次结果。在整个读改写序列外加同一把互斥锁后，两次操作只能串行完成，最终值为二。这个例子用于解释交错风险，实际语言实现应使用符合其内存模型的互斥或原子操作。

原子递增为一个特定的共享操作提供不可分割的语义。若业务操作还同时更新总量、余额和记录列表，仅把其中一个字段改为原子类型仍然不足以维持整体一致性。我们应先确定哪些状态必须一起改变，再选择锁、原子组合或其他同步结构。读取者也必须遵守约定，否则它仍可能观察到一组尚未一致的值。

互斥锁与等待方式

自旋锁在获取失败时反复检查锁状态，等待期间继续消耗处理器；阻塞式互斥锁则在适当条件下让线程睡眠，等待唤醒后重新参与竞争。临界区很短且锁持有者正在其他核心运行时，自旋可能避免睡眠和唤醒成本；锁持有者可能长时间停顿时，持续自旋会浪费处理器资源。

锁的实现通常需要原子读改写指令与适当的内存顺序，普通变量上的循环无法自动提供正确性。获取锁与释放锁还承担共享数据的可见性约定，让后一个持有者观察到前一个持有者完成的修改。只讨论锁变量的数值，而忽略临界区数据的访问顺序，会遗漏同步的关键部分。

临界区中的异常和提前返回需要统一处理释放。实际代码宜用语言提供的作用域锁管理结构，保证正常返回和异常路径都释放锁。在持锁期间执行慢速输入输出还会扩大等待时间；若必须这样做，应明确资源依赖和延迟要求，避免无关线程因同一把锁长期停顿。

条件变量与队列

互斥锁保护状态，条件变量用于等待某个关于共享状态的条件成立。等待操作在语义上把释放互斥锁与进入等待连接起来，返回前重新获得锁。被唤醒只表示值得重新检查条件，其他线程可能已经改变状态，某些接口也允许无对应通知的唤醒，因此等待判断应放在循环中。

以容量为 $K$ 的队列为例，令 $n$ 为当前元素数量，不变量为 $0\le n\le K$。消费者在持锁状态下检查 $n>0$，不满足时等待；生产者检查 $n<K$，不满足时等待。生产者插入元素并增加计数后通知等待数据的消费者，消费者删除元素后通知等待空位的生产者。检查、修改和通知的组织必须与所用条件变量接口一致。

容量为二的生产消费顺序

设队列容量为二，初始为空，生产者依次产生甲、乙、丙三个元素，消费者暂未运行。生产者插入甲后数量为一，插入乙后数量为二；准备插入丙时发现队列已满，于是等待空位并释放互斥锁。

消费者获得锁，取出甲，使数量从二降为一，并通知空位条件。生产者被唤醒后先重新获得锁，再检查当前数量。若没有其他生产者占用空位，它插入丙，数量恢复为二，队列顺序为乙、丙。我们逐步核对数量为零、一、二、一、二，始终满足容量约束。若被唤醒后直接插入而不重新检查，多生产者场景中另一个线程可能已先占据空位。

这个流程还说明通知本身不会长期保存业务状态。若生产者在消费者等待之前插入数据，消费者后续检查数量就能直接读取；它无需依赖已经发生的通知。共享状态表达事实，通知帮助等待者及时重新检查，两者的职责应在代码中保持清楚。

信号量与资源数量

计数信号量维护一个非负资源计数。获取操作在有资源时减少计数，否则等待；释放操作增加计数并允许等待者继续。若初始值为三个，且所有线程严格配对获取和释放，便能把同时使用某项资源的线程数限制在三个以内。信号量不一定要求释放者就是获取者，因此其使用约束与互斥锁不同。

有界队列可以用空位信号量和元素信号量配合互斥锁实现。生产者先获取空位，再锁住队列执行插入，解锁后释放一个元素计数；消费者先获取元素计数，再锁住队列执行删除，解锁后释放一个空位计数。如果先持有队列锁再等待空位，队列满时消费者可能无法获得锁进行删除，等待关系就会阻止进展。

同步正确性需要同时考虑安全性与进展。安全性要求不越界、不丢失更新以及共享不变量成立；进展还要求等待线程有机会继续，避免死锁和长期饥饿。互斥本身不保证公平顺序。评价某种锁实现时，需要读取接口的公平性承诺，并检查任务被取消或线程异常退出时资源如何归还。

并发状态练习

练习标记完成

所属知识

原子操作

难度

2/5

两个线程各执行一千次原子递增，初值为零，没有其他写入。给出最终值及成立条件。

查看解答

在每次原子递增都成功、初值为零且没有其他写入的条件下，结果为两千。原子操作使单次递增按某个整体顺序生效；如果还要求与其他字段保持关联，需要额外设计同步。

练习标记完成

所属知识

条件等待

难度

2/5

一个消费者被通知后，为什么仍应在持锁状态下再次检查队列是否非空？给出两种原因。

查看解答

消费者重新获得锁之前，另一个消费者可能已取走最后一个元素；接口也可能出现虚假唤醒。使用循环重新检查队列非空，只有条件成立才删除元素。

练习标记完成

所属知识

信号量计数

难度

2/5

信号量初值为五，依次完成三次获取和一次释放，期间没有其他操作。求剩余计数与净占用数量。

查看解答

初始五个资源，三次获取后剩余二个，一次释放后剩余三个。净占用为二个。计数推导要求每次获取和释放对应真实资源变化，重复释放会破坏约束。

练习标记完成

所属知识

等待与锁

难度

3/5

队列已经满，生产者持有队列锁再等待空位信号量，消费者需要这把锁删除元素。说明等待关系，并调整获取顺序。

查看解答

生产者持有队列锁并等待空位，消费者需要同一把锁才能删除元素并释放空位，双方无法继续。应先等待空位，再获取队列锁执行短暂的插入操作。

线程同步参考资料

Operating Systems: Three Easy Pieces

Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau · 2023 · Arpaci-Dusseau Books

打开官方来源

OSTEP 的 Locks、Condition Variables 和 Semaphores 章节分别说明互斥、条件等待与资源计数。对照示例时，应逐项检查共享变量、不变量、睡眠前的条件检查和唤醒后的重检，确认不同同步结构在程序中的作用。

xv6: a simple, Unix-like teaching operating system

Russ Cox, Frans Kaashoek, Robert Morris · 2025 · Massachusetts Institute of Technology

打开官方来源

MIT xv6 教材第 7 章讨论锁与内存顺序，第 9 章分析睡眠和唤醒中的竞争。内核代码还涉及中断与自旋锁配合，普通用户线程库提供的接口有自己的等待和调度要求，因此移植同步代码前应逐项核对这些约束。