Search code examples
algorithmoperating-systemprogressmutual-exclusion

Two Process Solution Algorithm 1

Here is the two process solution algorithm 1:

turn = 0;
i = 0, j = 1;
do
{
    while (turn != i) ; //if not i's turn , wait indefinitely 
    // critical section

    turn = j; //after i leaves critical section, lets j in

    //remainder section
} while (1); //loop again

I understand that the mutual exclusion is satisfied. Because when P0 is in critical section, P1 waits until it leaves critical section. And after P0 updates turn, P1 enters critical section. I don't understand why progress is not satisfied in this algorithm.

Progress is if there is no process in critical section waiting process should be able to enter into critical section without waiting.

P0 updates turn after leaving critical section so P1 who waits in while loop should be able to enter to critical section. Can you please tell me why there is no progress then?

Solution

  • Forward progress is defined as follows:

    If no process is executing in its CS and there exist some processes that wish to enter their CS, then the selection of the process that will enter the CS next cannot be postponed indefinitely.

    The code you wrote above does not satisfy this in the case the threads are not balanced, consider the following scenario:

    1. P0 has entered the critical section, finished it, and set the turn to P1.
    2. P1 enters the section, completes it, sets the turn back to P0.
    3. P1 quickly completes the remainder section, and wishes to enter the critical section again. However, P0 still holds the turn.
    4. P0 gets stalled somewhere in its remainder section indefinitely. P1 is starved.

    In other words, this algorithm can't support a system where one of the processes runs much faster. It forces the critical section to be owned in equal turns by P0 -> P1 -> P0 -> P1 -> ... For forward progress we would like to allow a scenario where it's owned for example in the following manner P0 -> P1 -> P1 -> .., and continuing with P1 while P0 isn't ready for entering again. Otherwise P1 may be starved.

    Petersons' algorithm fixes this by adding flags to indicate when a thread is ready to enter the critical section, on top of the turn-based fairness like you have. This guarantees that no one is stalled by the other thread inefficiency, and that no one can enter multiple times in a row unless the other permits it to.