edited by
47,120 views
112 votes
112 votes

Consider the following proposed solution for the critical section problem. There are $n$ processes : $P_0....P_{n-1}$. In the code, function $\text{pmax}$ returns an integer not smaller than any of its arguments .For all $i,t[i]$ is initialized to zero.

Code for $P_i$;

do {
    c[i]=1; t[i]= pmax (t[0],....,t[n-1])+1; c[i]=0;
    for every j != i in {0,....,n-1} {
        while (c[j]); 
        while (t[j] != 0 && t[j] <=t[i]);
    }
    Critical Section;
    t[i]=0;
    
    Remainder Section;
    
}  while (true);

Which of the following is TRUE about the above solution?

  1. At most one process can be in the critical section at any time
  2. The bounded wait condition is satisfied
  3. The progress condition is satisfied
  4. It cannot cause a deadlock
edited by

7 Answers

1 votes
1 votes

This is backery algorithm for synchronization for more than 2 processes (As Peterson's solution work for 2 processes only).

  • This algorithm works just like token system in a backery shop. All the processes needs to take their token before enter to critical section.
  • Processes are numbered 0 to N-1.
  • t[0.....N-1] is array (initialized to 0) to represent the token number. Tokens are simply the largest possible integer value available to assign to a process. Each entry corresponds to a process.
  • c[i] is the array to represent whether Process i is ready to choose its token for current round of execution.

Now, lets move to code part.

enter_CS(Pi)
{
    c[i]=1; // indicates that Process Pi is now ready to take its token;
    t[i]= pmax (t[0],....,t[n-1])+1; 
    c[i]=0;// Pi now has taken its token.
    for every j != i in {0,....,n-1} // for all the processes except Pi
    {
        while (c[j]); //here it waits for c[j] to be false which indicates that 
                    // process j has taken its token otherwise wait here.
        while (t[j] != 0 && t[j] <=t[i]);// t[j]!=0 indicates that jth process has
                         // not taken its token now so don't compare it.
         //   t[j] <= t[i]  indicates that if the coming process Pi's token
         // number is greater than any of the processes then it has to wait in while loop
    }
}
// That means the process with least non-zero token number will be able to enter the CS.
// Critical section
exit_CS(Pi)
{
    t[i]=0; // make its token zero so that other processes could enter now. 
}

So, this way only one process can be into its critical section. (i.e the process with least token number will be able to enter CS.)

Progress is not satisfied since the processes which have taken the token and after taking token get preempted. So it will block all other processes that come after it to take token.

Galvin says: There should be bound on number of times other processes are allowed to enter the critical section when a process has already made a request.

But here there is no bound on the number of time a process can ask for token after it has executed its CS. So, no bounded waiting.

Also, Bounded Waiting is not satisfied as deadlock can occur.

Correct Ans: (A)

edited by
0 votes
0 votes
First of all eveyone muat know this is lamports bakery algo. Google it and read it. It satisfy all the 4 conditions like peterson solution.
mutual exclusion,bonded waiting,progress,portablity
The difference between both is that peterson works for 2 process.lamorts bakery algo works for n processes. So how people are saying it doesnt provide bonded waiting
–2 votes
–2 votes
do {
   1. c[i]=1;
2. t[i]= pmax (t[0],....,t[n-1])+1;
3.c[i]=0;
4.    for every j != i in {0,....,n-1} {
        5.while (c[j]);
       6. while (t[j] != 0 && t[j] <=t[i]);
    }
   7. Critical Section;
   8. t[i]=0;
    
   9 Remainder Section;
    
}  while (true);

i would like to attempt this question :
Line no 1 - > indiacte that process i would like to enter ito into critical section . it shows its intention by setting value of i is equal to 1
 line no 2 : t[i]= return the maximum positive integer not less that any of it argument implies : the process would get its turn no . now let see what i mean
suppose at current instant p[1]=2 and p[2]=3 then another process say now p4 would get it turn as max (p[i])+1 here it will be 3+1 = 4
But apart from turn , it would be more approiate to say that the it record the number of times process want to enter into CS
the reason for this why i thought is
Line no 3 :
c[i]=0 : Again reseeting the value of i =0 ( will explain about this statement in the next some lines )
consder  a scenario where process p1 , p2 , p3 want to enter into CS
p[1] makes C[1]=1 (assumin p2 and p3 are not in picture now )
t[1]= 1 (sinc currenlt all are 0 so max (0)+1= 1 )
ad then p3 which will get t2;
p[1]=0 ; And suppose if now process p1 premept from here and go back to section where line 1 is present
noe this time p1 and p2enter simultaeously then  both process make there c[1]=1 and c[2]=1 (p3 is not presnet here )
since there is no lock on the line 2
both would end up as t[1]=3 and t[2]=3 (neglecting  relative speed of process )
so we basically got 2 process whose t[i] is same .
Line n0 4-6 : implies that if any  process i who want to enter into critical section , we must check for all the process j , if the t[j] of any process is found to be less than t[i] then then process p[i] would wait .
beacuse the one who comes early will enter into CS first . but this assumption is wrong with statement C[i]=0
continuing the above scenraio
where p[1]=2 =p[2] then in such a case no one would enter into CS , if anyother process say p3 comes whose  value  t[i] is less than other two  then  it will enter into Cs but still problem between p1 and p2 remain same so deadlock problem continues--- so this how option d is eleminated . And even from this sceanario i can say that process p3 ( only 1 process can be in CS ) ..option a may be answer ( let us prove other option too )
Now let us see Bounded waiting  :

"There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. In other words, no process should have to wait forever to enter its critical region."
--- i think this statement is wrong what if a process p1 prempt evertime from c[i]=0 , then go back to line 1 . Inpsite of another process making  a request to enter into Cs it is (p1 ) again making infinite number of attempts again and again to enter into Cs so Bw not satisfied

Now let us see Progress :
i dont agree with progress explantion . A progress basically mean if process doenst want to enter into CS then it shouldnt disallow any other process to enter into Cs . SO if any other process say P5 doesnt want to enter into so c[i]=0 so no other issue would arrise

so  i think progress is  satisfied too  a and c both .according to me .
Answer:

Related questions