Sunday 11 March 2012

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

No comments:

Post a Comment