Cooperating Processes

An Independent process is not affected by other running processes.

Cooperating processes may affect each other, hopefully in some controlled way.

Why cooperating processes?

It's hard to find a computer system where processes do not cooperate. Consider the commands you type at the Unix command line. Your shell process and the process that executes your command must cooperate. If you use a pipe to hook up two commands, you have even more process cooperation.

For the processes to cooperate, they must have a way to communicate with each other. Two common methods:

For now, we will consider shared-memory communication. We saw that threads, for example, share their global context, so that is one way to get two processes (threads) to share a variable.

Producer-Consumer Problem

The classic example for studying cooperating processes is the Producer-Consumer problem.

One or more produces processes is "producing" data. This data is stored in a buffer to be "consumed" by one or more consumer processes.

The buffer may be:

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.

Synchronization hardware

Hardware support can make some of this a little easier. Problems can arise when a process is preempted within a single high-level language line. But we can't preempt in the middle of a machine instruction.

If we have a single machine instruction that checks the value of a variable and sets it, atomically, we can use that to our advantage.

This is often called a Test-and-Set or Test and Set Lock instruction, and does this, atomically:

boolean TestAndSet(boolean *target) {
   boolean orig_val = *target;
   *target = TRUE;
   return orig_val;
}

So it sets the variable passed in to true, and tells us if it was true or false before we called it. So if two processes do this operation, both will set the value of target to true, but only one will get a return value of false.

Armed with this atomic test-and-set, we can make a simple mutual exclution solution for any number of processes, with just a single shared variable:

• Shared data

  boolean lock = false;
  

• Process P_i

  while (1) {
    while (TestAndSet(&lock));  /* busy wait */
  
      /* critical section */
  
    lock = false;
  
      /* non-critical section */
  }
  

This satisfies mutual exclusion and progress, but not bounded waiting (a process can leave the CS and come back around and grab the lock again before others who may be waiting ever get a chance to look).

A solution that does satisfy bounded waiting is still fairly complicated:

• Shared data

  boolean lock=false;
  boolean waiting[n];  /* all initialized to false */
  

• Process P_i and its local data

  int j;
  boolean key;
  
  while (1) {
    waiting[i]=true;
    key=true;
    while (waiting[i] && key)
      key = TestAndSet(&lock);
    waiting[i]=false;
  
      /* critical section */
  
    j=(i+1)%n;
    while ((j!=i) && !waiting[j])
      j=(j+1)%n;
    if (j==i) lock=false;
    else waiting[j]=false;
  
      /* non-critical section */
  
  }
  

Another hardware instruction that might be available is the atomic swap operation:

void swap(boolean *a, boolean *b) {
  boolean temp = *a;
  *a = *b;
  *b = temp;
}

An algorithm to use this, minus the bounded wait again, is straightforward:

• Shared data

  boolean lock = false;
  

• Process P_i

  boolean key = true;
  while (1) {
    while (key == true) swap(&key,&lock);  /* busy wait */
  
      /* critical section */
  
    lock = false;
  
      /* non-critical section */
  }
  

It's pretty similar to what we saw before with TestAndSet().

Semaphores

All that busy waiting in all of our algorithms for mutual exclusion is pretty annoying. It's just wasted time on the CPU. If we have just one CPU, it doesn't make sense for that process to take up its whole quantum spinning away waiting for a shared variable to change that can't change until the current process relinquishes the CPU!

This inspired the development of the semaphore. The name comes from old-style railroad traffic control signals, where mechanical arms swing down to block a train from a section of track that another train is currently using. When the track was free, the arm would swing up, and the waiting train could now proceed.

A semaphore S is basically an integer variable, with two atomic operations:

wait(S):
  while (S <= 0);  /* wait */
  S--;

signal(S):
  S++;

wait and signal are also often called down and up (from the railroad semaphore analogy) and occasionally are called P and V (because Dijkstra, who invented them, was Dutch, and these were the first letters of the Dutch words).

Important!!! Processes using a semaphore are not allowed to set or examine its value. They can use the semaphore only through the wait and signal operations.

Note, however, that we don't want to do a busy-wait. A process that has to wait should be put to sleep, and should wake up only when a corresponding signal occurs, as that is the only time the process has any chance to proceed.

Semaphores are built using hardware support, or using software techniques such as the ones we discussed for critical section management.

Since the best approach is just to take the process out of the ready queue, some operating systems provide semaphores through system calls.

Given semaphores, we can create a much simpler solution to the critical section problem for n processes:

• Shared data

  semaphore mutex=1;
  

• Process P_i

  while (1) {
    wait(mutex);
  
      /* critical section */
  
    signal(mutex);
  
     /* non-critical section */
  }
  

The semaphore provides the mutual exclusion for sure, and should satify progress, but depending on the implementation of semaphores, may or may not provide bounded waiting.

A semaphore implementation might look like this:

struct semaphore {
  int value;
  proclist L;
};

• wait(S):

     S.value--;
     if (S.value < 0) {
       add this process to S.L;
       block;
     }
  

• signal(S):

    S.value++;
    if (S.value <= 0) {
      remove a process P from S.L;
      wakeup(P);
    }
  

Note that what we have been looking at are counting semaphores. This means that is the semaphore's value is 0 and there are two signal operations, its value will be 2. This means that the next two wait operations will not block.

So semaphores can be used for more general-purpose things than simple mutual exclusion. Perhaps we have a section that we want at most 3 processes in at the same time. We can start with a semaphore initialized to 3.

Semaphores can also be used as a more general-purpose synchronization tool. Suppose statement B in process P_j can be executed only after statement A in P_i. We use a semaphore called flag, initialized to 0:

Here, P_j will be forced to wait only if it arrives at the wait call before P_i has executed the signal.

Of course, we can introduce deadlocks (two or more processes waiting indefinitely for an event that can only be caused by one of the waiting processes).

Consider semaphores Q and R, initialized to 1, and two processes that need to wait on both. A careless programmer could write:

Things might be fine, but they might not be.

There's also the possibility that a process might just forget a signal and leave one or more other processes (maybe even itself) waiting indefinitely.

Semaphore Implementations

There is a POSIX standard for semaphores in Unix. See sem_open(3), sem_wait(3) and sem_post(3).

The pthreads library also includes a semaphore-like construct called a mutex. It is essentially a binary semaphore (only 0 and 1 are allowed). See pthread_mutex_init(3).

Classical Problems of Synchronization

We will use semaphores to consider some synchronization problems. While some actual implementations provide the ability to try to wait, or to examine the value of a semaphore's counter, we restict ourselves to initialization, wait, and signal.

Bounded buffer using semaphores

First, we revisit our friend the bounded buffer.

• Shared data:

  semaphore fullslots, emptyslots, mutex;
  full=0; empty=n; mutex=1;
  

• Producer process:

  while (1) {
    produce item;
    wait(emptyslots);
    wait(mutex);
    add item to buffer;
    signal(mutex);
    signal(fullslots);
  }
  

• Consumer process:

  while (1) {
    wait(fullslots);
    wait(mutex);
    remove item from buffer;
    signal(mutex);
    signal(emptyslots);
    consume item;
  }
  

mutex provides mutual exclusion for the modification of the buffer (not shown in detail). The others make sure that the consumer doesn't try to remove from an empty buffer (fullslots is > 0) or that the producer doesn't try to add to a full buffer (emptyslots is > 0).

Dining Philsophers

• Five philosophers alternate thinking and eating
• Need 2 forks to do so (eating spaghetti), one from each side
• keep both forks until done eating, then replace both

Since fork is the name of a C function, we'll use a different (and possibly more appropriate) analogy of chopsticks. The philosophers needs two chopsticks to eat rice.

• Shared data:

  semaphore chopstick[5];
  chopstick[0..4]=1;
  

• Philosopher i:

  while (1) {
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
  
     /* eat */
  
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
  
     /* think */
  
  }
  

This solution may deadlock. One way to reduce the chances of deadlock might be to think first, since each might think for a different amount of time.

Another possibility:

Each philosopher

1. Picks up their left chopstick
2. Checks to see if the right chopstick is in use
3. If so, the philosopher puts down their left chopstick, and starts over at 1.
4. Otherwise, the philosopher eats.

Does this work?

No! It livelocks. Consider this: all could pick up their left chopstick, look right, put down the left, and repeat indefinitely.

How to solve this? Must either

1. introduce an asymmetry, or
2. limit the number of concurrently hungry philosophers to n-1.

Here's one that includes an asymmetry, by having odd numbered philosophers pick up to the right first. The code for philosopher i and problem size n.

void philosopher() {
  think;
  if (odd(i)) {
    wait(chopstick[(i+1) % n]);
    wait(chopstick[i]);
  }
  else {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % n]);
  }
  eat;
  if (odd(i)) {
    signal(chopstick[(i+1) % n]);
    signal(chopstick[i]);
  }
  else {
    signal(chopstick[i]);
    signal(chopstick[(i+1) % n]);
  }
}

Readers-Writers

We have a database and a number of processes that need access to it. We would like to maximize concurrency.

A possible solution:

• Shared data:

  semaphore wrt, mutex;
  int readcount;
  wrt=1; mutex=1; readcount=0;
  

• Writer process:

  while (1) {
    wait(wrt);
  
      /* perform writing */
  
    signal(wrt);
  }
  

• Reader process:

  while (1) {
    wait(mutex);
    readcount++;
    if (readcount == 1) wait(wrt);
    signal(mutex);
  
      /* perform reading */
  
    wait(mutex);
    readcount--;
    if (readcount == 0) signal(wrt);
    signal(mutex);
  }
  

Note that the semaphore mutex protects readcount and is shared among readers only.

Semaphore wrt is indicates whether it is safe for a writer, or the first reader, to enter.

Danger: a reader may wait(wrt) while inside mutual exclusion of mutex. Is this OK?

This is a reader-preference solution. Writers can starve! This might not be good if the readers are "browsing customers" but the writers are "paying customers!"