The Bakery algorithm

The Bakery algorithm


int choosing[n], turn[n];

code for process i: 0 <= i < n:

int j;
while (1) {
choosing[i] = 1;
turn[i] = max(turn[0], turn[1], ..., turn[n-1]) + 1;
choosing[i] = 0;
for (j = 0; j < n; j++)
if (j != i) {
while (choosing[j]) ;
while (turn[j] != 0 && (turn[j], j) < (turn[i], i)) ;
}
critical section;
turn[i] = 0;
non-critical section;
}


The notation


(a, b) < (c, d)

is equivalent to


(a < c) || (a = c && b < d)