Atomic exchange instruction is given as follows:
void exchange (int *a, int *b)
{
int temp;
temp = *b;
*b = *a;
*a = temp;
}
Now consider the solution to critical section problem based on above instruction:
1 int const n = /* number of processes */;
2 int lock = 0;
3 void P(int i)
4 {
5 int key = 1; //intent to obtain lock
6 while (true)
7 {
8 do exchange (&key, &lock)
9 while (key != 0); //if lock wasn’t free
10 /* critical section */;
11 lock = 0; //release lock, unblock
12 //other processes
13 /* remainder */;
14 }
15 }
16 void main()
17 {
18 lock = 0;
19 parbegin (P(1), P(2), ..., P(n));
20 }
Now I want to analyse two properties of critical section problem solution for this algorithm: bounded waiting and progress. People online define it many ways. For example: 1, 2.
One way is as explained here:
- Progress: means process will eventually do some work
- Bounded waiting: means that the process will eventually gain control of the processor
However I feel these are incorrect (Q.1 Am I wrong?) as this will imply lack of bounded waiting result in the lack of progress, essentially suggesting two requirements are one and the same (Q.2 Or is it like that only?).
Galvin et al defined these requirements more verbosely in their book:
Considering the process has following structure:
do
{
//entry section (implementing some locking mechanism)
//critical section
//exit section (implementing some unlocking mechanism)
//remainder section
}
while(true);
Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.
Bounded Waiting: There exists a bound 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.
Now with the help of these definitions I want to know whether bounded waiting and progress is ensured or not.
I feel bounded waiting is not ensured in above code as process P1 can enter its critical section any number of times before P2 can enter its critical section. This can be seen in below table:
| Step# | P1 | P2 |
|-------|---------|-------------------|
| 1 | Line 5 | |
| 2 | Line 6 | |
| 3 | Line 8 | |
| 4 | Line 9 | |
| 5 | | Line 5 |
| 6 | | Line 6 |
| 7 | | Line 8 |
| 8 | | Line 9 //spinwait |
| 9 | Line 10 | |
| 10 | Line 11 | |
| 11 | Line 13 | |
| 12 | Line 5 | |
| 13 | Line 6 | |
| 14 | Line 8 | |
| 15 | Line 9 | |
| 16 | | Line 8 |
| 17 | | Line 9 //spinwait |
However this means that P1 can execute forever without letting P2 enter its critical section at all. If we consider that the progress means "process will eventually do some work" (as stated in non-book definition above), then this will also mean that progress is also not ensured.
However I am trying to deduce if this is indeed the case with Galvin's definition also. But before that I want to interpret Galvin's definition of progress as follows:
If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section (in other words, processes executing in their entry and exit section) can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.
Now in table above, at step 10, no process is executing in its critical section. Process 1 executes line 11 lock = 0; which is essentially its exit section. Thus we can say that the decision to let process 2 enter its critical section is taken in exit section of process 1. Also in step 14, process 1 executed line 8 do exchange (&key, &lock), which is essentially entry section. Thus we can say that the decision to let process 2 not to enter its critical section is taken in entry section of process 1. (Q.3) With this interpretation, should we say that the progress is ensured?
I feel tangled with words here. Or I might be giving unnecessary importance to the concept of progress. Neverthless, I need to know whats the truth about progress requirement.
PS: The same confusion occurred to me while dealing with attempts made to produce Dekker's algorithm by Stallings in his book as I explained in comments to this answer.
