深入解析Peterson算法：并发编程中的经典互斥解决方案

2026/8/5 3:03:39

1. 项目概述：为什么我们需要理解Peterson算法？

在并发编程的世界里，我们常常需要协调多个线程或进程对共享资源的访问，比如一个共享的计数器、一个文件，或者一块内存区域。如果协调不当，就会出现数据竞争，导致程序结果不可预测，甚至直接崩溃。这就像两个人在同一时间都想通过一扇只能容纳一人的旋转门，如果互不相让，结果就是卡在门口，谁也过不去。为了解决这个“卡门”问题，早期的计算机科学家们提出了各种方案，而Peterson算法就是其中一颗璀璨的明珠。

Peterson算法由Gary L. Peterson在1981年提出，它是一个经典的、纯软件实现的、用于两个进程（或线程）互斥访问临界区的算法。说它“经典”，是因为它简洁、优雅，完美地展示了并发控制的核心思想；说它“纯软件”，是因为它不依赖于任何特殊的硬件原子指令（比如现代CPU的compare-and-swap），仅通过读写共享变量来实现；说它“形象”，是因为其背后的逻辑可以用非常生活化的场景来类比理解，这也是我们今天要深入探讨的重点。

对于任何想要深入理解操作系统、并发编程底层原理的开发者来说，Peterson算法都是一个绕不开的里程碑。它不仅仅是教科书上的一个知识点，更是理解现代锁、信号量等高级同步原语的思想基石。通过形象地分析它，我们能透彻地理解“忙等待”、“互斥”、“饥饿”这些并发中的核心概念，以及算法设计者是如何巧妙地用简单的“谦让”逻辑，解决了复杂的竞争问题。无论你是正在学习操作系统课程的学生，还是希望夯实底层知识的工程师，这篇分析都将带你穿越表象，直击Peterson算法的灵魂。

2. 核心思想与生活化类比：两个绅士的进门礼仪

要理解Peterson算法，我们不妨先忘掉代码，构思一个场景：假设有一间珍贵的藏书室（临界区），每次只允许一个人进入阅读。门口有两位彬彬有礼的绅士，Alice和Bob，他们都想进去。如何设计一套规则，确保永远不会两人同时进入，并且最终每个人都能有机会进去呢？

最朴素的想法是“轮流制”。Alice进去一次，然后Bob进去一次。但这需要他们严格记忆轮次，如果其中一人中途离开或忘记顺序，规则就失效了。另一种想法是“挂牌制”，门口只有一块“请进”的牌子，谁拿到牌子谁进去。但这又会产生新的问题：如果两人同时看到牌子并伸手去拿，还是可能产生冲突。

Peterson算法的精妙之处在于，它结合了两种“意愿”的表达，并引入了一个关键的“谦让”机制。算法需要两个共享变量和一个局部变量：

boolean flag[2]: 一个布尔数组，flag[0]代表Alice想进门的意愿，flag[1]代表Bob想进门的意愿。初始都为false（不想进）。
int turn: 一个整型变量，表示现在“轮到”谁谦让。取值0或1。
局部变量other: 代表另一个人的编号。

现在，让我们把算法规则翻译成两位绅士的对话：

Alice想进门时（进程0）她会这样做：

举起手，表示意愿：flag[0] = true（Alice说：“我想进去。”）
礼貌地让对方先走：turn = 1（Alice对空气说：“现在该Bob您先请。”）
在门口等待，直到条件满足：她会不停地检查两个条件：
- 条件A：Bob是不是不想进？（flag[1] == false）
- 条件B：是不是确实轮到我了？（turn == 0）只要条件A OR 条件B有一个成立，她就可以进入。用白话讲就是：“只要Bob不想进，或者现在明确轮到我了，我就可以进去。”否则，她就在门口踱步（忙等待）。

Bob的逻辑完全对称。

这个“等待条件”是算法的核心魔法。为什么它能保证互斥（不会两人同时进）？让我们分析最危险的时刻：两人同时都想进。

两人几乎同时执行了步骤1和2：都举起了手（flag[0]=true, flag[1]=true），并且都客气地让对方先走（turn被先后设置为1和0）。由于turn是共享变量，后写入的会覆盖先写入的。假设最终turn = 0。
此时，Alice检查条件：flag[1] == true(Bob举手了) 且turn == 0(轮到我)。条件A不成立，条件B成立（false OR true = true），所以Alice可以进入。
Bob检查条件：flag[0] == true(Alice举手了) 且turn == 0(现在轮到Alice)。条件A不成立，条件B也不成立（false OR false = false），所以Bob必须等待。
直到Alice出来后，放下手（flag[0] = false），Bob的条件A变为true，他才能进入。

你看，关键就在于turn这个变量。它就像一个“一次性令牌”，并且最后设置它的人会失去优先权。因为等待条件检查的是“对方不想进”或“轮到我”。当两人竞争时，“轮到我”这个条件只对其中一人成立，而另一个人因为刚刚把turn设成了对方，所以“轮到我”条件不成立，又因为对方举着手，所以必须等待。这就强制实现了互斥。

注意：这个“谦让”的步骤（turn = other）至关重要。如果去掉它，算法就会死锁。试想两人都举手，然后都等待对方放手，那就永远等下去了。turn变量打破了这种对称性。

3. 算法实现与逐行解析

理解了形象化的比喻，我们来看具体的代码实现。以下是Peterson算法最标准的双进程版本：

// 共享变量 bool flag[2] = {false, false}; int turn = 0; // 进程 Pi (i 为 0 或 1) void enter_critical_section(int i) { int j = 1 - i; // 另一个进程的索引 flag[i] = true; // 步骤1：举手，表示我想进入 turn = j; // 步骤2：谦让，表示让对方先来 // 步骤3：等待条件 while (flag[j] == true && turn == j) { // 忙等待：如果对方举手了，并且当前轮到他，我就等待 // 什么也不做，空循环 } // 条件满足，进入临界区 // ... 执行临界区代码 ... } void exit_critical_section(int i) { flag[i] = false; // 步骤4：放手，表示我出来了 }

我们来逐行解析，并解释每一步的“为什么”：

flag[i] = true;(举手)

目的：声明自己的意图。这是互斥算法的基本要求，一个进程必须让其他进程知道它想要进入临界区。
为什么先举手？顺序很重要。如果先谦让(turn=j)，再举手，可能会出现一个时间窗口：turn已设为对方，但自己还未举手。此时对方可能看到turn对自己有利，且你未举手，从而进入临界区。紧接着你也举起了手，但因为turn已设为对方，你将陷入等待。这虽然不会破坏互斥，但增加了不必要的延迟。先举手能更早地宣告竞争意图。

turn = j;(谦让)

目的：打破对称，解决死锁。这是Peterson算法的点睛之笔。它主动将优先权让给对方。
为什么是对方(j)？因为如果都设为自己，那么turn的值在竞争后可能相同，无法起到决定谁先进入的作用。设为对方，确保了在竞争情况下，turn的值会是一个确定的值（后写入者胜出），并且最后设置turn的进程会让自己处于等待状态。这创造了一种“礼让后生效”的规则。

while (flag[j] == true && turn == j);(等待)

条件分解：
- flag[j] == true：对方是否举手想进？如果不想，那我自然可以进。
- turn == j：现在是否明确轮到对方？这里的“轮到”是由上一步的谦让动作决定的。
逻辑关系：while循环继续的条件是“对方举手并且轮到他”。也就是说，只要这两个条件同时成立，我就必须等。只要有一个不成立，我就可以进入。
- 如果对方没举手(flag[j]==false)，不管turn是谁，我进。
- 如果对方举手了，但turn是我(turn==i)，说明在我最后一次设置turn后，对方也设置了turn（覆盖成了我），根据“最后谦让者等待”原则，现在该我进，我进。
为什么是“忙等待”(Busy Waiting)？在等待时，进程会占用CPU循环检查条件，这确实会浪费CPU资源。Peterson算法是一种“自旋锁”的思想雏形。在现代系统中，纯忙等待不是最佳实践，通常会结合线程调度（如yield()）或硬件支持。但在这个纯软件、教学性质的算法中，忙等待是最简单的实现方式，它清晰地展示了同步的逻辑。

flag[i] = false;(放手)

目的：退出时清除自己的意图。这样，正在等待的另一个进程就会发现flag[i]==false，从而满足flag[j]==false的条件，跳出忙等待，进入临界区。
重要性：如果退出时不放手，另一个进程将永远等待下去，导致“饥饿”。这确保了算法的进展性。

4. 正确性证明：互斥、进展与有限等待

一个正确的互斥算法必须满足三个条件：

互斥：任何时刻，最多只有一个进程在临界区内。
进展：如果没有进程在临界区内，并且有进程想进入，那么最终必须有某个进程能进入。
有限等待：一个进程从提出进入请求到获准进入，等待时间必须是有限的。即不会“饥饿”。

我们来论证Peterson算法如何满足这三条。

4.1 互斥性证明反证法：假设两个进程P0和P1同时进入了临界区。

同时进入意味着它们都成功通过了while等待循环。
对于P0，通过循环的条件是：!(flag[1]==true && turn==1)，即flag[1]==false || turn==0。
对于P1，通过循环的条件是：!(flag[0]==true && turn==0)，即flag[0]==false || turn==1。
由于它们都进入了，所以两个条件必须同时为真：
- (条件A)(flag[1]==false || turn==0) == true
- (条件B)(flag[0]==false || turn==1) == true
因为两个进程都在临界区，所以它们肯定都举了手：flag[0]==true且flag[1]==true。
将flag为真代入条件：
- 条件A变为：(false || turn==0)，即turn==0必须为真。
- 条件B变为：(false || turn==1)，即turn==1必须为真。
这要求turn同时等于0和1，这不可能。因此假设错误，两个进程不可能同时进入临界区。互斥得证。

4.2 进展性证明进展性要求系统不会“卡死”。考虑以下场景：没有进程在临界区，但至少有一个进程想进。

如果只有一个进程Pi想进（flag[i]=true, flag[j]=false），那么Pi的等待条件flag[j]==false立即满足，它可以无障碍进入。
如果两个进程都想进，那么根据turn的值，其中一个必然满足等待条件。
- 因为turn非0即1，假设turn=0。
- 那么P0检查：flag[1]==true && turn==0=>true && false=>false，循环条件不成立，P0进入。
- P1检查：flag[0]==true && turn==0=>true && true=>true，循环条件成立，P1等待。
只要在临界区内的进程最终会退出（flag[i]=false），等待的进程就能进入。因此，系统不会出现所有想进的进程都永远等待的情况。进展性得证。

4.3 有限等待（无饥饿）证明这是比进展性更强的要求。它要求一个进程不会因为其他进程的反复进入而永远被阻塞。

假设P0想进入，但P1正在临界区或也同时想进入。
在最坏情况下，P1退出临界区后，立刻又想进入。它执行flag[1]=true; turn=0;。
注意，此时turn被P1设为了0。这意味着“轮到P0”。
现在，P0和P1都举手了，且turn=0。根据等待条件：
- P0:flag[1]==true && turn==0=>true && false=>false，P0可以进入。
- P1:flag[0]==true && turn==0=>true && true=>true， P1必须等待。
关键点来了：只要P1在退出临界区后，想再次进入，它就会把turn设为0，从而将进入权拱手让给P0。因此，P0至多等待P1完成当前临界区的一次执行后，就一定能够进入。P1不可能连续进入两次而让P0一直等待。有限等待得证。

实操心得：在理解证明时，亲手画一下两个进程的执行序列图（Timeline）会非常有帮助。用横轴表示时间，纵轴表示两个进程的指令流，标注出flag和turn值的变化，你能直观地看到互斥是如何在时间交错中得以维持的。这是理解任何并发算法的黄金方法。

5. 局限性、现代意义与扩展思考

尽管Peterson算法在理论上如此优美，但在现代编程实践中，我们几乎不会直接使用它。这是为什么呢？

5.1 主要局限性

严格限于两个进程：算法核心设计针对两个竞争者。虽然存在扩展到N个进程的“过滤锁”算法，但其复杂度和性能远不如现代同步原语。
忙等待消耗CPU：while循环空转会持续占用CPU核心，这在单核时代是灾难，在多核时代也是极大的资源浪费，会导致高功耗和低效的系统调度。
内存序与编译器优化问题：这是最致命的一点。现代编译器和CPU为了性能，会对指令进行重排序（Reordering）。例如，编译器可能为了优化，将turn = j重排到flag[i] = true之前。或者，在多核CPU上，一个核心对flag[i]的写入，可能不会立即被另一个核心看到（可见性问题）。这都会破坏算法隐含的“顺序”假设，导致互斥失败。
不具备可重入性：同一个进程不能递归地进入临界区，否则会死锁在自己身上。

5.2 现代意义：思想的价值远大于代码既然如此，我们为什么还要学习它？

教学典范：它是讲解互斥、同步、并发问题本质的完美案例。理解了Peterson，就理解了锁要解决的核心问题。
理解硬件原语的基础：现代锁（如互斥锁、自旋锁）的实现，最终依赖于硬件提供的原子操作（如Test-and-Set, Compare-and-Swap, Load-Linked/Store-Conditional）。Peterson算法展示了在没有这些原子指令时，软件能达到的极限。理解了软件的局限，才能更好地理解硬件支持的必要性。
内存模型的启蒙：Peterson算法失效的风险，直接引出了内存一致性模型（Memory Consistency Model）的重要性。为了让它正确工作，我们需要在flag和turn的读写操作之间插入内存屏障（Memory Barrier）或使用原子变量（std::atomicin C++,volatile的正确使用等）。这促使我们思考并发环境下数据可见性和操作顺序的深层问题。

5.3 扩展思考：从Peterson到现代同步

如何解决忙等待？引入操作系统调度。当进程需要等待时，主动放弃CPU（如调用sched_yield()或进入睡眠状态），让操作系统去运行其他进程。这就是“睡眠锁”或“互斥锁”的基本思想。
如何解决编译器/CPU重排序？使用语言或硬件提供的内存序约束。在C++中，可以使用std::atomic<bool>并指定内存序（如std::memory_order_seq_cst）。这告诉编译器和CPU，此处的读写顺序不能随意调换。
如何扩展到多线程？基于Peterson思想的“过滤锁”算法层级太多，效率低。现代做法是使用“排队锁”，如MCS锁、CLH锁，它们能更好地在多核环境下减少缓存一致性流量，提高扩展性。

一个“现代化”的、用于教学演示的Peterson算法实现（使用C++原子操作）可能长这样：

#include <atomic> #include <thread> class PetersonLock { private: std::atomic<bool> flag[2]; std::atomic<int> turn; public: PetersonLock() : flag{false, false}, turn(0) {} void lock(int myId) { int other = 1 - myId; flag[myId].store(true, std::memory_order_seq_cst); // 举手，保证写顺序 turn.store(other, std::memory_order_seq_cst); // 谦让，保证写顺序 // 等待条件：使用与store相同的内存序加载，保证读到最新值 while (flag[other].load(std::memory_order_seq_cst) && turn.load(std::memory_order_seq_cst) == other) { // 可以加入 std::this_thread::yield() 来减少CPU占用 } } void unlock(int myId) { flag[myId].store(false, std::memory_order_seq_cst); // 放手 } };

这个版本使用了顺序一致性内存序，确保了操作的全局顺序，从而在支持该模型的硬件上能正确工作。当然，实际生产环境中的锁要复杂和高效得多。

6. 常见误解与疑难排查

在学习Peterson算法的过程中，有几个常见的“坑”容易让人困惑。

6.1 为什么turn变量是必要的？只用flag不行吗？这是最常见的误解。我们尝试设计一个只有flag的算法：

P0:flag[0]=true; while(flag[1]);进入临界区。
P1:flag[1]=true; while(flag[0]);进入临界区。想象这个执行序列：

P0设置flag[0]=true。
P1设置flag[1]=true。
P0执行while(flag[1])，发现为真，等待。
P1执行while(flag[0])，发现为真，等待。死锁！两个进程都在等待对方放手，但谁也无法进入临界区去放手。turn变量的引入，就是为了在双方都举手时，提供一个明确的、唯一的决策者，打破这种对称僵局。

6.2 两个进程的turn赋值语句，会不会相互干扰？会，而且这正是算法期望的。turn是一个共享变量。如果P0和P1几乎同时执行turn = 1和turn = 0，最终turn的值取决于哪个写操作后生效。在单核CPU上，这由指令交错决定；在多核CPU上，这由缓存一致性协议和内存写入顺序决定。但无论如何，最终turn会是一个确定的值（0或1）。这个“后写入者胜出”的机制，恰好决定了谁该等待。

6.3 在等待循环里，如果对方一直不退出，会不会饿死？根据前面的“有限等待”证明，不会。因为对方（比如P1）退出临界区后，如果它想再次进入，必须执行flag[1]=true; turn=0;。这个turn=0的动作，就把进入权明确地交给了P0。所以P0至多等待P1执行完当前临界区的一次操作。P1不可能连续获得两次进入权而让P0一直等待。

6.4 现代CPU和编译器下，这个算法为什么可能失效？假设如下代码：

flag[i] = true; // 写操作 A turn = j; // 写操作 B while (flag[j] && turn == j); // 读操作 C 和 D

编译器和CPU为了优化，可能会：

编译器重排序：认为B和A没有依赖关系，将B提到A之前执行。
CPU乱序执行：即使编译器没重排，CPU也可能让B的写操作先于A提交到内存。
缓存可见性：核心1写了flag[i]=true，但这个值可能还停留在核心1的缓存里，没有同步到核心2的缓存中。核心2在循环中读到的flag[i]可能还是false。

如果B先于A生效，就可能出现：P0设置了turn=1，但flag[0]=true还未被P1看到。P1看到turn=1（对自己有利）且flag[0]=false（以为P0不想进），于是P1进入临界区。同时P0看到flag[1]=true且turn=1（轮到你），于是P0也进入临界区。互斥被破坏！

排查与解决思路：

使用原子变量：将flag和turn声明为原子类型（如C++std::atomic）。
设置内存屏障：在A和B之间，以及循环的读取操作前，插入合适的内存屏障指令，确保写操作的顺序性和读操作的可见性。在C++中，通过指定std::memory_order_seq_cst可以达到这个效果。
理解松弛内存序：如果你使用更宽松的内存序（如memory_order_relaxed），就必须非常小心地组合使用memory_order_acquire和memory_order_release来建立同步关系，这非常复杂且容易出错。对于Peterson算法，顺序一致性是最简单安全的选择。

Peterson算法就像并发编程领域的一把瑞士军刀，小巧、精致，包含了解决竞争问题的基本工具和思想。虽然我们不再直接用它来构建生产系统，但通过剖析它，我们学到了互斥的本质、软件方案的局限、以及硬件内存模型的重要性。下次当你使用std::mutex.lock()或者pthread_mutex_lock()时，不妨想一想，在这个简洁的API之下，可能正闪烁着Peterson算法那“举手-谦让-等待”的智慧光芒。理解底层原理，永远能让你在面对更复杂的并发bug时，多一份从容和底气。