Peterson算法下两个进程可以同时进入忙等待吗？

Question

通过查看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();
}

在这个程序中，如果执行顺序是：

flag[0] = true
turn = 1
flag[1] = true
while(flag[1] && turn == 1){} // true
turn = 0
while(flag[0] && turn == 0){} //true

单笔总订单为

flag_set_0 < turn_set_0 < flag_set_1 < flag_read_0 < turn_read_0 < turn_set_1 < flag_read_1 < turn_read_1

,

这是一个没有矛盾的有效单全序，因为它遵守

t1

和

t2

要求的约束：

t1: flag_set_0 < turn_set_0 < flag_read_0 < turn_read_0
t2: flag_set_1 < turn_set_1 < flag_read_1 < turn_read_1

这意味着程序可以有两个线程同时进入忙等待循环和两个无限循环使程序未终止，我的理解对吗？

Answer 1

是的，他们都可以进入。 但其中一个人在

turn

不同时进入，在最后一家商店之前。 在下一次迭代中，其循环条件将为假。 这不是僵局。

自旋循环每次迭代都会检查

flag[other_thread]

和

turn

，而

turn

的条件相反，这对于两个循环来说不可能无限期地成立。

是的，我明白你的意思，唯一的可能性是实现不遵守[atomics.order] p11（应该在合理的时间内），这样它总是看到转符合条件，即使另一个线程有改变了它。但这不是算法的错，而是实现的错，对吧？在这种情况下，条件中的所有操作都将先于单个总顺序中的回合变化

S

，对吗？

这些是

seq_cst

操作，所以我不确定在两个循环都进入其自旋循环后是否可以延迟可见性。这涉及到他们在写完之后都轮流阅读。

也许这只是一个实现细节，真正的硬件必须等待

seq_cst

存储变得全局可见，然后

seq_cst

加载才能重新加载它（或者实际上所有以前的 seq_cst 存储变得可见）。 但如果不是，那么当第二个线程进入其自旋循环时，最后一个

turn=

分配已经对另一个线程可见。在这种情况下，如果两个线程在多次迭代中读取相反的

seq_cst

值，则可能不会违反

turn

要求；如果是这样，那么只有“应该”可见性及时性要求才能防止僵局。

---

如果你认为一个几十年来众所周知的算法被破坏了，那么你很可能犯了一个错误，应该继续寻找它没有被破坏的原因。 （或者，如果您需要寻求帮助来理解它，至少在假设该算法是正确的情况下表述您的问题。例如，“彼得森算法如何避免两个线程进入自旋循环时出现死锁？”这样表述可能会提示你再看看循环条件，或者不。）