第一次看到“Dekker算法”这个名字时我正被并发编程的互斥问题折腾得头疼。现代硬件上想实现线程互斥最省事的办法是lock xchg或者std::atomic几行代码就能搞定。但问题来了——如果一台机器没有任何原子指令、没有锁前缀只有对内存的普通读写你还能不能让两个线程老老实实地排队进临界区Dekker算法就是这个问题的一个经典答案它只用共享变量和顺序逻辑就在软件层面实现了双线程互斥。这篇文章会拆解它的完整推导过程、正确性论证以及它放到现代CPU上会遭遇什么。无论你是并发编程初学者、面试准备者还是在嵌入式裸环境里写多任务的人这份纯软件互斥的思路都值得吃透。1. 为什么都上原子指令了还要研究“仅用软件”的互斥1.1 硬件原子指令把互斥变得太容易现代处理器几乎都对互斥开了绿灯。xchg、cmpxchg、lock前缀再加上编译器提供的atomic语义随便摆弄几下就能守住临界区。原因在于硬件设计者为并发专门造了原语一条指令从读取到写入的整个过程在总线上不可分割其他核心要么看到操作前要么看到操作后不存在中间状态。我刚入门时也觉得既然有这些方便的指令为什么还要自我折磨去研究一个几百行都未必写得对的纯软件算法后来在某高校的一次课程设计里我需要在一个只有共享RAM、没有特殊同步指令的模拟多核环境里实现协作式多线程才意识到硬件不支持原子操作这个假设真实存在。更不要说是否能掌握这种无原语条件下的互斥构造能力本身也是理解现代并发原语价值的标尺。1.2 纯软件互斥的适用场景有人会问都21世纪了哪里还有没有原子指令的机器这问题并不空想。早期多处理器系统确实没有锁指令很多嵌入式MCU的DMA和主核之间共享缓冲区时也只有普通读写有些教学用的软核处理器干脆不实现原子指令。在这些场景里想在逻辑上保证同一时刻只有一个执行流访问共享资源就只能靠算法层面的互相谦让。更现实的意义是思维训练。原子指令是硬件替你兜底而纯软件互斥迫使你直视并发最本质的问题两个执行流看到的共享变量可能不是同一份、变量与变量之间的可见性顺序可能颠三倒四。把这种思维练扎实了再看lock前缀到底帮你解决了哪几个问题才会有原来如此的感觉。2. 热身失败两个看似正确却翻车的经典设计2.1 方案一flag数组——两人同时“闯关”我们先把问题限定为两个线程共享一个资源每个线程的代码分为entry进入区、critical临界区、exit退出区。最直觉的设计是每个线程用一个布尔变量表达我想进。// 共享变量 volatile int flag[2] {0, 0}; // flag[i]1 表示线程i想进临界区 // 线程0 flag[0] 1; while (flag[1] 1) { // 忙等 } // 临界区 critical_section(); flag[0] 0; // 线程1 flag[1] 1; while (flag[0] 1) { // 忙等 } critical_section(); flag[1] 0;表面上每个线程进临界区前都会看一眼对方是否也想进对方想进就等着。问题出在先置flag再检查这个顺序执行的假设上线程0执行完flag[0] 1后线程1恰好也执行完flag[1] 1。此时两边都看到对方flag为1于是双双在while里转圈——死锁。或者更糟的序列两个线程都在检查时看到对方flag为0同时冲进临界区互斥直接失败。这个版本的病根在于flag只表达了我还愿不愿意进没有解决如果两个人都想进谁该让这个裁定问题。两个人都互不相让结局要么一起挤进去要么一起堵在门口。2.2 方案二谦让令牌turn——不撞了但会饿死既然各自表达意愿会陷入僵持另一个直觉是引入一个轮流令牌共享变量turn表示当前轮到谁。只有拿到令牌的线程才能进。volatile int turn 0; // 线程0 while (turn ! 0) { // 谦让等待 } critical_section(); turn 1; // 线程1 while (turn ! 1) { // 谦让等待 } critical_section(); turn 0;这个方案绝对不会两个同时进因为turn只有一个值条件判断保证了唯一性。但秃鹫也来了假设线程0进了临界区退出时把turn写成1然后线程0又立刻想要再次进入。它会在while (turn ! 0)里等待——可是令牌已经在1手里了线程1如果因为任何原因比如还没跑到或者被更高优先级任务抢占迟迟不执行那么线程0哪怕不需要访问任何资源也只能干瞪眼。更极致的情形线程1永久停摆线程0也永久进不了临界区。这暴露了绝对谦让的缺陷它把前进的权利完全交给了对方自己毫无主动权。互斥性解决了但无死锁和无饥饿败得一塌糊涂。3. 组合拳flag和turn叠加出的Dekker算法3.1 核心直觉想进的意愿与争议时的谦让分开处理两个失败方案给了两条深刻的教训flag方案解决的是表达意图但缺少仲裁turn方案解决了仲裁却让渡了主动权。Dekker算法的精妙之处在于把两者组合并且理清了各自职责——flag用来声明我想进turn用来裁定当两个人同时想进时谁让一让。关键细节在于何时使用turn。只有在发现自己和对方都想进时才需要动用令牌决出胜负然后由输的那方主动撤回自己的flag等赢家完成后再把flag立起来重新尝试。这不是简单的轮流而是平时各自争先、冲突时协商礼让既避免了两个人都横冲直撞又不会因为某个线程退出而永久卡死。3.2 完整代码与逐行拆解下面这份C语言风格的代码是我常用来教学的版本共享内存模型下可直接映射到大多数语言volatile int flag[2] {0, 0}; volatile int turn 0; // 0或1表示当前争议偏向让谁 void thread_0(void) { while (1) { flag[0] 1; // 1. 表达想进 while (flag[1] 1) { // 2. 对方也想进吗 if (turn ! 0) { // 3. 若轮到对方优先 flag[0] 0; // 4. 我暂时撤出竞争 while (turn ! 0) { // 5. 等令牌轮转回来 // 自旋 } flag[0] 1; // 6. 重新表达想进 } } // 7. 此时安全进入临界区 critical_section(); turn 1; // 8. 退出时把优先权让给线程1 flag[0] 0; // 9. 清除自己的意愿标志 // 10. 剩余区 } } void thread_1(void) { while (1) { flag[1] 1; while (flag[0] 1) { if (turn ! 1) { flag[1] 0; while (turn ! 1) { // 自旋 } flag[1] 1; } } critical_section(); turn 0; flag[1] 0; } }逐步解释这个代码是怎么动的第1步线程0先把flag[0]设为1宣告自己即将使用资源。这是表达意愿。第2步它检查线程1的flag。如果线程1不想进那没有任何竞争者线程0直接进入临界区。如果两个线程同时想进while (flag[1] 1)成立进入内部协商。此时看turn——这是全局的仲裁者。若turn 0说明这轮争议偏向线程0线程1那边在类似逻辑中会主动撤出线程0不必让位继续自我旋转直到对方flag变0。若turn ! 0说明仲裁者认为线程1应该优先线程0立刻将自己的flag撤为0第4步然后死等turn变成0第5步。这等于告诉对方这轮你先我不抢。当线程1用完资源把turn改回0后线程0重新立起flag第6步再次试着进入。对称地线程1的代码也遵循完全一致的控制流只是把索引和turn的判定反过来。两者拼在一起就形成了冲突时按turn仲裁、非冲突时快速通过的节奏。3.3 四段式场景推演从执行序列看懂互斥为了彻底理解这段代码我建议你自己把以下四个场景在纸上推演一遍场景A无竞争线程0单独进入。线程0将flag[0]置1看到flag[1]为0直接进入临界区。不做任何不必要的谦让。退出时设置turn1但此时线程1并不在等这个设置只影响未来可能的争议。场景B完全同时发起。线程0和线程1几乎同时把各自flag置1然后同时看到对方的flag也为1。此时若turn还是0线程1会发现turn ! 1于是主动撤下自己的flag并等待线程0发现turn 0不会撤flag只需等线程1的flag变0后即可进入。同理如果turn是1则角色互换。场景C线程0正在临界区线程1到来。线程1立flag后看到线程0的flag是1又检查turn。假设turn是0线程1会主动把flag撤下并等待。线程0正常退出、改turn、清flag线程1看到flag[0]0后重新立flag进入。互斥没有被破坏。场景D线程0用完再次申请与线程1再次竞争。由于每次退出临界区都会更新turn仲裁会交替偏向。这意味着没有任何线程能依赖运气连续抢到资源也决定了等待时间存在明确上界——这是Dekker算法无饥饿的关键。推演完这四个场景你会发现互斥的物理根源其实很朴素一个线程只有在对方flag为0对方不想要或对方主动撤让对方把flag置0时才会进入临界区。这两条通道都不会和另一个线程的进入条件同时成立。4. 严谨论证互斥性、无死锁、无饥饿是怎么成立的4.1 证明互斥盯住两个线程最后一次写flag口说无凭要证明互斥性我们引入一个简单的不变量。假设两个线程真的同时处于临界区考虑它们各自进入临界区前最后一次对flag数组的写操作。线程0进入临界区前必须越过两关之一要么它看到flag[1]0要么它经历过撤让再立起flag后看到flag[1]0。无论走那条路它在最后一次写flag[0]1之后持续检查flag[1]直到观察到flag[1]0。线程1若也想进入临界区那么它必然在某个时刻把flag[1]置为1并且在这个写操作之后观察flag[0]。如果两个线程都在临界区这两个观察并确认对方flag为0的事件必须先后发生。设线程0最后一次写flag[0]的时刻是T0线程1最后一次写flag[1]的时刻是T1。若T0早于T1那么线程0看到flag[1]0一定发生在T1之前而在这个观察之后、进入临界区之前线程1却把flag[1]写成了1。线程0却已经进入它不再检查flag[1]这会破坏只能看到对方为0才进的逻辑吗不会因为此时线程1还有后续检查它会等到flag[0]0。线程0进入临界区时flag[0]必定是1于是线程1一定会在while处自旋无法进入临界区。反过来同理。两个线程中至少有一个会被对方flag拦住矛盾消解互斥性得证。4.2 证明无死锁与无饥饿turn是永远不会丢失的令牌无死锁的关注点是只要至少有一个线程还想进临界区系统就不会永远僵持。证明思路是观察turn的流转。turn只会在线程退出临界区时修改且修改方向是0→1或1→0。如果两个线程都在互相等待一定是双方flag同时为1而turn属于其中一方此时持有turn特权的一方应当进入临界区另一方在等待。但持有turn的一方为何没有进入因为它也卡在检查对方flag的循环里——这只有在对方flag为1又不撤让时才可能。而根据代码turn偏向谁谁就不撤让不偏向的一方才撤让。所以持有turn的一方不会被对方拦住它要么已经进入要么正在临界区内部。一旦持有turn的一方完成退出它会修改turn并把flag清零。另一方从等待turn轮转中醒来重新立起flag发现自己已经获得仲裁权进入临界区。整个链条中没有一环会永久阻塞死锁排除。无饥饿则依赖一个更强的性质每个线程在两次连续进入临界区之间其对手至多进入有限次。原因是每次critical section结束后线程会把turn让给对方自己下次再要进时必须等对方主动让回。这形成了一个严格交替的次序即使某个线程非常热切地不断申请也只能每隔一轮进入一次。所以等待时间存在由对方临界区执行时间决定的上界不会出现某个线程永远轮不到的饥饿。4.3 对照并发算法的四项基本要求我们可以把Dekker算法放到并发互斥算法的标准评价框架下核对要求Dekker算法的表现说明互斥满足由观察到对方flag为0才能进这一条件保证两个线程不可能同时满足无死锁满足turn一定偏向某一方持有turn的一方不会被granted阻塞无饥饿满足turn在退出时强制轮转等待时间有上界无忙等不满足全部等待都是自旋循环CPU空转最后一行是重点。Dekker算法是典型的忙等算法等待者不释放CPU这在线程可抢占的系统里问题不大时间片会轮换但在协作式调度或单核优先级系统中可能造成低优先级线程饿死高优先级线程之类的优先级反转问题。理解这一点才知道为什么现代系统宁可多花几条原子指令也要提供真正能睡眠阻塞的锁。5. 教科书代码放在现代CPU上会翻车吗5.1 乱序执行、store buffer与内存可见性把上面的C代码原封不动搬进x86或者ARM的多核程序里你会发现它不一定工作。问题不在算法逻辑而在硬件模型。现代CPU执行普通读写指令时允许在不破坏单线程语义的前提下重排顺序。编译器也可能做类似的事情——把循环里的共享变量访问优化到寄存器里彻底绕开内存。对于Dekker算法这种重排是致命的。比如线程0在逻辑上先写flag[0]1再读flag[1]但处理器可能先执行读操作或者写操作虽然执行了却滞留在store buffer中其他核心暂时看不到。于是线程0可能读到旧值flag[1]0而认为没有竞争线程1也基于同样的重排做了相同判断——两个线程一起进入临界区教科书里的完美证明在现代硬件上瞬间失效。5.2 补救volatile、内存屏障与原子类型那么如何让Dekker算法在现代环境里真正可运行至少要做到三点使用原子类型把flag和turn都声明为std::atomic并给所有读写指定恰当的内存序。memory_order_seq_cst最保守能同时阻止编译器和CPU层面的重排。必要时显式插入屏障在写flag之后、检查对方flag之前插入std::atomic_thread_fence(std::memory_order_seq_cst)在修改turn前也插入屏障避免让出特权和清除意愿这两个操作被颠倒。避免编译器优化掉自旋变量在纯C语言里用volatile只是最低限度它保证变量被当作内存访问而不是寄存器缓存但并不能保证内存序。所以现代开发中靠volatile远远不够必须用带内存序语义的原子操作。我实测过一个纯volatile版Dekker在x86上的表现在大部分场景下好像没出事因为x86由于强内存模型store-load重排极少发生。可一旦换到ARM这类弱内存模型的架构或者开足编译器优化问题立刻暴露。这提醒我们算法证明建立在顺序一致性模型上真实硬件不是一个级别的模型。5.3 生产环境里还要不要用Dekker就我的实际项目经历来看几乎不会。有锁指令和操作系统提供的互斥锁为什么还要用一个自旋共享变量的算法Dekker的意义不在实用而在于它冲刷了互斥必须有硬件原语的固有认知并且为理解无锁编程的memory ordering问题提供了极佳的起点。真正的实用价值可能出现在两类地方一是不支持原子指令的极简裸机环境虽然我很少碰到二是作为教学和面试题检验对并发缺陷的直觉——很多面试者能写出flag方案但在追问两个同时想进怎么办时卡壳Dekker的协商撤让设计正好是对这个盲区的补课。6. 从Dekker到我写并发代码的习惯改变6.1 只靠共享变量写并发我学到的三个思维工具亲手把Dekker从纸面推演到现代架构上验证之后我整理出了三条今后写任何并发代码都会套用的思维工具。第一不要假定操作顺序。两个线程各自的步骤在时间轴上可以随意交错任何我先执行了A再执行B所以对方肯定看到A的结果的推论都要重新检查。Dekker之所以要那么复杂的撤让逻辑正是因为不能假定两个线程会按某个理想的先后次序运行。第二仲裁变量必须独立于请求变量。flag表达我想进turn表达争议时该谁让。把这两件事混在一个变量里几乎所有互斥方案都会出问题。后来我设计其他共享状态协议时也习惯性地按请求、授权、释放三个角色分离变量职责清晰不易错。第三等待必须要能让自己脱身。flag方案的死锁是因为等待者不主动改变自身状态Dekker里等待的一方会撤下flag把自己的状态变成我不参与了让对方能顺利通过。这个主动降低姿态以打破僵局的模式在解决分布式系统的活锁问题时同样适用。6.2 与同类算法的对照换个写法为何更简洁学习过程中我不可避免会拿它和更简洁的同类方案做对比。Peterson算法同样用flag和turn两个共享变量但它的思想是既然无法在冲突瞬间决定谁进不如直接把入口让给对方一次把仲裁放在竞争发生之前。而Dekker的思路是竞争发生时由turn裁定谁撤让它更像两个人走到窄门前发现同时到达时由门卫turn指定谁退一步。后者逻辑链条更长需要处理撤让-等待-重生三个状态对理解者更不友好。坦率说如果你只是为了快速完成一个双线程互斥任务我会建议先考虑Peterson这种更简练的方案。但从追溯并发算法设计演进的角度Dekker提供了更完整的失败-修正-验证过程这也是它至今仍被众多操作系统教材保留的原因。我在检验两者的等价性时还意外发现一个细节Dekker的互斥性不依赖turn的初值——即使初始为0或1互斥都成立只是先让谁进不同但Peterson的某个变体如果初值给错或者更新位置不对会直接导致互斥失败。这种初值敏感性差异在面试辨析题里很常见也提醒我写并发算法时永远要检查初始化条件。6.3 一点小建议动手仿真而非只读代码最后分享一个我在学习Dekker时觉得最有效的方法找个支持共享内存多线程的仿真环境比如在任意主流编程语言里开两个线程按Dekker的步骤去实现并人为制造各种调度错位。专门配合乱序、抢占、延时去运行它直到你能预判出每一个打印顺序。很多人说看了证明就懂了但真正动手模拟各种交错之后那种对变量状态转变的肌肉记忆是看任何博客都给不了的。并发算法的学习从来不是背结论而是把每一个状态转换都内化成直觉。Dekker算法这个半个多世纪前的纯软件解法在今天仍能提供这种独特而强烈的训练。