What is progress and bounded waiting in 'critical section algorithm'?

Question

Consider the following code

  //proces i:                             //proces j:

  flag[i] = true;                         flag[j] = true;
  turn = j;                               turn = i;
  while(flag[j] == true && turn==j);       while(flag[i] == true && turn == i);

  <critical section>                      <critical section>

  flag[i] = false;                        flag[j] = false;

  <remainder section                      <remainder section>

I am certain that the above code will satisfies the mutual exclusion property but what I am uncertain about the following

1. What exactly does progress mean ? and does the above code satisfy it, The above code requires the the critical section being executed in strict alternation. Is that considered as progress ?

2. From what I see the above code does not maintain any information on the number of times a process has entered the critical section, would that mean that the above code does not satisfy bounded waiting ?

Answer 1

Progress means that the process will eventually do some work - an example of where this may not be the case is when a low-priority thread might be pre-empted and rolled back by high-priority threads. Once your processes reach their critical section they won't be pre-empted, so they'll make progress.

Bounded waiting means that the process will eventually gain control of the processor - an example of where this may not be the case is when another process has a non-terminating loop in a critical section with no possibility of the thread being interrupted. Your code has bounded waiting IF the critical sections terminate AND the remainder section will not re-invoke the process's critical section (otherwise a process might keep running its critical section without the other process ever gaining control of the processor).

Answer 2

1. Progress of the processes mean that the processes don't enter in a deadlock situation and hence,their execution continues independently! Actually, at any moment of time,only one of the process i or process j will be executing its critical section code and hence,the consistency will be maintained! SO, Progress of both processes are being talked and met successfully in the given code.

2. Next, this particular code is for processes which are intended to run only for once and hence, they won't be reaching their critical section code again. It is for single execution of process.

Bounded waiting says that a bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

This particular piece of code has nothing to do with bounded waiting and is for trivial cases where processes execute for once only!