Question

Provide relevant parts of C-like codes for N processes (N is an arbitrary integer larger tha in N process N way synchronization,i.e. each process has a synehronization point in its eode, and any f processes has to wait for other N-1 processes to cross or reach their synchronization points, and only then that process nay cross its synchronization point. One solution, that follows ideas from the similar problems we discussed in the class, would be to use N semaphores all initialized to O. But for this problem, your solution may use only 2 semaphores. Hint: All processes but one would have the same code for this synchronization

Answer 1

Answer:

wait(s){

   while(s<0);   // Busy waiting

   s--;

}

siganl(s){

   s++;

}

Here I am merging the solutions of Lamport's Bakery Algorithm and Semaphore concept to achive synchronization which n-1 bounded waiting.

Actually The bakers algorithm is this :

repeat

   choosing[i] := true;

   number[i] := max(number[0], number[1], ..., number[n - 1])+1;

   choosing[i] := false;

   for j := 0 to n - 1

       do begin

           while choosing[j] do no-op;

           while number[j] != 0

               and (number[j], j) < (number[i], i) do no-op;

       end;

       critical section

   

   number[i] := 0;

   

       remainder section

until false;

Now I am modifying the above bakery algorithm to achive synchronization with semaphore.

repeat

   choosing[i] := true;

   number[i] := max(number[0], number[1], ..., number[n - 1])+1;

 //choosing[i] := false;

  wait(s);

   for j := 0 to n - 1

       do begin

           //while choosing[j] do no-op;

           while number[j] != 0

               and (number[j], j) < (number[i], i) do no-op;

       end;

       critical section

   signal(s);

   number[i] := 0;

   

       remainder section

until false;

observe the Bold statements to get the difference between above and below code and you will definitely achieve synchronization with mutual exclusion and bounded waiting with n-1

Explanation: