CSE 120 Winter 2002

Principles of Computer Operating Systems

The Bakery algorithm was first published in
Leslie Lamport, A New Solution of Dijkstra's Concurrent Programming Problem, Communications of the ACM 17(8):453-455 (August 1974).


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)