1
$\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 */;           |
| }                              | }                              |
+--------------------------------+--------------------------------+
$\endgroup$

1 Answer 1

1
$\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.

$\endgroup$
6
  • $\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$
    – RajS
    Jan 29, 2020 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$
    – RajS
    Jan 29, 2020 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, 2020 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$
    – RajS
    Feb 3, 2020 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$
    – RajS
    Feb 3, 2020 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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