Databases
StackOverflow2013
Postsdbo
POUnable to understand correctness of Peterson Algorithm
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POUnable to understand correctness of Peterson Algorithm
    text
    copied!<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="https://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" rel="nofollow noreferrer">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>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload