Re: Glib Semaphores

[Kaz Kylheku <kaz ashi footprints net>]

On Tue, 16 Nov 1999, Karl Nelson wrote:

> Date: Tue, 16 Nov 1999 14:11:05 -0800
> From: Karl Nelson <kenelson@ece.ucdavis.edu>
> Reply-To: gtk-devel-list@redhat.com
> To: gtk-devel-list@redhat.com
> Cc: kenelson@sequoia.ece.ucdavis.edu
> Subject: Glib Semaphores
> Resent-Date: 16 Nov 1999 22:11:10 -0000
> Resent-From: gtk-devel-list@redhat.com
> Resent-cc: recipient list not shown: ;
> 
> 
> Since glib already provides Mutex and Conditional_Signals, it would
> seem like a good idea to provide a common usage of those in the
> form of Semaphores.  Many threading codes in text books are commonly
> expressed in terms of semaphores as there are conceptually simple
> to do things like lock step producer/consumer, flow combining and
> one pass.  

Semaphores are a poor synchronization primitive from a software engineering
standpoint, because it's harder to verify code which uses them to be free of
deadlocks and race than equivalent code that uses condition variables.  I
believe that semaphores do not provide added utility over conditions and
mutexes.

Certain kinds of problems may be expressed more succinctly using sempahores;
typically problems in which the semaphore's internal counter is exploited
in some way to represent some quantity in the problem space. Among such
problems are resource counting and producer-consumer queues.

A possible advantage of semaphores is that because the shared data they protect
is a simple counter, atomic operations may be exploited to perform the
increment and decrement operations. For that, semaphores have to be implemented
specially, rather than in terms of other primitives such as mutexes and
conditions.  This advantage disappears when the semaphores are used in
conjunction with data that must be separately protected anyway (such as
consumer/producer queue), for then the counter might as well be made part of
the queue structure and protected by the queue's mutex, e.g.

	/* wait for item to become available */

	mutex.lock();

	while (count == 0)
	    item_avail_cond.wait(monitor);

	count--;
	/* remove item */
	mutex.unlock();
	space_avail_cond.signal();

If a semaphore is used instead, a mutex is still needed to protect the
queue. 

	item_avail_sem.wait();
	mutex.lock();
	/* remove item */
	mutex.unlock();
	space_avail_sem.signal();

The succint notation comes from the semaphore's internal management of the
queue counter.  Note that the counter is not kept coherent with the queue state
of the queue structure at all times, because the states of the semaphores
change outside of the region protected by the mutex. This means that the
semaphore which represents the number of items doesn't always have a value that
accurately reflects the number of things actually in the queue.  And also note
how there are really two redundant counters: one semaphore measuring available
items, and one counting the remaining space. The invariant that space + items
== max_len is not satisfied at all times! To prove that the queue is not
misused, for example by trying to remove an item from the empty queue, one has
to prove that the semaphores have reasonable values at all times.  In a trivial
example, this doesn't pose a problem, but in large, complex multithreaded
software, this kind of uncertainty can cause real headaches.