自从接触并发编程那天起我们基本上都把“线程互斥”和“加锁”划等号。手一抖就是一个mutex.lock()实在不行还有atomic、semaphore仿佛互斥本来就该由某个神秘底层功能免费赠送。但真正让我把这件事想透彻的反而是教科书里那个看起来“过时”的Dekker算法不依赖任何硬件的原子指令不请求操作系统帮忙只靠两个普通内存变量就能让两个线程“你进我就退我进你就退”。这个方案让我意识到所谓互斥本质上是几个线程之间对“谁先进”达成的一种无需语言的默契。这篇内容适合正在学并发原理、需要在裸机或受限环境里实现同步、或者和我一样想搞明白“锁到底在锁什么”的开发者。我会把算法推导、完整可运行代码、现代硬件下的正确性缺口一次讲清楚末尾还有我自己调试这类代码踩过的坑。1. 为什么要在“没有锁”的环境下实现互斥先别急着把它当成老古董。我碰到的实际场景是这样的某个嵌入式项目里两个任务会轮流修改同一份配置结构体系统里没有调度器也没有可重入锁的库支持唯一能依赖的是几块共享内存。当时第一反应是“编译器总得给点原子操作吧”查来查去发现目标平台上根本没有现代标准库而一条底层同步原语在系统调用级别可能都有问题。这种情况除了硬着头皮用纯软件协议控制访问顺序没有别的捷径。1.1 临界区、竞态与“纯软件”的定义先对齐基础概念。临界区就是一段只允许一个线程同时执行的代码区域相对于共享资源而言它被访问的那一小段就是临界区竞态条件是多个线程同时进入临界区、读写顺序不确定导致结果依赖调度时序。比如两个线程同时对count执行count在底层分成读、加、写三步切走线程后就可能互相覆盖最终少加一。传统互斥方案依赖硬件原子指令比如Test-and-Set、Compare-and-Swap它们能保证“判断–置位”这一步不可分割或者依赖操作系统提供的睡眠唤醒和队列机制也是建立在硬件调度基础上的。而纯软件互斥算法只用原始的内存读、写和条件判断不加任何特殊指令。Dekker算法就是这一类里最早的经典方案它证明了一件事两个线程通过普通的共享变量协商也完全能做到交替独占访问。1.2 它解决什么问题、适合谁看这个算法在三种场景下仍然有价值教学和研究理解互斥为什么难硬件互斥到底省掉了哪些麻烦。极端受限环境平台不支持原子指令或没有系统库同时只有两线程并发。面试与底层原理问答当被问到“互斥锁是怎么实现的”时你能从纯软件起点一路讲到现代硬件屏障比只会背函数名有说服力得多。不过先说明白现代多核平台的生产环境千万别手搓这个算法仪式感很强正确性却很难保证。后面我会专门讲为什么教科书代码在真实的乱序执行CPU上可能直接翻车。2. 从“两个线程抢一个变量”到Dekker算法的完整推导如果只把Dekker算法当成一段要背的模板那对你写代码的帮助为零。真正有价值的是推导过程为什么最简单的方案会错为什么加变量能修复问题修复之后又引入什么新问题。2.1 方案一一个共享布尔锁标记最直观的想法是准备一个busy进入临界区前检查busy是否为false为false就置为true退出时再置回false。伪代码大概是while (busy) { /* 等待 */ } busy true; // 临界区 busy false;这个方案在单线程下永远正确但两个线程同时走到while检查时可能都看到busy false然后一个置true另一个也置true双双进入临界区。根子在于“检查”和“置位”是两个内存操作中间有可以被插队的窗口。2.2 方案二两个旗标表示“我想进”把单一busy改成每个线程一个意图变量bool flag0 false, flag1 false; // 线程0 while (flag1) { /* 等线程1 */ } flag0 true; // 临界区 flag0 false;可惜这还是错的。正常情况是线程0看到flag1 false于是进入临界区但如果线程1恰好也在执行自己的检查两边都看不到对方的意图结果又是同时进。2.3 先置旗标告诉对方“我正准备进”修正方式是先把自己的意图写出来再检查对方flag0 true; while (flag1) { /* 等待 */ } // 临界区 flag0 false;现在“同时抢”的问题似乎解决了因为两边都先亮出意图。但新的问题紧跟而来如果两边几乎同时置位flag0和flag1都为true然后线程0在while(flag1)内等待线程1也在while(flag0)内等待谁也无法前进死锁了。2.4 引入turn变量打破死锁僵局Dekker的聪明之处是加一个“仲裁变量”turn。它就像两个人轮流使用的通行证破解对称的互等局面。当两边都想进时turn决定谁先主动“后退一步”。算法骨架flag0 true; while (flag1) { if (turn ! 0) { flag0 false; while (turn ! 0) { /* 让位等待 */ } flag0 true; } } // 临界区 turn 1; flag0 false;线程1完全对称。核心思路拆开看第一层while(flag1)表示对方有意图时我得等。如果对方有意图且我又没拿到当前回合的“让路权”那我就把旗标放下腾空入口给对方一直等到turn归我。拿到turn后重新举起旗标继续检查对方是不是已经退出。turn的存在杜绝了两人同时“谦让”到外圈再同时回到内圈的死锁路径因为这个变量的值在给定时刻必然偏向一方。2.5 为什么它能保证互斥这里最关键的判断是两个线程只有当自己举起旗标、且对方旗标没有举起时才进入临界区。即使出现两个旗标同时为true的瞬间也绝对无法同时通过while检查——至少一边会陷入等待或降旗。更严格地说Dekker算法为两线程场景同时满足了互斥、无死锁和无饥饿结合合理的turn仲裁。理解算法最省力的方式是把两个状态画成真值表线程0旗标线程1旗标进入结果falsefalse任意一个可进入falsetrue只有线程1能进入truefalse只有线程0能进入truetrue由turn决定谁等注意这张表只说明进入条件具体到哪个线程走得动还要配合turn的让度逻辑一起看。实现时尤其要小心检查条件错误的顺序会直接破坏互斥。3. 完整可运行代码与验证环境纸上谈兵不算数我把算法写成能直接跑的C代码放在一台普通Linux环境上用pthread验证。3.1 教科书版Dekker实现#include stdio.h #include pthread.h volatile int flag[2] {0, 0}; volatile int turn 0; volatile long shared_counter 0; void enter_critical(int id) { int other 1 - id; flag[id] 1; while (flag[other]) { if (turn ! id) { flag[id] 0; while (turn ! id) { /* 自旋等待纯粹用变量协商 */ } flag[id] 1; } } } void leave_critical(int id) { turn 1 - id; flag[id] 0; } void* worker(void* arg) { int id *(int*)arg; for (int i 0; i 100000; i) { enter_critical(id); shared_counter; leave_critical(id); } return NULL; }主函数创建两个线程跑完后打印shared_counter。理想结果应该是200000。如果互斥失效、两个线程同时进入临界区共享计数会小于这个值。3.2 验证方法和观察结果编译命令gcc -O2 -pthread -o dekker dekker.c运行一次、十次、一百次绝大多数情况下在x86平台会得到200000。因为在x86处理器不太激进的内存重排和普通优化级别下代码碰巧能工作。此时不要高兴太早。把优化级别提高、或者在编译器设置里开启激进重排或者换到需要严格内存屏障的弱内存模型架构结果就会变得不可靠。3.3 如何直观调试它调试纯软件互斥的好办法就是加数据竞争观测点。把shared_counter换成临界区里的一段“耗时操作”比如循环一百万次空转能放大两条线程交错窗口更容易观察谁同时闯了进去。再加一个调试计数器记录“当前在临界区内线程数最大值”如果最大值超过 1立刻说明互斥失效。volatile int inside 0; volatile int max_inside 0; // 临界区入口 int cur __atomic_add_fetch(inside, 1, __ATOMIC_SEQ_CST); if (cur max_inside) { max_inside cur; }不过要提醒一句__atomic_add_fetch本身是原子操作用来“观测”允许进出的结果不会破坏Dekker协议的运行逻辑。4. 纸上正确与线上翻车现代内存模型的残酷真相很多教材讲完Dekker算法就收工了好像这算法天然正确。可是你现在拿这段代码到ARM、POWER等弱内存序平台跑很可能会出现与教科书矛盾的结果。这不是算法证明出了问题而是“内存模型”比几十年前复杂太多。4.1 编译器重排与CPU乱序我们写代码时总以为语句是按顺序执行的。实际上编译器可能把两个不相关的内存操作调换顺序CPU的乱序执行窗口也可能提前或延后某个读写。尤其现代多核CPU都有自己的一级、二级缓存一个核写入了变量在另一个核看来可能要到很晚才可见。Dekker算法在逻辑层面假设了“我读到的顺序就是别人写入的顺序、我写的顺序就是别人观察的顺序”而真实硬件并不承诺这一点。教科书上那个turn变量在和缓存一致性的交互中可能变得“时灵时不灵”。4.2 用生活类比理解内存屏障想象两个人约好轮流讲话Dekker相当于“我举起手你看到我举手于是你闭嘴”。但如果中间隔了一堵隔音的墙举手的信号要过一阵才能传到对方那里对方可能根本没看到就同时开口了。现代CPU的多核缓存就是那堵墙内存屏障memory barrier相当于给墙加一扇门保证某个写操作在继续后续动作之前被“推送”到其他核可见。C语言里volatile只告诉编译器“别优化这个变量的读写”不负责处理CPU乱序更不保证内存可见性。这就是为什么把volatile沾沾自喜地写在每一个变量上还是可能在多核上出问题。4.3 用C11原子操作修正协议真正能落地的版本应当把flag和turn声明为原子类型并在关键读写上加上适当的内存序。最保守的做法是用顺序一致序sequentially consistent orderingatomic_int flag[2] {0, 0}; atomic_int turn 0; void enter_critical(int id) { int other 1 - id; atomic_store_explicit(flag[id], 1, memory_order_seq_cst); while (atomic_load_explicit(flag[other], memory_order_seq_cst)) { if (atomic_load_explicit(turn, memory_order_seq_cst) ! id) { atomic_store_explicit(flag[id], 0, memory_order_seq_cst); while (atomic_load_explicit(turn, memory_order_seq_cst) ! id) { // 等待 } atomic_store_explicit(flag[id], 1, memory_order_seq_cst); } } }这样做的本质是让每一步内存操作都具备全局一致的顺序消除重排带来的不确定性。代价是性能有所下降可换来了真正的正确性。4.4 到底该不该在生产环境手写Dekker我的结论很直接不要。既然标准库给了pthread_mutex、std::mutex、std::atomic没有理由自己维护一个随时可能在架构升级后翻车的协议。学习它的目的是看清“互斥的原理”而不是替换成熟的同步原语。5. 常见问题与排查技巧实录这部分是我实际调试这类代码时积累的经验每一条背后都是真金白银的教训。5.1 为什么临界区计数结果总是不对典型症状shared_counter小于理论值且差异不稳定。原因可能有两个一是协议本身实现有误比如进入条件里少了对turn的判断二是内存可见性导致两边同时推进。排查方式先打印每次进入临界区的线程号与时间戳看是否有重叠窗口再在临界区里临时加入一段较长的空转循环增加交叠概率更容易复现。5.2 程序卡死是不是死锁如果两个线程都在while(turn ! id)里自旋转多半是turn没被正确赋值或者退出临界区时忘记把turn交给对方。另一个隐蔽原因线程1未正确编译同步共享变量两个核的缓存各持一份turn谁都等不到新值。排查手段在临界区加减退出时打日志输出线程ID和turn当前值。运行几轮后基本能定位是哪一侧没把turn交接出去。5.3 加了 volatile 还是出错这是初学者最常见的误区。volatile防止的是编译器对单个变量的优化比如把变量反复读优化成一次寄存器缓存。它不阻止编译器重排两个无关变量的顺序更不阻止CPU乱序执行。所以面对多核并发你必须使用原子类型或显式屏障volatile只是必要条件远不是充分条件。5.4 为什么有的平台总试不出来问题在常见的x86桌面和服务器平台上总体的存储模型相对较强很多教科书实现“碰巧”能跑通而在ARM等弱内存模型平台上由于读写缓冲区更激进问题暴露概率高得多。这种平台差异让人产生“算法没问题”的错觉其实只是没有把它放到真正严苛的环境中验证。5.5 调试纯软件互斥的几个技巧编译时加-fsanitizethread用线程检测工具扫描数据竞争。使用-O2甚至-O3优化让编译器有机会做更多重排。多次批量运行至少循环100次并观察是否存在偶发错误。用原子扩展记录“临界区同时进入的最大人数”自动判断互斥是否失效。这些手段组合起来能把“理论上正确”和“实践上可用”之间的鸿沟看得很清楚。6. 顺着Dekker往下走从两线程到多线程Dekker算法只适用于两个线程这是一个硬性边界。三个及以上线程同时要进临界区时算法的对称结构会爆炸式复杂单点仲裁失效无论怎么加变量都难以优雅扩展。这也是它在工程实践中被快速替换的原因之一。6.1 为什么多线程场景不能用同一套逻辑两个用户抢一把椅子只需要互相看眼色。五个人抢一把椅子就需要明确的排队协议或管理员。Dekker的框架里没有管理员只有两方互让。一旦增加第三方A和B互让时C可能趁虚而入仲裁逻辑彻底失衡。6.2 软件互斥到硬互斥的演进顺着Dekker思想往后走可以看到Peterson算法简化了流程再往后是面包店算法解决多线程公平性但它们都以纯软件读写为前提。现代操作系统转向硬件原子指令后互斥终于变成一条不可分割的指令性能与可靠性都大幅提升。这个演进脉络让我对“底层原语为何如此设计”有了更立体理解。7. 它留给现代开发者的真正价值如果在项目里死磕Dekker算法大概率不会带来业务价值。但梳理它时建立的心智模型会一直有用互斥不是“天然存在”的而是若干原子性假设叠加的结果。用锁时会去思考锁背后的内存序写并发代码时会主动区分“可见性”和“原子性”排查数据竞争时也不再盲目加volatile。我自己实际跑通这段代码后最大的收获是能看懂报错信息里data race字样背后的成因了。如果你恰好和我一样在某个受限环境里没有现成的互斥原语可以用Dekker算法至少给了一个不依赖外力的起点如果你只是好奇锁的内部原理这份推导也足够帮你从“会用”往前走一大步。作为练习建议你把Peterson算法和Dekker算法各实现一遍再把flag换成原子类型试跑体会理论与现实之间那条由编译器、CPU共同挖出的鸿沟。