"You know better than to trust a strange computer!"
- C3PO, The Empire Strikes Back

Agenda

• Announcements
• Producer-Consumer
• Critical Sections

Announcements

Producer-Consumer Problem

Last time we started to look at the producer-consumer problem. Here, we consider the bounded buffer case.

Bounded Buffer, buffer size n

For simplicity, we will assume the objects being produced and consumed are int values.

This solution leaves one buffer entry empty at all times:

• Shared data

  int buffer[n];
  int in=0;
  int out=0;
  

• Producer process

  while (1) {
    ...
    produce item;
    ...
    while (((in+1)%n) == out); /* busy wait */
    buffer[in]=item;
    in=(in+1)%n;
  }
  

• Consumer process

  while (1) {
    while (in==out); /* busy wait */
    item=buffer[out];
    out=(out+1)%n;
    ...
    consume item;
    ...
  }
  

Is there any danger with this solution in terms of concurrency? Remember that these processes can be interleaved in any order - the system could preempt the producer at any time and run the consumer.. Things to be careful about are shared references to variables.

Note that only one of the processes can modify the variables in and out. Both use the values, but only the producer modifies in and only the consumer modifies out. Try to come up with a situation that causes incorrect behavior - hopefully you cannot.

Perhaps we want to use the entire buffer...let's add a variable to keep track of how many items are in the buffer, so we can tell the difference between an empty and a full buffer:

• Shared data

  int buffer[n];
  int in=0;
  int out=0;
  int counter=0;
  

• Producer process

  while (1) {
    ...
    produce item;
    ...
    while (counter==n); /* busy wait */
    buffer[in]=item;
    in=(in+1)%n;
    counter=counter+1;
  }
  

• Consumer process

  while (1) {
    while (counter==0); /* busy wait */
    item=buffer[out];
    out=(out+1)%n;
    counter=counter-1;
    ...
    consume item;
    ...
  }
  

We can now use the entire buffer. However, there is a potential danger here. We modify counter in both the producer and the consumer.

Everything looks fine, but let's think about how a computer actually executes those statements to increment or decrement counter.

counter++ really requires three machine instructions: (i) load a register with the value of counter's memory location, (ii) increment the register, and (iii) store the register value back in counter's memory location. There's no reason that the operating system can't switch the process out in the middle of this.

Consider the two statements that modify counter:

	Producer		Consumer
P1	R0 = counter;	C1	R1 = counter;
P2	R0 = R0 + 1;	C2	R1 = R1 - 1;
P3	counter = R0;	C3	counter = R1;

Consider one possible ordering: P₁ P₂ C₁ P₃ C₂ C₃ , where counter=17 before starting. Uh oh.

What we have here is a race condition. We need to make sure that when one process starts modifying counter, that it finishes before the other can try to modify it. This requires synchronization of the processes.

If there were mutliple producers or consumers, we would have the same issue with the modification of in and out.

We need to make those statements that increment and decrement counter atomic. We say that the modification of counter is a critical section.

Critical Sections

The Critical-Section problem:

  while (1) {
     <CS Entry>
     critical section
     <CS Exit>
     non-critical section
  }

Any solution to the critical section problem must satisfy three conditions:

1. Mutual exclusion: If process P_i is executing in its critical section, then no other processes can be executing in their critical sections. "One at a time."
2. Progress: If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. "no unnecessary waiting."
3. Bounded waiting: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. "no starvation." (We must assume that each process executes at non-zero speed, but make no assumptions about relative speeds of processes)

We first attempt to solve this for two processes, P₀ and P₁. They share some variables to synchronize. We fill in <CS Entry> and <CS Exit> from above with code that should satisfy the three conditions.

Critical Section Algorithm 1

• Shared data

  int turn=0;
  

• Process P_i (define j=1-i, the other process)

  while (1) {
    while (turn!=i); /* busy wait */
  
      /* critical section */
  
    turn=j;
  
      /* non-critical section */
  
  }
  

Note the semicolon at the end of the while statement's condition at the line labeled "busy wait" above. This means that P_i just keeps comparing turn to i over and over until it succeeds. This is sometimes called a spin lock. For now, this is our only method of making one process wait for something to happen. More on this later.

This does satisfy mutual exclusion, but not progress (alternation is forced).

Critical Section Algorithm 2

We'll avoid this alternation problem by having a process wait only when the other has "indicated interest" in the critical section.

• Shared data

  boolean flag[2];
  flag[0]=false;
  flag[1]=false;
  

• Process P_i

  while (1) {
    flag[i]=true;
    while (flag[j]);
  
      /* critical section */
  
    flag[i]=false;
  
      /* non-critical section */
  
  }
  

flag[i] set to true means that P_i is requsting access to the critical section.

This one also satisties mutual exclusion, but not progress.

If we swap the order of the flag[i]=true; and while (flag[j]); statements, we no longer satisfy mutual exclusion.

Critical Section Algorithm 3

We combine the two previous approaches:

• Shared data

  int turn=0;
  boolean flag[2];
  flag[0]=false;
  flag[1]=false;
  

• Process P_i

  while (1) {
    flag[i]=true;
    turn=j;
    while (flag[j] && turn==j);
  
      /* critical section */
  
    flag[i]=false;
  
      /* non-critical section */
  
  }
  

So, we first indicate interest. Then we set turn=j;, effectively saying "no, you first" to the other process. Even if both processes are interested and both get to the while loop at the "same" time, only one can proceed. Whoever set turn first gets to go first.

This one satisfies all three of our conditions. This is known as Peterson's Algorithm.

Bakery algorithm

Can we generalize this for n processes? The Bakery Algorithm (think deli/bakery "now serving customer X" systems) does this.

The idea is that each process, when it wants to enter the critical section, takes a number. Whoever has the smallest number gets to go in. This is more complex than the bakery ticket-spitters because two processes may grab the same number (to guarantee that they wouldn't would require mutual exclusion - exactly the thing we're trying to implement), and because there is no attendant to call out the next number - the processes all must come to agreement on who should proceed next into the critical section.

We break ties by allowing the process with the lower process identifier (PID) to proceed. For P_i, we call it i. This assumes PIDs from 0 to n-1 for n processes, but this can be generalized.

Although two processes that try to pick a number at about the same time may get the same number, we do guarantee that once a process with number k is in, all processes choosing numbers will get a number > k.

Notation used below: an ordered pair (number, pid) fully identifies a process' number. We define a lexicographic order of these:

The algorithm:

• Shared data, initialized to 0's and false

  boolean choosing[n];
  int number[n];
  

• Process P_i

  while (1) {
    choosing[i]=true;
    number[i]=max(number[0],number[i],...,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;
  
      /* non-critical section */
  
  }
  

So great, we have a solution. But...problems:

1. That's a lot of code. Lots of while loops and for loops. Could be expensive if we're going to do this a lot.
2. If this is a highly popular critical section, the numbers might never reset, and we could overflow our integers. Unlikely, but think what could happen if we did.
3. It's kind of inconvenient and in some circumstances, unreasonable, to have these arrays of n values. There may not always be n processes, as some may come and go.