Agenda

• Announcements
• More Critical Sections
• Semaphores
• Classical Problems of Synchronization

Announcements

More Critical Sections

We left off with the Bakery Algorithm. Hopefully everyone's convinced that it works. Here are some 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

More next time....