# Mutual exclusion for n processes

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;


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?

-
What do you expect i = turn to do? –  Raphael Jan 20 '13 at 15:41

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.

-
What is j in your code? –  Raphael Jan 21 '13 at 11:02
@Raphael .. I am referring to the code in the link given by the OP. –  AJed Jan 21 '13 at 12:58

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).

-