From mboxrd@z Thu Jan 1 00:00:00 1970 From: Sergei Organov To: bartv@redhat.com Cc: ecos-discuss@sourceware.cygnus.com Subject: Re: [ECOS] No binary semaphore in C API? Date: Fri, 30 Mar 2001 02:22:00 -0000 Message-id: <8766greeto.fsf@osv.javad.ru> References: <20010316140116.A1062@visi.com> <3AB67D44.AFB5E10D@redhat.com> <20010326133727.A3008@visi.com> <200103281329.f2SDT3b05686@sheesh.cambridge.redhat.com> <3AC2E765.7331A9CF@acunia.com> <200103291118.f2TBIep15036@sheesh.cambridge.redhat.com> X-SW-Source: 2001-03/msg00532.html Bart Veer 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.