Semaphores

basically a non-negative integer variable that saves the number of wakeup signals sent so they are not lost if the process is not sleeping

another interpretation we will see is that the semaphore value represents the number of resources available

Semaphores can only be accessed by two operations (they will be system calls)

P (or down in Tanenbaum MOS)

V (or up)

semaphore S shared integer variable usually initialized to 1

  P(S): trap to the kernel
        disable interrupts (so semaphore access is atomic)
        if S > 0 then S := S - 1
        else { queue the process on S, change its state to blocked,
               schedule another process }
        enable interrupts
        return

  V(S): trap to the kernel
        disable interrupts
        if S = 0 and queue on S is not empty then
                      { pick a process from the queue on S,
                        change its state from blocked to ready }
        else S := S + 1
        enable interrupts
        return

if we have a shared-memory multiprocessor instead of a uniprocessor, then disabling interrupts to access S atomically is not good enough since disabling interrupts on one processor has no effect on another processor

instead we use test_and_set on a lock variable internal to the kernel, where there is a lock variable for each semaphore

a test_and_set which busy waits internal to the OS is not considered a busy-waiting solution to the mutual exclusion problem because the process doing the P operation is blocked if S is 0

or we can lock the bus and unlock it when done

Now we can implement

mutex_begin: P(S)

mutex_end: V(S)

Semaphores can be used in two ways

1. mutual exclusion to avoid race conditions in accessing shared data in critical sections in concurrently executing processes

   P(S) count++ V(S) /* S only takes on values 0, 1 */

   S is called a binary semaphore

2. process synchronization (also called condition synchronization)

       P(empty) ... V(full)
       P(full)  ... V(empty)
   

   the semaphore represents the number of resources available and is called a counting semaphore

SR Semaphores

Why is the semaphore mutex also used in the auditor process? Isn't is enough just to make the moving of money from one account to another in the ATM process into a single atomic action?
SR Program: A Semaphore Prevents Another Race Condition.

Semaphores can be used for process synchronization that is not for mutual exclusion. For example, this program starts three processes: Pa, Pb, and Pc. Only Pa can output the letter A, Pb B, and Pc C. Utilizing semaphores (and no other variables) the processes are synchronized so that the output satisfies the following conditions:

1. A B must be output before any C's can be output.
2. B's and C's must alternate in the output string, that is, after the first B is output, another B cannot be output until a C is output. Similarly once a C is output, another C cannot be output until a B is output.
3. The total number of B's and C's which have been output at any given point in the output string cannot exceed the number of A's which have been output up to that point.

This is an SR program simulating the bounded buffer producer and consumer classical OS problem. There is one producer and one consumer process that share a buffer of some finite number of slots. Three semaphores are used: one for mutual exclusion on updating the value of the variable count and two for condition synchronization (to keep a producer from putting something in a full buffer and to keep a consumer from taking something out of an empty buffer).
SR Program: Bounded Buffer Producer and Consumer.

Bounded buffers are useful for many things. For example, if you have a bunch of computations that can each be broken into several parts, each part taking about the same amount of time, then the series of computations can be performed in an assembly line, conveyor belt, or pipeline fashion. Each part will be handled by its own process. If a CPU can be dedicated to each process, then the series of computations can be performed faster.

The same basic idea is used in the vector or pipeline units in the Cray architecture. Adding two floating point vectors is a series of computations: C[i] = A[i] + B[i] for i = 1, 2, ..., N. Each addition operation can be broken into several parts or suboperations: compare the exponents, align the mantissas, etc. Each part can be done to the pairs of vector components in an assembly line fashion as the pairs stream into the vector unit.

This SR example program starts three processes. The first creates a random real number to which three operations or steps need to be performed: take the square root, then the sin, then square the number. Each of the three steps is performed in a process. Random SR naps are done to make each step take some real time. The first two processes use two bounded buffers to communicate their results to the next process. The bounded buffer can hold several intermediate results if the depositing process gets ahead of the fetching process.
SR Program: Bounded Buffer Pipeline.

For those interested in Java, here is the same bounded buffer producer and consumer program rewritten in Java. Included is an example compile and run. Note that since Java does not provide semaphores, we have to write our own binary and counting semaphore classes.
Java Program: Bounded Buffer Producer and Consumer.

Goals of a solution to the dining philosophers problem

• a fork used by only one philosopher at a time (mutual exclusion)
• a philosopher must have possession of both forks at the same time to eat
• no deadlock
• maximal concurrency -- a hungry philosopher should eat right away if both its forks are available (are not being used by another philosopher)

  used to eat, i.e. used does not mean hold and wait for other fork

  this is a form of no starvation in the absence of contention

• no starvation in the presence of contention -- a hungry philosopher should eventually get to eat

Bad solution

  philosopher(i):
    do true ->
      think()
      pick_up_left_fork()
      pick_up_right_fork()
      eat()
      put_down_left_fork()
      put_down_right_fork()
    od

Also suffers from starvation in the absence of contention if the philosophers get hungry in a ``bad'' order.

Even if you permit at most 4 of the 5 philosophers into the room to eat at any one time, this solution will still suffer from starvation in the absence of contention if they enter the room in a ``bad'' order.

Another bad solution

  philosopher(i):
    do true ->
      think()

      do not have_both_forks ->
        pick_up_left_fork()
        if right_fork_free ->
          pick_up_right_fork()
        [] put_down_left_fork()
        fi
      od

      eat()
    od

Here is a solution using semaphores that

satisfies all but no starvation in presence of contention

two philosophers can collaborate to starve the philosopher between them by coordinating their think and eat times to make sure one of the two is always eating, thus preventing the one in the middle from ever eating, so once it gets hungry it starves -- literally

This semaphore solution to the readers-writers problem can let writers starve because

readers arriving after a now-waiting writer arrived earlier can still access the database to read

if enough readers continually trickle in and ``keep the database in a read state'' then that waiting writer will never get to write

Sleeping barber

semaphores customers, barber, cutting all initially zero
integer waiting initially zero

  barber:                     customers:
    do true ->                  do true ->
      P(customers)                wander and grow hair for a while
      waiting--                   if waiting < number_chairs ->
      V(barber)                     waiting++
      P(cutting)                    V(customers)
    od                              P(barber)
                                    get hair cut for some time
                                    V(cutting)
                                  fi
                                od

still need a binary semaphore mutex to protect checking the value of waiting to see if there is room in the waiting room and to protect the ++ and -- of waiting

problem in this solution if multiple barbers: one barber could race ahead of another after doing V(barber) and before P(cutting) so a barber could release one customer with V(barber) but end up cutting another customer's hair with P(cutting)

not so much a problem here but in other situations this might be wrong

Animating Operating Systems Algorithms

Snapshot of the animation.

Have a look at the actual animation.
XTANGO Animation of Dining Philosophers.

If two philosophers collaborate, they can ``starve'' the one between them.
File Containing Animation Commands.
Snapshot of the animation.

Complete animation.
A Starving Philosopher.