14 - Concurrency control: mutual exclusion
14 - 并发控制：互斥
线程并发给了我们利用多处理器的能力，同时也带来了 “难编程” 的挑战——当然，这样的问题我们见得也不少，通常通过引入新的编程语言机制，或者是一个新的 API 就能解决问题。
本讲内容：基础并发控制：互斥 (mutual exclusion)。
入门：线程库
spawn(fn): 创建共享内存的线程 (执行流、状态机)
join(): 等待线程结束
放弃：确定性 & 执行顺序 & 全局一致性
人类是 “sequential creatures”
具备 A→…→B 简化为A→B 的直觉本能
编译器 (处理器也是编译器) 也是这样设计的
但是多处理器彻底改变了 “执行” 的含义
任何 load 都可能读到其他线程写入的值
连 1 + 1 都不会实现了，这还怎么玩？
真的要放弃并发编程？？？
不要急...
线程 = 人
大脑能完成局部存储和计算
共享内存 = 物理世界
物理世界天生并行
程序 = 状态机
C 程序、机器指令、model checker……
物理世界也可以用状态迁移来建模
1. 互斥：阻止并发 (并行) 的发生
1.1. 简单的问题入手
1 + 1，够简单了吧
long sum = 0;
void T_sum() {
sum++;
}我们希望有一个 API
无论怎么执行，sum 的求和都是正确的
互斥 (互相排斥)：阻止同时的 sum++
mutual exclusion...
1.2. Stop the World
让硬件给我们提供一条 “ザ・ワールド” 指令行不行？
long sum = 0;
void T_sum() {
stop_the_world();
// ザ・ワールド 状态
sum++;
resume_the_world();
}似乎有些 “overkill”
只要能声明 “不能并发” 的代码块就可以了
其他 (和 sum 无关的) 代码还是可以同时执行的
不需要整个世界都停下来...而是让访问相关的寄存器/内存的代码停下来...
1.3. 互斥：阻止并发
lock();
sum++;
// 或者任意代码
unlock();拟人视角
用 lock/unlock 标记一个代码块
获得一把锁，如果锁已经被其他线程占用，当前线程会被阻塞，直到锁被释放
当线程完成对共享资源的操作后，unlock，释放互斥锁，允许其他线程进入
在某个时刻，只能一个人拥有这把锁
所有标记的代码块之间 “mutually exclusive”
“一旦我进入标记的代码块，其他人就无法进入”
其中称之为：临界区？
状态机视角
被标记代码块的执行可以理解为 “一次状态迁移”
(当然，这是有条件的)
1.4. 不并发，还需要线程吗？
加了锁，是不是就不需要多核了？？？
悲观的 Amdahl's Law
如果你有 1/k 的代码是不能并行的，那么
乐观的 Gustafson's Law (的更细致版本)
并行计算总是能实现的
(Tn 代表 n 个处理器的运行时间)
具体情况具体而言，看能并发的部分时间长还是不能并发的时间长？
1.5. 实际生活许多计算是可以并行的
经典物理：局部性原理
物体对相邻物体的影响需要时间
(即便严格来说不成立，依然是一个很好的近似)
推论：任何物理世界模拟皆可以大规模并行
Embarrassingly Parallel 的例子
图书馆 v.s. 分布式数据存储
大脑 v.s. 深度神经网络
NP-Hard 问题的搜索
2. 使用共享内存实现互斥
不正确的尝试...
2.1. Dekker's Algorithm
绕口令：A process PP can enter the critical section if the other does not want to enter, otherwise it may enter only if it is its turn.
“Myths about the mutual exclusion problem” (IPL, 1981)
2.2. Peterson's Algorithm
还是绕口令：A process PP can enter the critical section if the other does not want to enter, or it has indicated its desire to enter and has given the other process the turn.
并发的危险
你很难从字面上判断它到底对不对
就像 “n 个线程循环 m 次，sum 的最小值为 1”
就像 “n 个线程循环 m 次，sum 的最小值为 2”
就像 “n 个线程循环 m 次，sum 的最小值为 3”
2025 年的思考模型都做不到……
2.3. Peterson's Protocol
有三个变量：你的手、他的手、厕所门。
如果希望进入厕所，按顺序执行以下操作：
举起自己的旗子 (store 手)
把写有对方名字的字条贴在厕所门上 (store 门)
然后进入持续的观察模式：
观察对方是否举旗 (load 手)
观察厕所门上的名字 (load 门)
对方不举旗或名字是自己，进入厕所，否则继续观察
出厕所后，放下自己的旗子 (不用管门上的字条)
2.4. 直观解释
进入厕所的情况
如果只有一个人举旗，他就可以直接进入
如果两个人同时举旗，由厕所门上的标签决定谁进
手快 (被另一个人的标签覆盖)、手慢
一些更细节情况
A 看到 B 没有举旗
B 一定不在厕所
B 可能想进但还没来得及把 “A 正在使用” 贴在门上
A 看到 B 举旗子
A 一定已经把旗子举起来了 (!@^#&!%^(&^!@%#
../../lec4/mosaic/mosaic.py工具链...可以进行状态遍历？
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec14/peterson# ../../lec4/mosaic/mosaic.py -c peterson.py | grep \"cs\" | sort | uniq
mosaic 遍历所有状态
grep
sort 进行排序
uniq 提取不重复的状态，重复的取一种...
2.5. We Need“绝对正确”的工程化解决方案
Model Checker: 自动遍历状态空间的乐趣
先贴标签再举旗，还对吗？
如果放下旗子之后 (前) 把门上的字条撕掉，还对吗？
观察举旗和名字的顺序交换，还对吗？
是否存在 “两个人谁都无法进入厕所”、“对某一方不公平” 等行为？
都转换成图 (状态空间) 上的遍历问题了！
电脑为什么叫 “电脑”
因为它能替代部分人类的思维活动
而且能替代得越来越多 (计算器 → 编程语言 → 大模型)
// The caveat is: no matter how many times we run this test
// without seeing it fail, we cannot be certain that we have
// inserted sufficient barriers. Understanding the correctness
// of this code is far beyond the scope of this course.2.6. Computer Science 的叛逆本质
我们的终极目标就是干掉我们自己
人奸
每个班上都有一个老师总是夸夸，你曾经暗恋的 Ta
Ta：认认真真完成老师作业
工整的笔记，启发了思维，浪费了生命
我：烦死了！劳资不干了！玩
去了战略：提出好的问题、适当地分解问题
战术：执行过程中使用先进工具替代机械思考
状态空间搜索 + AI 启发式剪枝 (AlphaX)
2.7. Peterson算法：假设
做了并发编程中需要 “放弃” 的假设
Load/store 指令是瞬间完成且生效的
指令按照程序书写顺序执行
(不怪他们，那时候还没有高性能编译器和多核计算机)
所以……
直接写那么一个 Peterson 算法应该是错的？
我们当然能写个程序试试！
2.8. 实现 Peterson 算法 - Spicy
Compiler barrier (编译优化屏障)
asm volatile("": : :"memory"); 或是 volatile 变量
> 内联代码？告诉编译器不要优化代码...
Memory barrier (内存屏障)
__sync_synchronize()= Compiler Barrier +x86:
mfenceARM:
dmb ishRISC-V:
fence rw, rw
能够实现单次 load/store 的原子性
2.9. 上厕所的问题没有解决
智力体操不是我们想要的
我们需要 “absolutely correct” 的工程化方案
如果三个人同时上厕所怎么办？
厕所有两个门怎么办？
......？
3. 使用原子指令实现互斥
实现互斥：软件不够 硬件来凑
3.1. Peterson 的路线错误
试图在 load/store 上实现互斥
计算机系统是我们造的
我们当然也可以把它改成容易实现互斥的样子
这是 Computer Science 和自然科学的一个很大不同
相当多的游戏规则是我们定的
软件不好解决的，硬件帮忙
给我一条 “stop the world” 的指令可以吗？
3.2. 还真有一条指令
cli (x86)
Clear Interrupt Flag
eflags 里有一个 bit 是 IF (0x200)
对于单处理器系统，死循环 = 计算机系统卡死
csrci mstatus, 8 (RISC-V)
Control and Status Register Clear Immediate
同样，清除 mstatus 的 MIE bit
适用条件
单处理器系统、操作系统内核代码
3.3. 实现线程互斥有什么？
思路
从不正确的代码开始，把我们 “想做到” 的事用指令去做
错误原因：if 条件在执行 can_go = ❌ 时已经不成立了
void lock() {
retry:
if (can_go == ✅) {
can_go = ❌; // then function returns
} else {
goto retry;
}
}
void unlock() {
can_go = ✅;
}竞态条件
假设两个线程同时执行 lock 函数。
线程A检查 can_go ，发现它是 ✅ ，然后线程A被挂起
此时，线程B检查 can_go ，发现它仍然是 ✅ ，于是线程B将 can_go 设置为 ❌ 并返回
当线程A恢复执行时，它也会将 can_go 设置为 ❌ 并返回
这样，两个线程都认为自己获取了锁，导致互斥失败
3.4. 请求硬件提供：stop-the-world 的“小操作”！
ἄτομος (atomos): “indivisible” 的原子指令
一个 “不被打断” 的 load + 计算 + store
x86: Bus Lock (locked instruction)
RISC-V: LR/SC & A 扩展
来自 MIPS: Load-Linked/Store-Conditional (LL/SC)
arm: ldxr/stxr, stadd (store add) 指令
if (can_go == ✅) {
can_go = ❌; // then function returns
}
// movl $✅, %eax
// movl $❌, %edx
// lock cmpxchgl %edx, (can_go)3.5. 终于实现 1+1 了
asm volatile("lock incq %0" : "+m"(sum));
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec14/sum-atomic# cat README.md
**使用原子指令实现求和**：如果我们为 add/inc 等指令增加 lock 的前缀，处理器硬件会实现将这条指令实现为原子指令。
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec14/sum-atomic# make
gcc -O2 -I/mnt/d/CSLab/osCourse/lec13/thread-lib -o sum sum.c
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec14/sum-atomic# ./sum
sum = 200000000
2*n = 2000000003.6. 自旋锁：API 与实现
typedef struct {
...
} lock_t;
void spin_lock(lock_t *lk); // 可以有多组 can_go
void spin_unlock(lock_t *lk);void spin_lock(lock_t *lk) {
retry:
if (!atomic_cmpxchg(&lk->status, ✅, ❌)) {
goto retry;
}
}
void spin_unlock(lock_t *lk) {
lk->status = ✅;
__sync_synchronize();
}root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec14/sum-spinlock# make
gcc -O2 -I/mnt/d/CSLab/osCourse/lec13/thread-lib -o sum sum.c
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec14/sum-spinlock# ./sum
Thread 3: sum = 54462141
Thread 5: sum = 56437040
Thread 2: sum = 58434711
Thread 6: sum = 59569350
Thread 4: sum = 59759860
Thread 1: sum = 60000000
sum = 60000000
60*n = 600000003.7. Caveat: lock/unlock 是万恶之源
从设计出这个 API 开始……
人类就走上万劫不复的错误道路了
因为 lock 和 unlock 都是程序员负责的
写代码的时候就必须清楚地知道什么时间会和谁共享数据
还记得 Tony Hoare 的 billion-dollar mistake 吗？程序员 100% 会花式犯错的！！！
忘记标记代码；在偶然的路径上忘记 unlock (例如：在 lock/unlock 之间 return)；……
T1: spin_lock(&l); sum++; spin_unlock(&l);
T2: spin_lock(&I); sum++; spin_unlock(&I);不要笑， 🤡就是你自己
linux kernel里面有无穷无尽的这种 bug...
4. 使用系统调用实现互斥
操作系统来帮忙
4.1. 性能的另一个维度：Scalability
系统随着需求或负载增加时，依然能够保持性能和稳定性，灵活扩展资源的能力。(另一个角度：在资源增长时，能维持或提升性能的能力)
Spinlock 已经可以算是 performance bug 了
4.2. 自旋锁的 Scalability 问题
性能问题 (1)
除了获得锁的线程，其他处理器上的线程都在空转
“一核有难，八核围观”
如果代码执行很久，不如把处理器让给其他线程
性能问题 (2)
应用程序不能关中断……
持有自旋锁的线程被切换
导致 100% 的资源浪费
(如果应用程序能 “告诉” 操作系统就好了)
你是不是想到了什么解决方法？
> 比如某个线程被中断了之后...其他所有的处理器都在空转
有没有可能一边 run 一边告诉 OS 自己的 state...
4.3. 线程自己解决不了，OS help it
可以把上锁和解锁的操作交给 OS
把锁的实现放到操作系统里就好啦
syscall(SYSCALL_acquire, &lk);acquire
试图获得 lk，但如果失败，就切换到其他线程
syscall(SYSCALL_release, &lk);release
释放 lk，如果有等待锁的线程就唤醒
剩下的复杂工作都交给内核
actually...关中断 + 自旋
自旋锁只用来保护操作系统中非常短的代码块
本课程不讨论
成功获得锁 → 返回
获得失败 → 设置线程为 “不可执行” 并切换
4.4. pthread Mutex lock
与自旋锁完全一致，而且性能足够好
pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL);
pthread_mutex_lock(&lock);
pthread_mutex_unlock(&lock);编程的时候用这个就行啦!
没有争抢的时候性能非常好
甚至都不需要 trap 进操作系统内核
更多线程争抢时也有相当好的 scalability
这么神奇？
哪种方式更快？
spin...单线程很快，但是 2 个以上的 thread 会慢得非常快
mutex...
atomic...中间只能有一条代码
4.5. Futex: Fast Userspace muTexes - Spicy
小孩子才做选择。操作系统当然是全都要啦！
性能优化的最常见技巧：优化 fast path
Fast Path: 自旋一次
一条原子指令，成功直接进入临界区
Slow Path: 自旋失败
请求系统调用
futex_wait请操作系统帮我达到自旋的效果
(实际上并不真的自旋)
比你想象的复杂
如果没有锁的争抢，Fast Path 不能调用
futex_wake自旋失败 → 调用
futex_wait→ 线程睡眠如果刚开始系统调用，自旋锁被立即释放？
如果任何时候都可能发生中断？
并发：水面下的冰山
Futexes are tricky by Ulrich Drepper
连他的发明人第一次用...也会错...
吃一些苦头！然后让自己有更多的信心和概念...然后解决它
5. 总结
Take-away Messages: 并发编程 “很难”，而类应对这种复杂性的方法就是退回到不并发。我们可以在线程中使用 lock/unlock 实现互斥——所有被同一把锁保护的代码，都失去了并发的机会 (虽然先后依然是不受控制的)。当然，互斥的实现是相当有挑战性的，现代系统中的互斥设计线程中的原子操作、内核中的中断管理、原子操作和自旋等机制。值得注意的是，而只要程序中 “能并行” 的部分足够多，串行化一小部分也并不会对性能带来致命的影响。
Last updated