Consider the following codes of two processes sharing a variable turn that is in

Question

Consider the following codes of two processes sharing a variable turn that is initialized to 1. Do the processes satisfy all requirements of critical region solution (i.e., mutual exclusion, progress & bounded waiting)? Explain. Process P0 /* other code */ while (turn i = 0) { } /* wait update (); /* critical region turn = 0; /* other code */ Process P1 /* other code */ while (turn i = 1) { } /* wait update (); /* critical region turn = 1; /* other code */ Suppose there are two processes -i and j, sharing variables turn and flag [2]. Consider the following code for process i. Process j has similar code. do { flag [i] = true; while (flag [j]) { if (turn == j) { flag [i] = false; while (turn == j); /* do nothing */ flag [i] = true; } } critical_task(); /* critical region */ turn = j; flag[i] = false; other_tasks (); /* remainder section */ } while (true); Explain whether the above solution satisfy the necessary conditions (mutual exclusion, progress & bounded waiting) of critical region problem

Explanation / Answer

2.

P0 and P1 are forced to alternate their entries into the critical section, ensuring mutual exclusion and bounded waiting. However, the progress requirement is violated.
Assume that the initial value of turn is 1:
(1) T1 exits its while-loop
(2) T1 enters and exits its critical section
(3) turn is set to 1
(4) T1 terminates in its non-critical section
context switch
(1) T0 enters its while-loop and will stuck in while loop, hence wait for long.
Thread T0 cannot exit the loop in (1) since the value of turn is 0 and turn will never be changed by T1.

3.
This algorithm satisfies the three conditions of the critical section problem.
(1)Mutual exclusion is ensured through the use of the flag and turn variables.
If both processes set their flag to true, only one will succeed, namely, the process whose turn it is. The waiting process can only enter its critical section when the other process updates the value of turn.

(2)Progress is provided, again through the flag and turn variables.
This algorithm does not provide strict alternation.
Rather, if a process wishes to access their critical section, it can set their flag variable to true and enter their critical
section. It only sets turn to the value of the other process upon exiting its critical section. If this process wishes to
enter its critical section again ­ before the other process ­ it repeats the process of entering its critical section and
setting turn to the other process upon exiting.

(3)Bounded waiting is preserved through the use of the turn variable.
Assume two processes wish to enter their respective critical sections. They both set their value of flag to true, however only the thread whose turn it is can
proceed, the other thread waits. If bounded waiting were not preserved, it would therefore be possible that the
waiting process would have to wait indefinitely while the first process repeatedly entered ­ and exited ­ its critical
section. However, Dekker’s algorithm has a process set the value of turn to the other process, thereby ensuring that
the other process will enter its critical section next.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.