[boost] Re: thread lib review

From: John Maddock (John_Maddock_at_[hidden])
Date: 2001-09-09 05:55:03

>I wasn't aware that POSIX had a counting semaphore?  Regardless, the 
>limit isn't truly infinity is it?  Infinity certainly 
>wouldn't "simplify" the implementation AFAICS.  I also don't see how 
>a fixed max size would simplify things over a user specified max size 
>(within limits).

What I'm suggesting is the rest of the lib follows the POSIX standard quite
closely - except for semaphore.

Heres the summary from the POSIX v6 draft:

3199 4.15 Semaphore
3200 A minimum synchronization primitive to serve as a basis for more
complex synchronization
3201 mechanisms to be defined by the application program.
3202 For the semaphores associated with the Semaphores option, a semaphore
is represented as a
3203 shareable resource that has a non-negative integer value. When the
value is zero, there is a
3204 (possibly empty) set of threads awaiting the availability of the
semaphore.
3205 For the semaphores associated with the X/Open System Interface
Extension (XSI), a semaphore
3206 is a positive integer (0 through 32767). The semget( ) function can be
called to create a set or array
3207 of semaphores. A semaphore set can contain one or more semaphores up
to an implementation-3208
defined value.
3209 Semaphore Lock Operation
3210 An operation that is applied to a semaphore. If, prior to the
operation, the value of the
3211 semaphore is zero, the semaphore lock operation shall cause the
calling thread to be blocked and
3212 added to the set of threads awaiting the semaphore; otherwise, the
value shall be decremented.
3213 Semaphore Unlock Operation
3214 An operation that is applied to a semaphore. If, prior to the
operation, there are any threads in
3215 the set of threads awaiting the semaphore, then some thread from that
set shall be removed from
3216 the set and becomes unblocked; otherwise, the semaphore value shall be
incremented.

the rationale is relevant as well:

4288 Semaphores
4289 Semaphores are a high-performance process synchronization mechanism.
Semaphores are
4290 named by null-terminated strings of characters.
4291 A semaphore is created using the sem_init( ) function or the sem_open(
) function with the
4292 O_CREAT flag set in oflag .
4293 To use a semaphore, a process has to first initialize the semaphore or
inherit an open descriptor
4294 for the semaphore via fork ().
4295 A semaphore preserves its state when the last reference is closed. For
example, if a semaphore
4296 has a value of 13 when the last reference is closed, it will have a
value of 13 when it is next
4297 opened.
4298 When a semaphore is created, an initial state for the semaphore has to
be provided. This value is
4299 a non-negative integer. Negative values are not possible since they
indicate the presence of
4300 blocked processes. The persistence of any of these objects across a
system crash or a system
4301 reboot is undefined. Conforming applications shall not depend on any
sort of persistence across
4302 a system reboot or a system crash.
4303 •Models and Requirements
4304 A realtime system requires synchronization and communication between
the processes
4305 comprising the overall application. An efficient and reliable
synchronization mechanism has
4306 to be provided in a realtime system that will allow more than one
schedulable process
4307 mutually-exclusive access to the same resource. This synchronization
mechanism has to
4308 allow for the optimal implementation of synchronization or systems
implementors will
4309 define other, more cost-effective methods.
4310 At issue are the methods whereby multiple processes (tasks) can be
designed and
4311 implemented to work together in order to perform a single function.
This requires
4312 interprocess communication and synchronization. A semaphore mechanism
is the lowest
4313 level of synchronization that can be provided by an operating system.
4314 A semaphore is defined as an object that has an integral value and a
set of blocked processes
4315 associated with it. If the value is positive or zero, then the set of
blocked processes is empty;
4316 otherwise, the size of the set is equal to the absolute value of the
semaphore value. The value
4317 of the semaphore can be incremented or decremented by any process with
access to the
4318 semaphore and must be done as an indivisible operation. When a
semaphore value is less
4319 than or equal to zero, any process that attempts to lock it again will
block or be informed that
4320 it is not possible to perform the operation.
4321 A semaphore may be used to guard access to any resource accessible by
more than one
4322 schedulable task in the system. It is a global entity and not
associated with any particular
4323 process. As such, a method of obtaining access to the semaphore has to
be provided by the
4324 operating system. A process that wants access to a critical resource
(section) has to wait on
4325 the semaphore that guards that resource. When the semaphore is locked
on behalf of a
4326 process, it knows that it can utilize the resource without
interference by any other
4327 cooperating process in the system. When the process finishes its
operation on the resource,
4328 leaving it in a well-defined state, it posts the semaphore, indicating
that some other process
4329 may now obtain the resource associated with that semaphore.
4330 In this section, mutexes and condition variables are specified as the
synchronization
4331 mechanisms between threads.
4332 These primitives are typically used for synchronizing threads that
share memory in a single
4333 process. However, this section provides an option allowing the use of
these synchronization
4334 interfaces and objects between processes that share memory, regardless
of the method for
4335 sharing memory.
4336 Much experience with semaphores shows that there are two distinct uses
of synchronization:
4337 locking, which is typically of short duration; and waiting, which is
typically of long or
4338 unbounded duration. These distinct usages map directly onto mutexes
and condition
4339 variables, respectively.
4340 Semaphores are provided in IEEE Std 1003.1-200x primarily to provide a
means of
4341 synchronization for processes; these processes may or may not share
memory. Mutexes and
4342 condition variables are specified as synchronization mechanisms
between threads; these
4343 threads always share (some) memory. Both are synchronization paradigms
that have been in
4344 widespread use for a number of years. Each set of primitives is
particularly well matched to
4345 certain problems.
4346 With respect to binary semaphores, experience has shown that condition
variables and
4347 mutexes are easier to use for many synchronization problems than
binary semaphores. The
4348 primary reason for this is the explicit appearance of a Boolean
predicate that specifies when
4349 the condition wait is satisfied. This Boolean predicate terminates a
loop, including the call to
4350 pthread_cond_wait( ). As a result, extra wakeups are benign since the
predicate governs
4351 whether the thread will actually proceed past the condition wait. With
stateful primitives,
4352 such as binary semaphores, the wakeup in itself typically means that
the wait is satisfied. The
4353 burden of ensuring correctness for such waits is thus placed on all
signalers of the semaphore
4354 rather than on an explicitly coded Boolean predicate located at the
condition wait. Experience
4355 has shown that the latter creates a major improvement in safety and
ease-of-use.
4356 Counting semaphores are well matched to dealing with producer/consumer
problems,
4357 including those that might exist between threads of different
processes, or between a signal
4358 handler and a thread. In the former case, there may be little or no
memory shared by the
4359 processes; in the latter case, one is not communicating between
co-equal threads, but
4360 between a thread and an interruptlike entity. It is for these reasons
that IEEE Std 1003.1-200x
4361 allows semaphores to be used by threads.
4362 Mutexes and condition variables have been effectively used with and
without priority
4363 inheritance, priority ceiling, and other attributes to synchronize
threads that share memory.
4364 The efficiency of their implementation is comparable to or better than
that of other
4365 synchronization primitives that are sometimes harder to use (for
example, binary
4366 semaphores). Furthermore, there is at least one known implementation
of Ada tasking that
4367 uses these primitives. Mutexes and condition variables together
constitute an appropriate,
4368 sufficient, and complete set of interthread synchronization
primitives.
4369 Efficient multi-threaded applications require high-performance
synchronization primitives.
4370 Considerations of efficiency and generality require a small set of
primitives upon which more
4371 sophisticated synchronization functions can be built.
4372 •Standardization Issues
4373 It is possible to implement very high-performance semaphores using
test-and-set
4374 instructions on shared memory locations. The library routines that
implement such a high-
4375 performance interface has to properly ensure that a sem_wait() or
sem_trywait() operation
4376 that cannot be performed will issue a blocking semaphore system call
or properly report the
4377 condition to the application. The same interface to the application
program would be
4378 provided by a high-performance implementation.

>When debugging you want the trap to occur as close to the error as 
>possible, which is what asserts are good at.  With an exception the 
>debugger will trap several levels down from where the error actually 
>occurred, possibly even further down than a debugger allows you to 
>traverse back up the stack with.  Also, many (most?) debuggers allow 
>you to step over the assertion, which would allow you to debug your 
>exception trapping code.  To my mind asserts are for debugging and 
>exceptions are for error handling.

OK, but does that mean that operator new should assert rather than throw?
These are both resource acquisition errors.

>Well, I don't know BeOS, but if it supports mutexes then you can 
>emulate a condition, much as we did for Win32.  The emulation will be 
>much more efficient if BeOS has a counting semaphore, though.  Does 
>it?

It has a counting semaphore and nothing else (no mutexes etc), there is
also no user-defined upper limit to the semaphore (like POSIX), and it's
not FIFO as far as know (does that matter?).

>Even the POSIX specific stuff isn't always 100% portable and/or 
>detectable.  For example, pthread_yield() does not appear to be 
>universally available, nor is there a defined macro that indicates 
>it's presence or not.  Though I could be wrong.  I'm not a POSIX 
>programmer and have relied on research and input from others.

It's got no macro, because it doesn't exist as far as POSIX is concerned:
POSIX used sched_yield() for this, and it's predicated on:

defined(_POSIX_PRIORITY_SCHEDULING) && (_POSIX_PRIORITY_SCHEDULING > 0)

Presumably pthread_yield() is specific to one particular vendor?

- John Maddock
http://ourworld.compuserve.com/homepages/john_maddock/