I've been searching information on Peterson's algorithm but have come across references stating it does not satisfy starvation but only deadlock. Is this true? and if so can someone elaborate on why it does not?
Peterson's 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;
The algorithm uses two variables, flag and turn. A flag value of 1 indicates that the process wants to enter the critical section. The variable turn holds the ID of the process whose turn it is. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by setting turn to 0.
Peterson's algorithm is starvation free and fair. If a thread is in the critical section and the other one is waiting in the waiting loop - the one waiting will get into the CS next, even if the thread that was in the CS is much faster.
Disadvantages of Peterson's SolutionThe process may spend a long time waiting for the other processes to come out of the critical region. It is termed as Busy waiting. This algorithm may not work on systems having multiple CPUs. The Peterson solution is restricted to only two processes at a time.
By using 'turn' variable bounded waiting is ensured. What amongst mutual exclusion, bounded waiting and progress would fail if we have turn = i in the entry section of process Pi and the same for process Pj i.e turn = j in it's entry section.
Peterson Solution MCQ Question 1 Detailed SolutionMutual exclusion and progress are guaranteed. It doesn't use semaphore variable, but it uses to integer variables (turn and interest) to achieve synchronization.
As Ben Jackson suspects, the problem is with a generalized algorithm. The standard 2-process Peterson's algorithm satisfies the no-starvation property.
Apparently, Peterson's original paper actually had an algorithm for N
processors. Here is a sketch that I just wrote up, in a C++-like language, that is supposedly this algorithm:
// Shared resources
int pos[N], step[N];
// Individual process code
void process(int i) {
int j;
for( j = 0; j < N-1; j++ ) {
pos[i] = j;
step[j] = i;
while( step[j] == i and some_pos_is_big(i, j) )
; // busy wait
}
// insert critical section here!
pos[i] = 0;
}
bool some_pos_is_big(int i, int j) {
int k;
for( k = 0; k < N-1; k++ )
if( k != i and pos[k] >= j )
return true;
}
return false;
}
Here's a deadlock scenario with N = 3
:
pos[0] = 0
and step[0] = 0
and then waits.pos[2] = 0
and step[0] = 2
and then waits.pos[1] = 0
and step[0] = 1
and then waits.step[0]
and so sets j = 1
, pos[2] = 1
, and step[1] = 2
.pos[2]
is big.j = 2
. It this escapes the for loop and enters the critical section. After completion, it sets pos[2] = 0
but immediately starts competing for the critical section again, thus setting step[0] = 2
and waiting.step[0]
and proceeds as process 2 before.References. All details obtained from the paper "Some myths about famous mutual exclusion algorithms" by Alagarsamy. Apparently Block and Woo proposed a modified algorithm in "A more efficient generalization of Peterson's mutual exclusion algorithm" that does satisfy no-starvation, which Alagarsamy later improved in "A mutual exclusion algorithm with optimally bounded bypasses" (by obtaining the optimal starvation bound N-1
).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With