Re: Glib Semaphores

[Kaz Kylheku <kaz ashi footprints net>]

On Tue, 16 Nov 1999, Karl Nelson wrote:

> Probably true, but then some things are better represented one way 
> while others are better represented in others.  I assume the user
> will chose the most appropriate representation.
> 
> [...]
> A typical example of producer/consumer expressed if lock step operation
> is necessary can be cleanly written with semaphores like this. 
> 
>  main:
>    // spawn threads
>    process.down();  // wait until all processes die to terminate
>    process.down();

This is almost always done best by a special ``join'' system call.  E.g.
pthread_join() in POSIX, or, heaven forbid, WaitForSingleObject() on a thread
handle in Win32.

Failing that, the down() function could easily be implemented by
a condition.

	process_type::join()
	{
	    mutex.lock();
	    while (state != dead)
		cond.wait(mutex);
	    mutex.unlock();
	}

When the thread dies, it sets the state to dead and broadcasts the condition.
All waiting threads are released, and anyone who subsequently acquires the
mutex finds the thread in a dead state. Note that you can safely call

	process.join();

multiple times without deadlocking; it's an idempotent operation. Also,
multiple threads can call process.join() to wait for a given process to die,
(so long as cond.broadcast() is used to indicate the termination.) 

>  consumer:
>    while (want_items)
>      {
>        consumer.down();
>        // eat up an item
>        producer.up();
>        // do some more processing which is not shared
>      }
>    process.up();
> 
>  producer:
>    while (can_produce)
>      {
>        producer.down();
>        // produce some items.
>        consumer.up();
>        // more unshared processing
>      }
>    process.up();
>
> Here, I don't need any more mutexs nor do I need to worry about
> the recombining.

Instead you now have to worry whether the initial states of your semaphores
is logically correct with respect to the item list.

What has to be true initially? Suppose the queue starts empty, a reasonable
initial state. Then the producer semaphore should be up, so that the producer
can get in to the code that produces items.  The consumer semaphore should be
down, so the consumer is forced to wait.  With conditions, you don't worry,
because they have no state.

I find the code snippet surprisingly difficult to understand given its trivial
size. I can't see how it can work unless I work backward to what the correct
values for the semaphores must be. It's not even immediately obvious that
the queuing operations are properly protected from each other.

It's only easy if you have a textbook example that you can trust.  To that I
say, get a textbook that teaches semaphores as well as conditions.

> so arguments about representing some queue length don't really 
> apply.

It's true that you are now not representing queue length, but you are using the
semaphores to represent some other attribute of the queue: namely empty
and non-empty.

Note the producer is waiting on the ``empty'' predicate, which is is
unnecessarily strong; the weakest precondition for adding something to a queue
is that it's not full, not that it's empty.

The excessively weak predicates that are implied result in strict alternation
between producer and consumer, which wastes cycles. An implementation of this
could run thousands of times slower than similar code that context switches
only involuntarily or at queue boundaries---for example by using conditions
or by using counting semaphores rather than binary semaphores.