Re: [ECOS] No binary semaphore in C API?

[Bart Veer <bartv at redhat dot com>]

>>>>> "Chris" == Chris Gray <gray@acunia.com> writes:

    Chris> Bart Veer wrote:
    >> Arguably there should be an assert in Cyg_Binary_Semaphore::post(),
    >> 
    >> CYG_ASSERT( false == state, "Posting to unlocked binary semaphore");
    >> 
    >> However I am not sure that there is sufficient agreement on the
    >> general semantics of binary semaphores to make that assertion valid.
    >> Some people might expect multiple posts to be a no-op. IMO the absence
    >> of completely clear semantics for a synchronization primitive is a
    >> good argument for removing that primitive completely.

    Chris> As I understand it, the theoretical semantics of a binary
    Chris> semaphore is that you "cannot" post to it twice. To the
    Chris> theoretician, the question of what happens when something
    Chris> that can't happen happens is purely hypothetical.

Maybe it is time to look at some history.

Looking at a 15-year old copy of an OS reference book, Peterson and
Silberschatz, it describes the use of semaphores for mutual exclusion.
However there are some problems with this use: most importantly a
semaphore does not have the concept of a current owner thread, so the
system can do nothing about priority inversion problems. Hence the
introduction of a new primitive, the mutex, for mutual exclusion.
Semaphores are still very useful, but as a means of communicating
information between threads rather than for mutual exclusion.

The original posting that started this thread involved a scenario
where a mutex could not be used for mutual exclusion, so a binary
semaphore was substituted instead. A side effect of this is that the
system cannot help avoid priority inversion problems, so that will
have to be addressed at the application level. For mutual exclusion
usage, you need to worry about what happens if the application
incorrectly executes a sequence lock/unlock/unlock/lock. IMO this
should result in an assertion failure inside the second unlock, to
facilitate tracking down the problem.

Sergei described an alternative usage of binary semaphores as a
synchronization primitive, for communication between threads:
basically a way of informing other threads that some event has
happened at least once. For this usage multiple posts to a binary
semaphore should be equivalent to a single post, i.e. there is no
difference in behaviour between wait/post/wait and
wait/post/post/wait. For this usage, the assertion would be incorrect.

Now, I am not entirely convinced that this use of binary semaphores is
a good idea. Specifically, consider the sequences of events
wait/post/post/wait and wait/post/wait/post, where the waits and the
posts happen in different threads and are not otherwise synchronized.
Depending on very subtle timing differences, e.g. when the thread
doing the posts gets timesliced, both sequences are equally likely to
happen but the resulting behaviour would be very different. I am
somewhat uncomfortable with a synchronization primitive that can lead
to such non-deterministic behaviour.

The current binary semaphore implementation does not have the
assertion, so it is not the best solution for mutual exclusion. That
argues for a new class, e.g. Cyg_UnownedMutex, to serve that purpose.
The Cyg_Binary_Semaphore class could then be left as is, i.e. behaving
as per Sergei's event signalling usage. That could still confuse
people who are used to thinking about binary semaphores as a legal
mutual exclusion primitive, as per old reference titles. To avoid that
we could also rename Cyg_Binary_Semaphore to something else, breaking
the historical association.

I am not sure anybody would be happy with this solution.

Bart