cs357 Lecture Notes
Spring 2000
Week 10, Tuesday

For today you should have finished homework 6.

Homework 7 is available now.  It is due next Tuesday 18 April.
As always, you should meet with your partner as soon as possible!

Also next Tuesday, we're having an exam!  It will cover everything
through Chapter 6, and all homeworks through homework 7.

Semaphores continued
----------

Last time, I explained the big picture:

1) all synchronization primitives are equivalent

2) different systems provide different ones

3) you can always implement what you need in terms of the others

4) arguably, semaphores are the most versatile, so we will
   use them to implement solutions to common synchronization
   problems

And I presented the semantics of semaphores:

A semaphore is an integer that is initialized and
then accessed only through two operations:

wait   P  proberen   decrement   "test and wait if necessary"
signal V  verhogen   increment   "signal and wake if necessary" 

Think of the value as being the number of locks available,
if non-negative, or the number of people in queue if negative.

If you invoke P while value >= 1, you don't have to wait.
If you invoke P while value <= 0, you have to wait

If you invoke V while value < 0, you are reducing the length
                                 of the queue, so you have
				 to wake someone up 

Implementation
--------------

Here is the implementation that uses a mutex and a condition
variable.

Warning: the following pseudocode contains an error that
you will discover as part of homework 7.

If you see it, shh!


wait (Semaphore *s)
{
    acquire (s->mutex);
    s->value--;
    if (s->value < 0) {
        wait (s->cond_var);   // note that this releases the mutex
    }
    release (s->mutex);
}
	   
signal (Semaphore *s)
{
    acquire (s->mutex);
    s->value++;
    if (s->value < 0) {
        signal (s->cond_var);   
    }
    release (s->mutex);
}

POSIX provides an implementation of Semaphores, but not as
part of the Pthread package.  See the man page for sem_init.

     (check out the veneers lock.c and cond.c)


Bounded buffer problem
----------------------

a.k.a. producer-consumer problem

1) producer puts things into a shared buffer (think of an
   array of integers)

2) consumer takes things out

Maximum capacity is fixed.

Example: coke machine

Synchronization requirements:

1) can't take coke from an empty machine

2) can't put coke into a full machine

3) have to maintain mutually exclusive access to machine


Initialize three Semaphores:

fullBuffers = 0
emptyBuffers = capacity
machineFree = 1

Producer code (coke delivery man)

wait (emptyBuffers)
wait (machineFree)
    put one Coke in machine
signal (machineFree)
signal (fullBuffers)


Consumer code (coke drinker)

wait (fullBuffers)
wait (machineFree)
    put one Coke in machine
signal (machineFree)
signal (emptyBuffers)


First, notice that the Semaphores are not all being
used the same way.

machineFree is simply acting as a mutex; it's value
is always 0 or 1

fullBuffers counts the number of cans of coke, or
the number of people waiting in queue

emptyBuffers counts the number of empty slots, or
the number of producers waiting with cans of coke.

Likely scenario: there is only one producer, running
in a loop, so emptyBuffers is never lower than -1.

Moral: high-level sync mechanisms like Semaphores allow
complicated problems to be solved with readable,
demonstrably correct, symmetric code.

Well, almost.

What would happen if you reversed the order of the first
two statements?


Readers/writers problem
-----------------------

Similar to mutual exclusion, except that it is ok to
have multiple readers, but not multiple writers and not
readers and writers at the same time.

1) readers can proceed as long as there are zero writers
2) writers can proceed as long as there are zero readers
   and zero writers

Variables:

integer readcount;    // how many readers in the room?
Semaphore mutex;      // protect access to readcount
Semaphore wrt;        // can a writer enter?

Mutex is being used as a lock; wrt is being used
as a condition variable!  Versatile, no?


The writer code is simple:

wait (wrt)
    do some writing
signal (wrt)

This provides mutual exclusion among writers, but also
gives readers an ability to control writers.  Here's
the reader code:

wait (mutex)
  readcount++
  if (readcount == 1) wait (wrt);
signal (mutex)

    do some reading

wait (mutex)
  readcount--;
  if (readcount == 0) signal (wrt);
signal (mutex)


The use of mutex is obviously correct, in the sense of
providing mutual exclusion.

The first reader to enter has to bar writers by decrementing wrt

    if there were no writers, then the reader proceeds
    and future writers are barred

    if there is a writer then we wait for him to leave

    while we wait, no other readers can get mutex!

Subsequent readers don't have to wait on wrt, because
the presence of a prior reader indicates that it is
safe to enter, and that writers are already barred.

For similar reasons, the last reader to leave has to
unbar the writers.

Problem with this solution: writer might have to wait
forever while readers come and go.  We might like to
have a system where the readers already in the system
can finish, but once a writer arrives, future readers
have to wait.


Dining philosophers

Five philosophers.  Five chopsticks.  Each philosopher
needs two chopsticks to eat.

Chopsticks represent resources that need to be allocated
to threads, in the case where a thread needs to allocate
multiple resources before it can make progress.

Simple solution:

while (true) {
  wait (chopstick[i])
  wait (chopstick[(i+1)%5])

     eat

  signal (chopstick[i])
  signal (chopstick[(i+1)%5])

     think
}

Problem?  Deadlock!

Solutions:

1) no more than 4 philosophers (not clear to me that this
   is true)

2) only pick up one chopstick if you know you can get both

3) run different code for odd and even philosophers