Bakery Algorithm

• Notation <º lexicographical order (ticket #, process id #)

1. (a,b) < c,d) if a < c or if a = c and b < d
2. max (a0,…, an-1) is a number, k, such that k ³ ai for i - 0, 

…, n – 1

• Shared data

  boolean choosing[n];

  int number[n];

    Data structures are initialized to false and 0 respectively

do {

  choosing[i] = true;

  number[i] = max(number[0], number[1], …, number [n – 1])+1;

  choosing[i] = false;

  for (j = 0; j < n; j++) {

  while (choosing[j]) ;

  while ((number[j] != 0) && (number[j,j] < number[i,i])) ;

  }

  critical section

  number[i] = 0;

  remainder section

} while (1);