Mutual exclusion for n processes

Question

I want to implement mutual exclusion for $n$ processes. Critical section code:

int turn = 0;        /* shared control variable */

Pi:                  /* i is 0 or 1 */
while (turn != i)
   ;                 /* busy wait */
CSi;
turn = 1 - i;

This solution from this page but it is only made for two processes.

I tried to adapt it for $n$ processes like this:

turn = 0 // shared control variable 

i = turn;

while (turn != i);

// CS

turn = (turn + 1) % n;

Does this work?

Answer 1

From my understanding of the 2-processor, if you want to do the same thing you would delete the statement (I truly dont know why you had it. There could be something interesting behind this statement of yours).

 i = turn 

and instead, let each of the $n$ processors have an id from $\{1, \dots, n\}$. Then, you would let the processors go in sequence to the critical code. That is, assume a processor $i$ takes the token and left it. Then, it has to wait the other $n- 1$ to take the token if it want to take it again. The problem in this solution is the sequential method of taking the token.

If you want to have something more efficient, then have a look at the Lamport's bakery algorithm. The pseudocode of the algorithm is available in the site you provided, and it is explained in wikipedia. The idea of this algorithm is very simple in fact. There is a queue of processors that want to get the token. These processors enter the queue, and the first come is first served.

In regard to the link you included in your question, this is done by these lines:

number[i] = max(number) + 1;   // enter the queue ! 
...
... 
while (number[j] != 0 && (number[j] < number[i] || 
                         number[j] == number[i] && j < i) )  
// wait until your turn comes. 
...
Do your critical section ! ... 
... 
 number[i] = 0;     // go out of the queue .. 

Obviously, you can play around with this. But it is a neat way of implementing FIFO requests.

Answer 2

Take a look at Allen B. Downey's "The Little Book of Semaphores, it discusses synchronization in great depth. In any case, schemes based on just the atomicity of writing to memory are unwieldly and of no practical use (real CPUs have special instructions that simplify implementing this stuff enormously).