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

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个不正确的算法开始演示.通过在完成之前考虑过程死亡(除了其他情况)但是然后声称Peterson算法是正确的,它证明它们是不正确的.我遇到了这个线程,它让我知道在考虑N进程(n> 2)时存在问题但是对于两个进程这个算法工作正常.
因此,如上所述,算法分析存在问题(由我的一个同学建议,我完全是他的第二个),或者Peterson算法也没有声称有2个进程的死锁？

---

在本文中,有关着名互斥算法的一些神话,作者得出结论, 彼得森从未声称他的算法可以确保有限的旁路.
无限绕行可以被认为是无限的,就像死锁一样？那么在这种情况下,我们可以减少接受Peterson算法可能导致死锁的麻烦.

Answer 1

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

1)相互排斥 - flag [0]和flag [1]都可以为true,但turn只能是0或1.因此,只能执行两个关键部分中的一个.另一个会旋转等待.

2)进度 - 如果进程0在临界区,则转= 0并且标志[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 ......相互排斥失败,现在可以进行竞争条件.

Answer 2

大多数锁定算法不会考虑进程在关键部分内死亡的情况（其他进程如何区分在获取锁定后死亡的进程与仅花费很长时间的进程？）。

然而，当进程不在关键部分时终止，不应阻止其他进程进入或离开。比如一个临界区，两个进程“轮流”进入临界区就是有问题的；如果一个进程在临界区外死亡，第二个进程将永远等待第一个进程结束。这也许就是你老师所指的。

（作为一种 hacky 解决方案，您可以尝试处理在超时的关键部分内死亡的进程；如果一个进程花费很长时间，您就认为它已经死亡。如果一个进程花费太长时间，则存在允许两个进程进入关键部分的风险。不过很长。）