algorithm - 无法理解彼得森算法的正确性

Question

我有一个场景要在这里讨论 Peterson 算法:

flag[0]   = 0;
flag[1]   = 0;
turn;

P0: flag[0] = 1;                                       
    turn = 1;                                               
    while (flag[1] == 1 && turn == 1)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[0] = 0;   

P1: flag[1] = 1;                                       
    turn = 0;                                               
    while (flag[0] == 1 && turn == 0)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[1] = 0;

假设两个进程同时开始执行。P0 设置 flag[0]=1 并结束。然后P1开始。它的 while 条件将被满足为 flag[0]=1(由 P0 设置并且 turn =0)并且它将永远卡在这个循环中，这是一个死锁。
那么彼得森算法是否没有考虑到这种情况？
如果在分析此类算法时不考虑死于进程，则在 William Stalling 的操作系统书籍中，附录 A 包含一系列并发算法，从 4 个不正确的算法开始进行演示。它通过考虑进程在完成之前死亡的情况(以及其他情况)来证明它们是不正确的，但随后声称彼得森算法是正确的。我遇到了this线程给我线索，在考虑 N 个进程(n>2)时存在问题，但对于两个进程，该算法工作正常。
那么在算法分析中是否存在问题(由我的一位同学建议，我完全支持他)如上所述，或者 Peterson 算法也没有声称 2 个进程出现死锁？

---

本文Some myths about famous mutual exclusion algorithms ，作者得出结论，Peterson 从未声称他的算法可确保有界旁路。
无界绕过是否可以被认为是在死锁的情况下达到无穷大？那么在那种情况下，我们可以更容易地接受 Peterson 算法会导致死锁这一事实。

Answer 1

当然，您可以编写会抛出未处理异常的代码，但算法假定执行进程在其临界区执行后始终将其标志设置为 false。因此，Peterson 的算法确实通过了关键部分的 3 个测试。

1) 互斥——flag[0] 和 flag[1] 都可以为真，而 turn 只能为 0 或 1。因此只能执行两个临界区中的一个。另一个将旋转等待。

2) Progress - 如果进程 0 在临界区，则 turn = 0 且 flag[0] 为真。一旦它完成了它的关键部分(即使发生了灾难性的事情)，它必须将 flag[0] 设置为 false。如果进程 1 正在自旋等待，它现在将释放为 flag[0] != true。

3) 边界等待 - 如果进程 1 正在等待，则进程 0 只能在进程 1 获得绿灯之前进入其临界区一次，如 #2 中所述。

Peterson 算法的问题在于，在现代架构中，CPU 缓存可能会搞砸互斥要求。这个问题被称为缓存一致性，有可能CPU 0 上的进程0 使用的缓存将flag[0] 设置为true，而CPU 1 上的进程1 仍然认为flag[0] 为false。在这种情况下，两个关键部分都会进入，然后 BANG...互斥失败，现在可能出现竞争条件。