第一次看到“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，直接进入临界区。不做任何不必要的谦让。退出时设置turn=1，但此时线程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算法这个半个多世纪前的"纯软件解法"，在今天仍能提供这种独特而强烈的训练。
