Two Process Solution Algorithm 1

Question

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?

Answer 1

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.

Answer 2

You can not be sure about the order in which the code in the two processes is run. When first P1 is run and tries to enter the critical section, it is not allowed to, because it is the turn of P0. So, P1 can not enter the critical section even if there is no other process in it. Therefore progress is not fulfilled.

Answer 3

The problem here is that this totally depends on the lower level process scheduling. OS usually takes a bit to wake up a sleeping process, and this is done at a point when the process currently running on the CPU voluntarily gives up control by executing some blocking system call, or out of timer interrupt when time quanta expires. On a full SMP system this also takes some non-trivial in-kernel synchronization and signaling.

This means that process 0 can just loop leaving and entering critical section again without process 1 ever having a chance to run.

Also, I hope you are nor relying on bare integer variables for mutual exclusion. These might be cached in a register by a compiler, and if not, processor caches come into play. This is supposed to be done with special CPU instructions like test-and-set.