[ECOS] No binary semaphore in C API?

[Sergei Organov]

Bart Veer <bartv@redhat.com> writes:

[...]

> 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.

Exactly. I started to write my own explanation of differences, but you already
explained it perfectly. The only thing that I'd like to make more explicit is
that having owner concept not only makes provision for implementing of
priority inheritance, but also is a good thing by itself as unlocking mutex by
non-owner is explicitly prohibited. It's like bathroom door lock, -- once you
entered the bathroom and locked the door, nobody else can enter until you
unlock it, -- that's what mutual exclusion is about. Using binary semaphore
for mutual exclusion resembles using of bathroom lock that is easily unlocked
from outside. 

>
> 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.

I think that original post has a scenario for which there is no primitive in
eCos that exactly matches requirements and there will never be one I guess as
the problem that should be solved is rather complex and hopefully
rare. Somebody (you?) described it as "mutual exclusion between thread
groups". For me it belongs to the same class as read-write locks but
apparently is even more complicated. One of solutions, IMHO, is to implement
special object on top of primitives that eCos provides and use it in the
application. Then it will be this object that will take care of preserving
semantics of eCos primitives it uses. And if it is possible to build it on top
of current binary semaphore, it is also possible to build it on top of current
counting semaphore, I believe.

I'm still not convinced that tuning eCos primitive for such questionable usage
is a good idea especially as it prohibits another possible application.

>
> 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 intended usage assumes that the two sequences you've mentioned don't
actually make visible behavior of the program different, otherwise there is a
race condition and thus the program is just incorrect. If a program is broken,
it's just broken no matter what primitive is used.

In the simplest case the suggested use for (otherwise obsolete?) binary
semaphore is a producer-consumer model where consumer should process the
recent produced data as soon as possible and it's not required to process
every peace of produced data. Here single producer thread makes posts and
single consumer thread makes waits on binary semaphore. It also seems to be
valid to have multiple consumer threads that otherwise do the same job. This
could be useful on multiprocessor systems to increase performance.

>
> 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.

Now about names. For me Cyg_UnownedMutex sounds strange. Maybe I don't
understand something very basic, but for me "Unowned" and "Mutex" are
contradicting terms. Mutex should have owning semantics, I believe. Either it
is only single thread that can own mutex or "group of threads", but concept of
owning is what differs mutex from semaphore, as you correctly said at the
beginning of the message.

To add even more to the discussion, binary semaphore could be considered to be
just a counting semaphore with upper bound of count equal to 1. Current
counting semaphore is then counting semaphore with upper bound set to
arbitrary rather large number, e.g., INT_MAX. Then back to initial
question. What is semantics when counting semaphore is at upper bound and
'post' is invoked?  The discussion indicates that both semantics could be
useful. Unfortunately strict semantics that disallows such operation makes it
impossible to use the primitive for the purpose above. Less  restrictive
semantics does allow both uses. It just doesn't help to catch some programming
mistakes. Having that, I think it's OK to have only a no-op semantics.

I have nothing against having both semantics, I just doesn't think it is worth 
efforts.

Sergei.