1. 从“Zeroin”项目看并发编程的基石最近在整理一些老项目的代码翻到了一个名为“Zeroin”的早期实验性项目。这个项目名字听起来有点抽象其实它的核心目标很简单探索如何在多线程环境下不使用任何现代高级同步原语比如操作系统提供的锁、信号量仅凭最基本的读写操作来实现两个线程之间的互斥访问。听起来像是计算机科学史前时代的事情没错这正是并发编程的“石器时代”考古。而“Zeroin, Part 1”要啃的第一块硬骨头就是Dekker‘s Algorithm戴克算法。如果你对并发编程稍有了解可能会觉得现在有pthread_mutex_t、std::mutex、synchronized关键字等等为什么还要去研究一个半个多世纪前1965年由荷兰数学家T. J. Dekker提出的算法这正是这个项目的价值所在。理解Dekker算法不是让你在工作中去写它而是为了彻底搞懂“互斥”这个概念究竟是如何从无到有被构建出来的。它像是一把钥匙能帮你打开理解现代锁、内存屏障、甚至CPU缓存一致性协议的大门。当你被“死锁”、“活锁”、“内存可见性”这些问题折磨时回头看看这个最原始的解决方案往往会有豁然开朗的感觉。简单来说Dekker算法解决了两个线程假设叫P0和P1如何安全地进入一个“临界区”比如修改一个共享变量的问题而且它保证了“有限等待”不会有一个线程永远等不到。它只使用了两个布尔型标志位flag[0]和flag[1]和一个整型轮转变量turn通过巧妙的标志设置与检查顺序实现了互斥。接下来我们就钻进这个算法的内部看看它到底是怎么运转的以及为什么在今天它依然是一个绝佳的教学案例和思维训练工具。2. Dekker算法的核心机制一场精心设计的“谦让舞”Dekker算法的精妙之处在于它通过一套规则让两个线程在都想去临界区时能够有序地“协商”谁先进入而不是一拥而上导致数据混乱。我们先看它的经典伪代码结构然后一步步拆解其逻辑。线程P0的算法逻辑// 初始化 flag[0] false; flag[1] false; turn 0; // 或 1 表示初始让谁先尝试 // 线程P0的循环 while (true) { flag[0] true; // P0举手示意“我想进临界区” while (flag[1] true) { // 检查P1是否也举手了 if (turn ! 0) { // 如果现在不该我轮转值不是0 flag[0] false; // P0暂时放下手礼让 while (turn ! 0) { // 忙等待直到轮到我turn变为0 } flag[0] true; // 再次举手 } } // 临界区Critical Section // ... 执行需要互斥的操作 ... turn 1; // 退出时把机会让给P1 flag[0] false; // P0放下手表示我出来了 // 剩余区Remainder Section }线程P1的逻辑完全对称只是将所有的0和1互换。2.1 算法状态机的三重保障这个算法之所以能工作依赖于三个核心变量交织出的状态机flag[i]意图标志。flag[i] true直白地宣告“线程i有意进入临界区”。这是一个“先举手后进门”的协议避免了直接冲进去的冲突。turn轮转变量。这是一个仲裁者。当两个线程都举手flag[0]和flag[1]都为真时turn决定谁该让路。它保证了在竞争情况下不会两个线程互相谦让导致谁也无法前进即避免活锁。检查与设置的顺序这是算法的灵魂。注意P0的操作顺序先设置自己的flag[0]为真然后才去检查flag[1]。这个顺序至关重要。如果反过来先检查再设置会出现一种情况两个线程同时检查对方的flag发现都是false然后都设置自己的flag为true接着都认为对方没举手而进入临界区互斥就被破坏了。2.2 一次完整的“握手”流程解析让我们模拟一次典型的竞争场景假设初始turn 0步骤1P0和P1几乎同时执行都设置了flag[0]true和flag[1]true。步骤2双方都进入内层while循环检查对方的flag。因为对方的flag都是true所以条件成立进入if判断。步骤3检查turn。当前turn0。对P0if (turn ! 0)为假因此它不执行if块内的礼让操作而是持续在while (flag[1] true)这个空循环里等待忙等待。这被称为“自旋”。对P1if (turn ! 1)为真因为turn0不等于1因此P1进入if块。步骤4P1执行礼让操作flag[1] false放下手然后进入while (turn ! 1)循环自旋等待。步骤5P1在等待时P0仍在自旋检查flag[1]。一旦P1将flag[1]设为falseP0立即跳出while (flag[1] true)循环成功进入临界区。步骤6P0退出临界区时执行turn 1将机会让给P1然后flag[0] false。步骤7turn变为1后在步骤4中等待的P1立即跳出while (turn ! 1)循环重新设置flag[1]true然后检查flag[0]。此时P0的flag[0]已为false所以P1也能顺利进入临界区。这个过程就像两个绅士在门口相遇都举手示意要进门。他们约定看一个令牌turn令牌在谁手另一方就主动退后一步、放下手等待。等拿令牌的那位进去再出来后会把令牌交给等待的那位。通过“举手-看令牌-礼让”这套固定舞步确保了任何时候只有一人能进门。注意这里的“忙等待”Busy Waiting是早期算法的一个特点线程会在循环中空转消耗CPU。这在现代多核编程中通常是需要避免的低效行为但在理解原理时它是最清晰的模型。3. 为什么Dekker算法是正确且公平的一个互斥算法必须满足三个基本条件互斥Mutual Exclusion、空闲让进Progress、有限等待Bounded Waiting。我们来逐一验证Dekker算法。3.1 互斥性的证明互斥意味着不可能有两个线程同时处于临界区。假设反证法成立即P0和P1同时进入了临界区。那么它们进入之前各自的while (flag[1/0] true)循环条件都必须为假。也就是说在P0进入的瞬间它看到flag[1] false在P1进入的瞬间它看到flag[0] false。但是根据算法的顺序一个线程在进入临界区前一定已经将自己的flag设为了true。所以如果两者都进入了意味着在某个时间点flag[0]和flag[1]都曾为true。那么后设置flag的线程在设置之前一定会先看到对方已经为true的flag从而被阻塞在内层while循环或礼让流程中根本无法进入临界区。这与假设矛盾。因此互斥性得证。3.2 空闲让进与有限等待空闲让进指当没有线程在临界区时如果有线程想进入不应该被无限期阻挡。Dekker算法满足这一点如果没有竞争另一个线程的flag为false那么想进入的线程会直接通过检查进入临界区。有限等待指一个线程从提出申请到进入临界区等待时间是有上限的。这是由turn变量保证的。考虑最坏情况P0和P1都想进入且turn1。P0可能会被P1阻挡一次因为turn ! 0P0需要礼让。但当P1进入并退出临界区时它必定会将turn设置为0。这样下一轮竞争中turn就有利于P0P0至多再等待P1进入一次后就能保证获得进入权。因此任何一个线程最多在连续两次竞争中失败后第三次一定能成功进入。这就实现了有限等待避免了“饿死”。4. 从理论到实践在现代系统上模拟Dekker算法的陷阱在“Zeroin”项目中用C语言实现Dekker算法时你很快会发现一个严峻的问题代码按照逻辑写出来了但运行结果时对时错数据竞争依然发生。这不是算法逻辑错了而是我们遇到了现代计算机体系结构带来的挑战。4.1 内存可见性与编译器优化我们来看一个看似正确的C语言实现片段// 共享变量 int flag[2] {0, 0}; int turn 0; // 线程0的入口函数 void *thread0(void *arg) { for (int i 0; i 1000000; i) { flag[0] 1; // 举手 while (flag[1] 1) { if (turn ! 0) { flag[0] 0; while (turn ! 0) {} // 忙等待 flag[0] 1; } } // 临界区递增共享计数器 counter; turn 1; flag[0] 0; } return NULL; }问题出在哪里编译器优化为了提高速度编译器可能会对指令进行重排序或者将频繁读取的变量缓存到寄存器中。例如它可能认为while (flag[1] 1)循环内的flag[1]值不会改变因为另一个线程修改的是内存而本线程的寄存器副本没变从而将其优化成只读一次导致线程无法看到另一个线程对flag[1]的更新永远跳不出循环。CPU乱序执行与内存模型即使编译器不做激进优化现代CPU为了性能也会乱序执行指令并且每个核心可能有自己的缓存。线程P0对flag[0]1的写入可能不会立即被线程P1的CPU核心看到因为写入还停留在P0的核心缓存里没有刷新到共享的主内存。这就是所谓的“内存可见性”问题。4.2 让Dekker算法在现代硬件上“活过来”为了让这个古老的算法能在今天的多核CPU上正确运行我们必须使用内存屏障Memory Barrier或原子操作Atomic Operations来对抗编译器和CPU的优化。使用volatile作用有限在C/C中volatile关键字告诉编译器不要把这个变量优化到寄存器里每次读写都必须从内存中进行。这解决了编译器缓存的问题但并不能解决CPU缓存一致性和指令重排序的所有问题。因此仅用volatile是不够的在高并发下依然可能出错。使用编译器屏障GCC/Clang提供了__asm__ __volatile__( ::: memory)这样的内联汇编语句作为一个通用的编译器屏障阻止屏障前后的读写操作被编译器重排序。这比volatile更强但依然属于软件层面。使用CPU内存屏障在x86架构上mfence指令是一个全内存屏障能确保屏障前的所有内存操作store/load都完成后才执行屏障后的操作。在实现Dekker时我们可能需要在关键的位置插入屏障。使用原子操作与顺序一致性模型这是最现代、最推荐的做法。使用C11标准的stdatomic.h或C11的atomic。我们可以将flag和turn声明为原子变量atomic_int或atomic_bool并使用memory_order_seq_cst顺序一致性内存顺序进行所有操作。顺序一致性是最强的内存模型它保证了所有线程看到的原子操作顺序都是一致的相当于在所有原子操作周围都加上了全内存屏障。这虽然会损失一些性能但能完美地让Dekker算法逻辑正确执行。一个使用C11原子操作的修正版关键部分示例如下#include stdatomic.h atomic_int flag[2] {ATOMIC_VAR_INIT(0), ATOMIC_VAR_INIT(0)}; atomic_int turn ATOMIC_VAR_INIT(0); void *thread0(void *arg) { for (int i 0; i 1000000; i) { atomic_store_explicit(flag[0], 1, memory_order_seq_cst); // 举手 while (atomic_load_explicit(flag[1], memory_order_seq_cst) 1) { if (atomic_load_explicit(turn, memory_order_seq_cst) ! 0) { atomic_store_explicit(flag[0], 0, memory_order_seq_cst); while (atomic_load_explicit(turn, memory_order_seq_cst) ! 0) { // 忙等待但此时对turn的读取是原子的、顺序一致的 } atomic_store_explicit(flag[0], 1, memory_order_seq_cst); } } // 临界区 counter; // 注意counter本身也需要是原子的或受保护 atomic_store_explicit(turn, 1, memory_order_seq_cst); atomic_store_explicit(flag[0], 0, memory_order_seq_cst); } return NULL; }通过这个实践你会深刻体会到一个逻辑上正确的并发算法在真实的计算机系统上运行还需要考虑内存模型这一层。这恰恰是学习Dekker算法的另一大收获它逼着你去理解硬件和编译器对并发程序的影响。5. Dekker算法的局限性与历史地位尽管Dekker算法在理论上优雅地解决了两个线程的互斥问题但它有明显的局限性这也解释了为什么它没有在工业界被直接采用。5.1 无法扩展到N个线程这是最致命的缺点。Dekker算法的核心协商机制依赖于一对一的“谦让”和唯一的turn变量。当线程数量增加到3个或更多时这种二元协商机制就崩溃了。你无法用一个简单的turn变量在多个线程间做出公平的仲裁。后来出现的Peterson算法同样是两个线程更简洁但扩展性问题依旧。直到更复杂的面包店算法Lamport‘s Bakery Algorithm出现才在理论上解决了N线程的互斥问题但其复杂度和性能开销也大大增加。5.2 忙等待消耗CPU资源算法中包含了while循环空转这在等待时会持续占用CPU核心。对于可能等待较长时间的场景例如等待I/O这是极大的资源浪费。现代操作系统的锁实现如futex会结合忙等待和线程休眠在短期等待时自旋长期等待时让出CPU以达到效率最优。5.3 对现代硬件不友好如前所述它严重依赖顺序内存模型。在现代的弱内存模型处理器如ARM、PowerPC上不施加严格内存屏障的正确实现将异常困难且低效。5.4 历史地位与教学意义虽然不实用但Dekker算法的历史地位无可替代。它是第一个被证明正确的、解决了两线程互斥且满足有限等待条件的软件算法。它清晰地展示了互斥协议所需的几个基本要素表达意图flag、解决竞争turn、正确的操作顺序。后来的所有无锁算法、同步原语其思想内核都能追溯到这些简单的概念。在“Zeroin”项目中实现它就像程序员的一次“朝圣”。你亲手用最原始的工具共享变量搭建了一个同步设施这个过程中对竞争条件的每一分担忧对内存操作的每一次斟酌都会深化你对“并发”本质的理解。当你再使用std::mutex.lock()时你看到的将不再是一个黑盒魔法而是一套复杂但有序的协商规则在底层默默工作。6. 超越Dekker它在现代并发中的思想回声Dekker算法的思想并未过时它以各种形式存在于现代并发编程中。自旋锁SpinlockDekker算法中的忙等待正是自旋锁的核心行为。现代自旋锁如Linux内核的spinlock_t使用原子操作如Test-and-Set, Compare-and-Swap来实现更高效、可扩展的flag检查与设置其“自旋等待”的逻辑与Dekker一脉相承。互斥锁Mutex的实现基础用户态的互斥锁库在竞争不激烈时往往会先尝试一段类似自旋锁的乐观获取。其底层状态管理锁定、未锁定、可能有等待者的思想复杂度远超Dekker但解决“谁该进入”这个核心问题的思路是相通的。无锁编程中的标志位在一些无锁数据结构中我们经常能看到使用标志位类似flag来指示某个节点是否被占用、是否正在修改。管理这些标志位的原子操作和内存顺序是Dekker算法精神在更精细层面的体现。硬件内存屏障的理解为了正确实现Dekker而学习内存屏障这直接帮助你理解Java中的volatile、C中的std::atomic、以及各种内存顺序memory_order_relaxed,acquire,release,seq_cst的深层含义。你知道它们为什么存在是为了解决什么样的问题。所以下次当你调试一个诡异的并发bug或者阅读某个高性能无锁队列的源码时不妨想想Dekker算法。这个诞生于大型机时代的古老智慧依然在每一个多核处理器的缓存行里在每一段并发安全的代码中静静地发挥着作用。它提醒我们最复杂的系统往往建立在最清晰、最坚定的基础概念之上。
