Dark Mode

Chetan Warke
asked
in Operating System
Nov 17, 2018

2,050 views
0 votes

The first known correct software solution to the critical-section problem

for two processes was developed by Dekker. The two processes, P0 and

P1, share the following variables:

boolean flag[2]; /* initially false */

int turn;

The structure of process Pi (i == 0 or 1) is shown in Figure 5.21. The

other process is Pj (j == 1 or 0). Prove that the algorithm satisfies all

three requirements for the critical-section problem. How it can satisfy bounded waiting condition?

do {

flag[i] = true;

while (flag[j]) {

if (turn == j) {

flag[i] = false;

while (turn == j)

; /* do nothing */

flag[i] = true;

}

}

/* critical section */

turn = j;

flag[i] = false;

/* remainder section */

} while (true);

for two processes was developed by Dekker. The two processes, P0 and

P1, share the following variables:

boolean flag[2]; /* initially false */

int turn;

The structure of process Pi (i == 0 or 1) is shown in Figure 5.21. The

other process is Pj (j == 1 or 0). Prove that the algorithm satisfies all

three requirements for the critical-section problem. How it can satisfy bounded waiting condition?

do {

flag[i] = true;

while (flag[j]) {

if (turn == j) {

flag[i] = false;

while (turn == j)

; /* do nothing */

flag[i] = true;

}

}

/* critical section */

turn = j;

flag[i] = false;

/* remainder section */

} while (true);

0 votes

P1, P2 share these variable (took process names as (P1 and P2) rather than (P0 and P1))

boolean flag[2]; /* initially false */

int turn;

Code for P1:

- do {
- flag[i] = true;
- while (flag[j]) {
- if (turn == j) {
- flag[i] = false;
- while (turn == j)
- ; /* do nothing */
- flag[i] = true;
- }
- }
- /* critical section */
- turn = j;
- flag[i] = false;
- /* remainder section */
- } while (true);

Code for P2:

- do {
- flag[j] = true;
- while (flag[i]) {
- if (turn == i) {
- flag[j] = false;
- while (turn == i)
- ; /* do nothing */
- flag[j] = true;
- }
- }
- /* critical section */
turn = i;- flag[j] = false;
- /* remainder section */
- } while (true);

I believe you don't have any doubt in Mx and Progress. Say P1 got CS first (when P2 is also waiting for the CS-entry), while leaving P1 will make the turn to P2, see line 12 (I have turned it Bold.) If P1 wants to re-enter the CS, It will enter Loop (at line 3, will be struck at loop 2 at line 6) after spinning for a while, due to scheduling algorithm it has to be preempted out and P2 has to be given the Processor, P2 breaks Loop (as it has (turn==i) in line 6 of its respective code) whereby entering the CS. So none of the 2 processes is INFINITELY starving for the processor. Hence Bounded wait handled.