行业资讯
南京大学 操作系统 (JYY) 学习笔记：并发控制与互斥锁的底层演进 (Mutual Exclusion)
 学习笔记：并发控制与互斥锁的底层演进 (Mutual Exclusion))
写在前面这是本系列的第十四篇。在上节课中我们见识到了“并发”这头猛兽的威力线程并发给了我们利用多核处理器的能力但也彻底摧毁了程序状态迁移的确定性带来了“极难编程”的挑战。连最简单的1 1都会算错这代码还怎么写本讲内容既然无法驾驭乱序的并发我们的策略就是——阻止它我们将探讨基础并发控制的核心概念互斥 (Mutual Exclusion)以及人类为了实现绝对安全的lock/unlock是如何从软件算法一路卷到硬件指令最后由操作系统接管一切的。入门线程库与确定性的丧失线程库回顾spawn(fn): 创建共享内存的线程 (执行流、状态机)。join(): 等待线程结束。放弃确定性 执行顺序 全局一致性人类是 “Sequential Creatures” (顺序生物):具备 $ A \rightarrow \dots \rightarrow B $ 简化为 $ A \rightarrow B $ 的直觉本能。编译器甚至处理器这种“硬件编译器”也是基于这种单线程的顺序假设来设计的。多处理器彻底改变了“执行”的含义:在并发世界里任何load都可能读到也可能读不到其他线程刚刚写入store的值。连1 1都无法保证正确执行这还怎么玩真的要放弃并发编程不要急。我们可以做一个类比映射线程 人大脑能完成局部存储和计算。共享内存 物理世界物理世界天生就是并行的多个人同时在一个房间里活动。程序 状态机物理世界其实也可以用状态迁移来严格建模。互斥阻止并发 (并行) 的发生从最简单的问题入手1 1够简单了吧longsum0;voidT_sum(){sum;}为了让这个简单的自增在多线程下绝对正确我们希望有一个 API无论怎么执行sum** 的求和结果都是正确的。**这就引入了互斥 (Mutual Exclusion)互相排斥阻止同时发生sumStop the World (时间停止)让硬件给我们提供一条“ザ・ワールド” (The World时停) 指令行不行longsum0;voidT_sum(){stop_the_world();// 此时进入 ザ・ワールド 状态全世界其他线程全被冻结sum;resume_the_world();}这显然有些“Overkill” (杀鸡用牛刀)只要能声明“不能并发”的特定代码块就可以了。其他和sum无关的代码还是应该允许同时执行的。我们不需要让整个世界都停下来而是只让访问相关寄存器/内存的代码排队。互斥机制的诞生lock();sum;// 或者任意共享资源操作代码unlock();拟人视角用lock/unlock标记一个代码块。这就好比获得了一把钥匙如果锁已经被别人占用当前线程就会被阻塞排队等待操作完成后unlock允许下一个人进入。在任何时刻只能有一个人拥有这把锁。所有被标记的代码块被称为临界区 (Critical Section)它们之间是 “Mutually Exclusive” 的。状态机视角加上锁之后被标记代码块的执行在宏观上就可以被理解为“一次原子的状态迁移”不可分割的一步。不并发还需要线程吗既然加了锁变成了排队串行那我们还需要多核和多线程吗悲观的 Amdahl’s Law (阿姆达尔定律)如果你有 $ 1/k $ 的代码是加锁不能并行的那么无论你加多少个 CPU你的最大加速比都存在理论上限$ T_\infty \frac{T_1}{k} $乐观的 Gustafson’s Law (古斯塔夫森定律)随着计算规模的增大并行计算的红利总是能覆盖串行的开销$ T_p T_\infty \frac{T_1}{p} $(注$ T_nKaTeX parse error: Expected group after _ at position 6: _ 代表 _̲n $_ 个处理器的运行时间)_实际生活许多计算是高度可并行的经典物理的局部性原理物体对相邻物体的影响需要时间即便在量子力学纠缠态严格来说不成立但在宏观依然是极好的近似。推论任何物理世界的模拟皆可以大规模并行$ T_\infty \ll T_1 $。Embarrassingly Parallel (尴尬的并行/完美并行) 例子图书馆管理 v.s. 分布式数据存储系统。人类大脑 v.s. 深度神经网络矩阵乘法。NP-Hard 问题的暴力穷举搜索。软件方案的困境使用共享内存实现互斥 (Spicy ️)早期计算机科学家试图只用软件普通的load/store来实现互斥。Dekker’s Algorithm 与 Peterson’s Algorithm绕口令般的算法“A process P 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.”Peterson 协议的拟人比喻假设有三个变量你的手旗子、他的手旗子、厕所门上的字条。如果想进厕所先举起自己的旗子然后把写有对方名字的字条贴在门上。持续观察模式看看对方是否举旗看看门上是不是自己的名字如果对方没举旗或者门上的名字是自己进入厕所否则死循环继续观察。出了厕所后放下自己的旗子。软件并发的极端危险你很难从字面上判断这些并发算法到底对不对就像你无法用肉眼看出“n个线程循环m次sum的最小值是多少”哪怕是今天的顶级大模型也推导不出所有状态。必须借助Model Checker (模型检查器)把代码转换成图交给电脑去进行状态空间的穷举遍历。电脑为什么叫“电脑”因为它能替代人类机械的思维活动。致命假设编译器和 CPU 不会乱序直接写一个 Peterson 算法在现代电脑上跑绝对是错的因为这类算法做了一个现代 CPU 早已放弃的假设Load/store指令是瞬间完成且对所有人立刻生效的。指令是严格按照程序书写顺序执行的。现代修复方案必须在关键位置强行插入屏障Compiler barrier (编译优化屏障):asm volatile( ::: memory);Memory barrier (内存屏障):__sync_synchronize()(对应底层的mfence,dmb ish,fence rw, rw等指令强制保证读写的先后和可见性)。结论智力体操不是我们想要的我们需要的是 “Absolutely Correct” 的绝对安全的工程化方案。降维打击使用原子指令实现互斥既然软件不好解决那就让硬件来凑硬件协助Stop-the-world 的小操作我们能不能请求硬件提供一条绝对不会被打断的指令早期单核时代cli(x86 清除中断标志) 或csrci mstatus, 8(RISC-V 关中断)。关了中断系统就不会调度代码自然互斥。多核时代关中断没用了我们需要真正的原子指令 (ἄτομος / indivisible)。硬件厂商在 CPU 指令集里提供了自带“魔法”的指令能在一个不可分割的周期里同时完成load calc storex86:lock前缀 (如lock cmpxchgl)。RISC-V:LR/SC(Load-Reserved/Store-Conditional) 及A扩展。ARM:ldxr/stxr。自旋锁 (Spinlock)API 与实现有了原子指令如atomic_cmpxchg我们终于可以写出绝对安全的锁了typedefstruct{intstatus;// ✅ (0) 或 ❌ (1)}lock_t;voidspin_lock(lock_t*lk){retry:// 如果 status 是 0原子的把它变成 1并进入临界区// 否则疯狂死循环重试if(!atomic_cmpxchg(lk-status,0,1)){gotoretry;}}voidspin_unlock(lock_t*lk){lk-status0;__sync_synchronize();// 确保释放锁之前的数据修改全部刷入内存}Caveat (警告)lock/unlock 是万恶之源从设计出这个 API 开始……人类就走上万劫不复的错误道路了。因为lock和unlock都是程序员全权负责的程序员 100% 会花式犯错忘记加锁、加了忘记解、在if里提早return忘了unlock导致全局死锁……Linux 内核里至今仍有无穷无尽的这种 Bug。// 不要笑下面这个小丑 就是你自己T1:spin_lock(l);sum;spin_unlock(l);T2:spin_lock(I);sum;spin_unlock(I);// 复制粘贴时字母小写 l 写成了大写 I终极方案使用系统调用实现互斥 (OS 来帮忙)自旋锁的 Scalability (可扩展性) 灾难Spinlock在多核下简直是 Performance Bug性能灾难 1“一核有难八核围观”。拿不到锁的线程在其他 CPU 上疯狂空转白白消耗 100% 的算力和电量。性能灾难 2如果持有锁的线程被操作系统调度器切换下去了或者发生了中断此时所有空转等待的线程将面临无穷无尽的等待把上锁和解锁的操作交给 OS既然线程自己解决不了空转那就求助操作系统内核syscall(SYSCALL_acquire, lk);试图获得锁。如果失败OS 会直接把当前线程标为“睡眠”状态切换去执行其他线程绝不空转浪费 CPU。syscall(SYSCALL_release, lk);释放锁并告诉 OS“我用完了你可以去唤醒之前那些在睡觉等待的线程了。”(注自旋锁并没有被淘汰在内核底层自旋锁依然被用来保护极其短暂的不可被中断的数据结构但普通的应用程序绝对不该用自旋锁)。完美工程解pthread Mutex Lock 与 Futexpthread_mutex_tlock;pthread_mutex_init(lock,NULL);pthread_mutex_lock(lock);pthread_mutex_unlock(lock);编程的时候直接用pthread_mutex就可以了为什么它性能好因为它底层采用了Futex (Fast Userspace muTexes)技术。Futex小孩子才做选择我全都要性能优化的最常见技巧是优化 fast path。Fast Path (快车道):绝大部分时候锁其实是没竞争的。此时直接在用户态用一条原子指令抢锁瞬间进入临界区根本不需要陷入操作系统内核Slow Path (慢车道):只有当发生争抢原子指令失败时才触发极其昂贵的系统调用futex_wait让 OS 帮我把线程催眠排队。Futex 极其复杂连它的发明人 Ulrich Drepper 第一次用的时候都写出了 Bug。但对我们来说直接调用封好的 API 享受它带来的极致性能即可。总结Take-away Messages:并发编程“很难”而人类应对这种指数级复杂性的唯一方法就是——退回到不并发。我们可以在线程中使用lock/unlock实现互斥所有被同一把锁保护的代码都退化成了安全的串行执行虽然谁先谁后依然是随机的。互斥的实现充满了挑战经历了从纯软件算法Peterson、硬件原子指令Spinlock到最后操作系统深度介入的休眠锁Mutex/Futex的漫长演进。值得庆幸的是只要我们程序中“能并行”的部分足够多在关键节点串行化一小部分数据更新并不会对整个系统的性能带来致命的影响。
郑州网站建设
网页设计
企业官网
![[GESP202606 四级] 扫雷](http://pic.xiahunao.cn/yaotu/[GESP202606 四级] 扫雷)
