无法理解彼得森算法的正确性正确性、算法、彼得森
我有一种情况，讨论这里彼得森算法：
I have a scenario to discuss here for Peterson Algorithm:
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设置标志[0] = 1而死亡。然后P1开始。其而条件将被满足作为标志[0] = 1（由P0设定并转动= 0），它会停留在这个循环永远是一种死锁。 所以呢彼得森算法没有考虑这种情况？ 在情况下，如果被认为是死亡过程中未中，而由威廉失速分析这些算法再在操作系统书，附录A中包含了一系列算法的并发性，从4算法不正确的示范。这证明了他们不正确考虑垂死的处理（除其他情况）完成前的情况下，但随后声称彼得森算法是正确的。 我碰到this线程，给我的线索，有一个问题，当考虑ñ过程（N> 2），但两个过程这个算法工作正常。 那么，有没有在算法分析的问题（我的同学的一个建议，我完全第二他），这样或彼得森算法并不声称僵局2的过程吗？
Suppose both process start executing concurrently .P0 sets flag[0]=1 and die. Then P1 starts. Its while condition will be satisfied as flag[0]=1 ( set by P0 and turn =0) and it will stuck in this loop forever which is a dead lock. So does Peterson Algorithm doesn't account for this case ? In case if dying of process in not to be considered while analyzing such algorithms then in Operating System Book by William Stalling, appendix A contain a series of algorithm for concurrency, starting with 4 incorrect algorithm for demonstration. It proves them incorrect by considering the case of dying of a process ( in addition to other cases) before completion but then claims Peterson Algorithm to be correct. I came across this thread which give me clue that there is a problem when considering N process( n>2) but for two process this algorithm works fine. So is there a problem in the analysis of the algorithm(suggested by one of my classmate and i fully second him) as discussed above or Peterson Algorithm doesn't claim deadlock with 2 process too?
在本文关于著名互斥算法，笔者总结出了一些神话的彼特森先生从来没有声称他的算法，确保有限绕行。 可以无界旁路被认为是达到无穷大的情况下死锁的？那么在这种情况下，我们可以少一些麻烦在接受了彼得森算法会导致死锁。
In this paper Some myths about famous mutual exclusion algorithms, the author concluded Peterson has never claimed that his algorithm assures bounded bypass. Can unbounded bypass be thought of as reaching infinity as in case of deadlock ? Well in that case we can have less trouble in accepting that Peterson Algorithm can lead to deadlock.
推荐答案
当然，你可以写code，将抛出一个未处理的异常，但算法设的执行过程中会始终将其标志设置为false，它的后关键部分已经执行。因此，Peterson的算法并通过3次测试的关键部分。
Certainly you could write code that would throw an unhandled exception, but the algorithm supposes that the executing process will always set its flag to false, after its critical section has executed. Therefore Peterson's algorithm does pass the 3 tests for critical sections.
1）互斥 - 标志[0]和标志[1]既可以是真实的，但反过来只能是0或1。因此，只有可以执行的两个关键部分之一。另将旋转等。
1) Mutual exclusion - flag[0] and flag[1] can both be true, but turn can only be 0 or 1. Therefore only one of the two critical sections can be executed. The other will spin wait.
2）的进展 - 如果进程0中的关键部分，然后打开= 0和国旗[0]是真实的。一旦它已经完成它的关键部分（即使有灾难性发生），则必须设置的标志[0]为false。如果流程1，通过旋等待，现在它将免费为标志[0]！=真。
2) Progress - If process 0 is in the critical section, then turn = 0 and flag[0] is true. Once it has completed it's critical section (even if something catastrophic happens), it must set flag[0] to false. If process 1 was spin waiting, it will now free as flag[0] != true.
3）绑定等待 - 如果过程1在等待，进程0只能进入它的关键部分一次，前处理1开绿灯，如＃解释2
3) Bound-waiting - If Process 1 is waiting, Process 0 can only enter it's critical section once, before process 1 is given the green light, as explained in #2.
与Peterson的算法的问题是，在现代建筑中，CPU缓存可以搞砸了互斥的要求。该问题被称为高速缓存一致性，并且可能的是在CPU的0设置标志[0]等于真使用PROCESSS 0的高速缓存中，同时在CPU 1方法1仍然认为标志[0]是假的。在这种情况下，两个临界区将进入，和BANG ...互斥失败，和比赛条件现在也是可能的。
The problem with Peterson's Algorithm is that in modern architecture, a CPU cache could screw up the mutual exclusion requirement. The problem is called cache-coherence, and it is possible that the cache used by Processs 0 on CPU 0 sets flag[0] equal to true, while Process 1 on CPU 1 still thinks flag[0] is false. In this case, both critical sections would enter, and BANG... mutual exclusion fails, and race conditions are now possible.
