0
$\begingroup$

I was reading concurrency control section from Operating Systems book by William Stallings. In this book, he gives three attempts by Dekker to give solution to critical section problem:

Attempt 1

+------------------------+------------------------+
| //process 0            | //process 1            |
| while (flag[1]);       | while (flag[0]);       |
| flag[0] = true;        | flag[1] = true;        |
| /* critical section*/; | /* critical section*/; |
| flag[0] = false;.      | flag[1] = false;.      |
+------------------------+------------------------+

Attempt 2

+------------------------+------------------------+
| //process 0            | //process 1            |
| flag[0] = true;        | flag[1] = true;        |
| while (flag[1]);       | while (flag[0]);       |
| /* critical section*/; | /* critical section*/; |
| flag[0] = false;       | flag[1] = false;       |
+------------------------+------------------------+

Attempt 3

+-----------------------+-----------------------+
| //process 0           | //process 1           |
| flag[0] = true;       | flag[1] = true;       |
| while (flag[1])       | while (flag[0])       |
| {                     | {                     |
|    flag[0] = false;   |    flag[1] = false;   |
|    /* delay */        |    /* delay */        |
|    flag[0] = true;    |    flag[1] = true;    |
| }                     | }                     |
| /* critical section*/ | /* critical section*/ |
| flag[0] = false;      | flag[1] = false;      |
+-----------------------+-----------------------+

Which of the above attempts ensure progress requirement of solution to critical section?

Progress requirement is stated as follows in the book by Galvin et al:

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 sections can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.

This is what I feel:

  1. Remainder section is code executing after critical section. In attempt 1, if process 0 is busy waiting in while(), then it will be unblocked by process 1 by setting flag[1] to false, which is in remainder section. So this attempt does not seem to ensure progress.
  2. This attempt can cause deadlock. So, it may indefinitely postpone decision to let process enter its critical section. Hence, it does not ensure progress requirement.
  3. This attempt can cause livelock. So, like attempt 2, it may indefinitely postpone decision to let process enter its critical section and hence, it does not ensure progress requirement.

Am I correct with these points?

Edit - Adding some attempts by Dekker given in the book

Need confirmation for these too. I feel none of them ensure progress as above three attempts.

Attempt 0

+------------------------+------------------------+
| //process 0            | //process 1            |
| while (turn != 0);     | while (turn != 1);     |
| /* critical section*/; | /* critical section*/; |
| turn = 1;              | turn = 0;              |
+------------------------+------------------------+

Attempt 4 - Final attempt

+--------------------------------+--------------------------------+
| //process 0                    | //process 1                    |
| while (true) {                 | while (true) {                 |
|     flag [0] = true;           |     flag [1] = true;           |
|     while (flag [1]) {         |     while (flag [0]) {         |
|         if (turn == 1) {       |         if (turn == 0) {       |
|             flag [0] = false;  |             flag [1] = false;  |
|             while (turn == 1); |             while (turn == 1); |
|             flag [0] = true;   |             flag [1] = true;   |
|         }                      |         }                      |
|     }                          |     }                          |
|     /* critical section */;    |     /* critical section */;    |
|     turn = 1;                  |     turn = 0;                  |
|     flag [0] = false;          |     flag [1] = false;          |
|     /* remainder */;           |     /* remainder */;           |
| }                              | }                              |
+--------------------------------+--------------------------------+
| cite | improve this question | | | | |
$\endgroup$
0
$\begingroup$

The overall structure of the processes is modelled to be like:

while(TRUE) {
   /** get exclusive access */
   /* critical section is here */
   /** release exclusive access */
   /* remainder, i.e., non-critical section */
}

You are right, the remainder is outside of the critical section. A real process alternates between critical section/remainder.

None of the alternatives ensures some process will eventually enter the critical section, the other one might loop around and attempt entering again while this one is waiting.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ one more subtle doubt is why definition of progress requires "processes that are not executing in their remainder sections can only participate in the decision on which will enter its critical section next" Whats wrong with being executing in remainder section and doing the decision, it will still let some process enter critical section and make the overall system proceed to completion. $\endgroup$ – anir Jan 29 at 6:11
  • $\begingroup$ (continued from previous comment) I have also added two more attempts by Dekker given in the book. I believe they too dont ensure progress. If that is the case, I am guessing are they even valid solutions to critical section problem, especially attempt 5, which is given to be the final attempt. $\endgroup$ – anir Jan 29 at 6:42
  • $\begingroup$ @anir, "remainder" is just code outside the critial section (and whatever hoops it has to jump through to get exclusive access /rescind it) $\endgroup$ – vonbrand Jan 29 at 17:46
  • $\begingroup$ I came to know that only attempt 1 and 4 ensure progress. This explains why attempt 0 does not ensure progress. Attempt 2 and 3 does not ensure progress due to deadlock and livelock.[continued to next comment] $\endgroup$ – anir Feb 3 at 11:26
  • $\begingroup$ [continued from previous comment] Process 1 and 4 ensure progress since they take decision whether to allow other process to enter CS in exit section. Section after CS which sets/resets turn and flag variables is exit section not remainder section. I was making mistake in interpreting it as remainder section and concluding process 1 and 4 also does not ensure progress. Now my doubt is whether they ensure bounded waiting. I think only attempts with turn variable (with or without flag variable) ensure bounded waiting, Thus, attempt 0 and 4 ensure bounded waiting, others wont. Am I correct? $\endgroup$ – anir Feb 3 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.