Unable to understand correctness of Peterson Algorithm <p>I have a scenario to discuss here for Peterson Algorithm:</p> <pre><code>flag[0] = 0; flag[1] = 0; turn; P0: flag[0] = 1; turn = 1; while (flag[1] == 1 &amp;&amp; turn == 1) { // busy wait } // critical section ... // end of critical section flag[0] = 0; P1: flag[1] = 1; turn = 0; while (flag[0] == 1 &amp;&amp; turn == 0) { // busy wait } // critical section ... // end of critical section flag[1] = 0; </code></pre> <p>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.<br> So does Peterson Algorithm doesn't account for this case ?<br> 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 <a href="http://stackoverflow.com/questions/4033738/does-petersons-algorithm-satisfy-starvation">this</a> thread which give me clue that there is a problem when considering N process( n>2) but for two process this algorithm works fine.<br> 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?</p> <hr> <p>In this paper <a href="http://portal.acm.org/citation.cfm?id=945527">Some myths about famous mutual exclusion algorithms</a>, the author concluded <strong>Peterson has never claimed that his algorithm assures bounded bypass.</strong><br> 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.</p>