boost::semaphore

From: williamkempf_at_[hidden]
Date: 2001-10-22 12:42:06

Below is a private e-mail sent to me by Alexander Terekhov regarding 
the
POSIX implementation of boost::semaphore.  If you follow the link he
includes to a Usenet discussion archived on Google you'll see a 
thread that
leads me to make two conclusions that may change the public interface 
of
boost::semaphore.  Since the Boost.Threads library has been accepted 
and
released I want to ask opinions before deciding to make any such 
changes.

Here are the conclusions I reach, which result in two very different
changes.

1)  Despite my use of the MAX count for MS semaphores in the past 
which lead
to the inclusion in Boost.Threads Alexander shows that this concept 
only
results in a race condition.  I agree with Alexander that this 
concept needs
to be removed from boost::semaphore.

2)  He quotes a classic paper by Hansen which states that semaphores 
are
unsafe for general use and that the mutex/condition combination can 
achieve
all of the same synchronization needs (the only caveat being 
performance,
though that's going to depend significantly on the implementation of 
all of
the synch concepts and isn't really worth using as an argument for 
keeping).
  Beman already suggested we consider removing semaphore during the 
review
process, and, unfortunately, I felt there wasn't enough reasoning for
removing this "fundamental" concept and didn't do so.  Now I'd like to
reconsider and simply remove it completely.

Thoughts?  Comments?  Concerns?

Bill Kempf

Bill Kempf
williamkempf_at_[hidden]

>From: "Alexander Terekhov" <TEREKHOV_at_[hidden]>
>To: williamkempf_at_[hidden]
>Subject: Boost.Thread semaphore POSIX impl
>Date: Mon, 22 Oct 2001 16:17:05 +0200
>
>
>Hi Bill,
>
>Seems to me that Boost.Thread semaphore POSIX impl.
>is incorrect because it does not follow POSIX defs:
>
>"Semaphore Lock Operation
>
>  An operation that is applied to a semaphore. If, prior to the
>  operation, the value of the semaphore is zero, the semaphore
>  lock operation shall cause the calling thread to be blocked
>  and added to the set of threads awaiting the semaphore; ..."
>
>a) !! NO DECREMENT !!
>
>"...otherwise, the value shall be decremented."
>
>b) DECREMENT; decrease level of allowed concurrency.
>
>"Semaphore Unlock Operation
>
>  An operation that is applied to a semaphore. If, prior to the
>  operation, there are any threads in the set of threads awaiting
>  the semaphore, then some thread from that set shall be removed
>  from the set and becomes unblocked; ..."
>
>a) !! NO INCREMENT !!
>
>"...otherwise, the semaphore value shall be incremented."
>
>b) INCREMENT; increase level of allowed concurrency.
>
>here is an example which i believe illustrates how
>_correct_ impl should look like (modified
>http://groups.yahoo.com/group/boost/message/18615 ):
>
>class semaphore
>{
>   pthread_mutex_t mutex;
>   pthread_cond_t signal_occurred;
>   unsigned sem_cnt;
>   unsigned sem_waiting;
>   unsigned sem_signaled;
>public:
>
>   void lock()
>   {
>     pthread_mutex_lock(&mutex);
>     if (0 != sem_cnt) {
>       --sem_cnt;
>     }
>     else {
>       ++sem_waiting;
>       do {
>         // add proper cleanup handler!!!
>         pthread_cond_wait(&signal_occurred, &mutex);
>       } while (0 == sem_signaled);
>       --sem_signaled;
>       // add synch to unblock destructor thread,
>       // because POSIX says: "39080 It is safe to
>       // destroy an initialized semaphore upon which
>       // no threads are currently blocked.
>     }
>     pthread_mutex_unlock(&mutex);
>   }
>
>   void unlock()
>   {
>     pthread_mutex_lock(&mutex);
>     if (0 == sem_waiting) {
>       ++sem_cnt;
>       pthread_mutex_unlock(&mutex);
>     }
>     else {
>       --sem_waiting;
>       ++sem_signaled;
>       pthread_mutex_unlock(&mutex);
>       pthread_cond_signal(&signal_occurred);
>     }
>   }
>
>   ~semaphore()
>   {
>     // add synch to wait for last signaled
>     // thread to acquire the mutex/retract
>     // waitor status...
>   }
>
>};
>
>also, i think that MS-MAX checks are pretty
>useless because semaphore does not really
>track the number of threads using resource(s)
>protected by semaphore. what it does is simply
>provides means of control of how many *more*
>threads are allowed to pass the semaphore lock
>operation not waiting for subsequent unlock(s).
>more info on MS-MAX silliness, IMHO:
>
>http://groups.google.com/groups?as_umsgid=3BC7661C.D364599E%40web.de
>
>regards,
>alexander.
>
>ps. CV destructor needs some synch to correctly
>handle signal/broadcast&delete case (similar to
>~semaphore), see pthreads-win32 CV impl in cvs.
>
>