关于Peterson's algorithm下双线程能否同时进入busy wait循环的技术问询

你的理解不正确，Peterson算法的核心逻辑保证了不会出现两个进程同时陷入忙等、无限挂起的情况，下面结合你给出的代码和执行假设具体分析：

Peterson算法的C++实现 #

#include <thread>
#include <atomic>
int main(){
  std::atomic<bool> flag[2] = {false,false};
  std::atomic<int> turn = {0};
  std::thread t1([&](){
     flag[0] = true;  // flag_set_0
     turn = 1;    // turn_set_0
     while(flag[1] && turn == 1){  // flag_read_0, turn_read_0
         // busy wait
     }
     // critical section
     flag[0] = false;
  });
  std::thread t2([&](){
     flag[1] = true;  // flag_set_1
     turn = 0;  // turn_set_1
     while(flag[0] && turn == 0){ // flag_read_1, turn_read_1
         // busy wait
     }
     // critical section
     flag[1] = false;
  });
  t1.join();
  t2.join();
}

你假设的执行场景的错误点 #

你给出的执行序列和全序看似符合线程内的执行顺序约束，但存在两个关键误解：

1. 忙等是持续循环检查，而非单次判断 #

你假设t1执行while(flag[1] && turn ==1){}后会一直停在循环里，但实际上这个循环会持续重新检查条件。当t2执行turn = 0后，t1下一次循环检查时，turn ==1的条件会立即不成立，循环会终止，t1会进入临界区。

2. 忽略了turn变量的让步逻辑 #

Peterson算法中，turn变量的作用是明确“当前轮到哪个进程进入临界区”：

• 当t1设置turn =1，是在声明“如果t2也想进入，优先让t2来”
• 当t2设置turn =0，则是主动让步：“现在轮到t1进入了”

在你假设的场景中，t2执行turn=0后，t1的忙等条件flag[1] && turn ==1中的后半部分直接失效，t1必然退出忙等。后续t1进入临界区并设置flag[0]=false后，t2的忙等条件flag[0] && turn ==0也会失效，t2随之退出忙等。

结论 #

Peterson算法是经过严格证明的互斥算法，它保证了最多只有一个进程会进入忙等，不会出现两个进程同时挂起的情况。你的假设错误在于将忙等的单次条件判断等同于永久阻塞，忽略了循环的持续检查逻辑和turn变量的让步机制。

内容的提问来源于stack exchange，提问作者xmh0511