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:
- 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 settingflag[1]
tofalse
, which is in remainder section. So this attempt does not seem to ensure progress. - 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.
- 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 */; |
| } | } |
+--------------------------------+--------------------------------+