The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
32 views
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);
asked in Operating System by (7 points) | 32 views
0
this process suffers strict alternation

1 Answer

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:

  1. do {
  2. flag[i] = true;
  3. while (flag[j]) {
  4. if (turn == j) {
  5. flag[i] = false;
  6. while (turn == j)
  7. ; /* do nothing */
  8. flag[i] = true;
  9. }
  10. }
  11. /* critical section */
  12. turn = j;
  13. flag[i] = false;
  14. /* remainder section */
  15. } while (true);

Code for P2:

  1. do {
  2. flag[j] = true;
  3. while (flag[i]) {
  4. if (turn == i) {
  5. flag[j] = false;
  6. while (turn == i)
  7. ; /* do nothing */
  8. flag[j] = true;
  9. }
  10. }
  11. /* critical section */
  12. turn = i;
  13. flag[j] = false;
  14. /* remainder section */
  15. } 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.

answered ago by (125 points)

Related questions

+2 votes
1 answer
3
+2 votes
0 answers
5
+3 votes
1 answer
6


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,964 questions
49,519 answers
162,507 comments
65,759 users