CSC 325 Operating Systems with an Emphasis on UNIX
Teamwork 5

Organize yourselves into groups of two or three students. Discuss the following problems in your group. Elect one person to be group scribe to type up your team's answers.

The Bakery Algorithm
This is a generalization to n processes of the critical section problem for two processes that you read about in your text. To draw a parallel with sales at a real bakery, processes are called "customers," and the critical sections of code are called the "shop". On entering the "shop" a "customer" gets a number, and the "customer" with the lowest number is served next. Unfortunately, in the operating system bakery world, we cannot guarantee that each "customer" gets a different number, so in the case of a tie, the "customer" with the lowest alphabetical name is served first. In this solution cooperating processes share the following common data structures:
  const int n = …some fixed value;
  bool choosing[n-1] = false; //Boolean array
  int number[n-1]; //integer array with each element initialized to 0.

Pseudo-code Solution to the Bakery Algorithm for Process i:
do
{
  choosing[i] = true;
  number[i] = max(number[0], number[1], number[2],…number[n-1])+ 1;
  choosing[i] = false;
  for (int j = 0; j<=n-1; j++)
  {
    while (choosing[j]);
    //do no-op
    while((number[j]!=0)&&((number[j]<number[i]||(number[j]==number[i])&&j<i));
    //do no-op
  }
  /* critical section */
  number[i] = 0;
  /* remainder section */
}
while(true);

1. Explain the main purpose of the choosing array and the main purpose of the number array. In other words, what actual role in the Bakery Algorithm solution do the values in each of these arrays play?
   
2. Show that in the Bakery Algorithm if Process n is in its critical section and Process k ( k != n) has already chosen it's number[k] != 0, then number[n] < number[k] or (number[n] = number[k] and n < k).
   
3. Write a convincing argument that the Bakery Algorithm satisfies the Mutual Exclusion criteria.
   
4. Write a convincing argument that the Bakery Algorithm satisfies the Progress criteria.
   
5. Write a convincing argument that the Bakery Algorithm satisfies the Bounded Waiting criteria.
   

Save your text file as yourlastnameT5.txt.