SKC++: No semaphores!
Hypothesis: SKC++ doesn’t need semaphores. If you disagree with this, please comment, with supporting arguments. In the meantime, I’ll present a few arguments of my own, supporting this hypothesis, though I’m not enough of a mathematician to establish it as a law – or even as a theory. I emphasise that I’m talking here about explicit semaphore objects; SKC++ of course has other mechanisms to which can be attributed some semaphore-like aspects.
Semaphores go back to the beginning of time (well real-time software, anyway) but I believe we have moved on and can now leave them behind. They have been used for three things:
- Signalling
- Mutual exclusion
- Synchronisation
For signalling, event flags are better, I believe. SKC++ has event flags, plus a similar but stripped-down mechanism for signalling interrupts.
For Mutual Exclusion the semaphore has several shortcomings and has been largely supplanted by the mutex. SKC++ has mutexes (or should that be mutices?).
Synchronisation between tasks (in the classic sense of a rendezvous, or similar, using a semaphore or condition variable) seems to me to be an odd concept, fraught with problems. Browsing through Niall Cooling’s excellent blog on the subject just reinforces my view. In an event-driven system like SKC++, the idea is that a task should perform some function in response to an event, then just wait for another event. That a task should ever have to wait, during the processing of an event, for some other task or tasks (known or unknown) to reach some particular stage of execution is a different and incompatible concept. Furthermore, I believe that the latter is a very bad basis for a multitasking model because it encourages excessive coupling between tasks.
I maintain (until shown to be misguided) that event flags and message passing are sufficient to support asynchronous processing and also to support structured, arm’s length transactions between tasks and that no other form of synchronisation is necessary.
In reaching my decision not to implement semaphores in SKC++, I considered various problems for which semaphores have been proposed as part of the solution. In each case, I was able to find an alternative solution without much trouble. For example, a “counting semaphore” is often touted as a mechanism for keeping track of the number of spaces available in a car park. Such an approach seems attractive but when the wider problem is looked at (displaying the number of spaces, controlling access through the entry gates, etc.), the counting aspect is the most trivial part. It can easily be incorporated into a central task which communicates intelligently with the gate monitoring/controlling tasks and also provides the display data.
SKC++ enhancement
Consideration of the problems referred to above convinced me that semaphores were unnecessary but also led me to enhance SKC++’s event-handling. As a result, events for each task can now have either fixed priority (as before) or rotating priority.
Peter Bushell's Blog 
Your proposal is generally sound. I certainly agree with the following aspects of what you said:
1. That mutexes are superior to semaphores for mutual exclusion in a system with deadlines. Only the mutex can prevent a priority inversion.
2. That rendezvous is a bad idea. If you are having that kind of coupling between two tasks, there is probably a more elegant solution to your overall software architecture. It probably involves the passing of event ids via message queues.
In most respects, a message queue and a semaphore are identical constructs. The message is always the same (whatever is agreed by sender and receiver) in the case of a semaphore. This means the semaphore implementation is a more efficient subcase of the message queue. If you don’t care about the efficiency of the empty-message subcase of message queues, you can use a message queue for anything you would use a semaphore for (even rendezvous).
I’ve written a few things on mutexes vs. semaphores in my blog at http://www.embeddedgurus.net/barr-code. In addition, I’m the host of a webinar on that subject at http://www.techonline.com.
@Michael Barr
Thanks for your comment, Michael.
In SKC++ the efficiency of the semaphore for signalling (actually slightly better) is obtained by using a bare event flag, without the overhead of an accompanying message where none is needed. However, I’ve stuck my neck out by providing no autonomous object which can stand in for a semaphore (say, for a rendezvous); both event groups and message queues are tied to and are effectively part of the particular tasks which wait at them.
I was going to argue that counting semaphores must be needed for some architectures (maybe a pool of dedicated hardware processors) but thinking about it you can reproduce the behaviour at the application level with the features you provide.
Since I grew up with Ada however, I should make a case for rendezvous. There are certainly cases where the fact that you can exchange data between tasks __in both directions__ is very useful, and can avoid some of the anti-patterns you have mentioned – like loops of events going between tasks (A triggers B triggers C triggers A, etc.).
But as always, you are right – these situations normally occur because the architect hasn’t thought about it enough.
Just a personal point of view – I don’t necessarily expect this to be a consensus opinion.
I’m not sure how useful it is to look at items like semaphores, mutexs, etc. in isolation. The primary question for the designer is ‘what is the software trying to achieve?’ (e.g., passing information between concurrent units, synchronization of operations or protection of operations/data). The next question: what is the ‘best’ way of doing this? Final question: what are the pros/cons of the chosen technique(s)?
Semaphores, mutexs, protected objects etc. are enabling mechanisms; their qualities should be assessed from this point of view.
I think it’s great to remove semaphores from SKC++ for all the reasons you’ve recounted, and hopefully it’ll get people to think about what they’re doing rather than how they’re doing it.
Have you had a look at the Enea OSE and Scipota RTOS API’s. I’m no expert but I believe that they are very message centric and do not provide the lower level primitives found in most other RTOS’.
@David Thompson
Perhaps the concept of a rendezvous in Ada came about because the humble semaphore was in vogue at about the time the language was invented! I reluctantly have to conclude that the vanilla SKC++ won’t be a good candidate for an Ada run-time system.
However, the inner heart of the kernel (downgraded to C), plus a semaphore (easy to code), plus some nasty POSIX, probably, would do the job 🙂
Jim & Niall…
My sentiments, exactly. I mentioned the semaphore only because I imagined many people would expect to see such a thing in any RTOS. I appear to have been wrong about that, happily!
@Dave Banham
I looked at OSE some time ago, and Sciopta after reading your comment. While I like their approach in general, they both exhibit two things which I’m trying to counter:
– Too many system calls
– Written in C
@Peter Bushell
Surprisingly I came across rendezvous recently disguised under the term “synchronous events”, which, when explained, was something like “I send you an event/message, you do something (whilst I wait) and then send me another event/message in response”. So your kernel will cover this kind of pattern perfectly adequately.
Peter, a slightly different angle on the debate: If you are attempting to make the leanest possible system, and feature X can be eliminated, then consider eliminating it. If OTOH you want to make a rich system that gives users a choice of how they go about things, then consider including the feature even if it is “redundant”.
Getting a product accepted is about the user experience. That applies as much to an RTOS as to a toy like an iPad. Have you ever stood behind someone while they use a program you are a hot shot at, say Excel, and suddenly notice them doing something in quite a different way to how you would? That’s richness.
The other argument in favour of richness is that it gives uses more opportunities to perhaps use the product in ways you, the maker, didn’t anticipate. Which of course in an RTOS may not always be a Good Thing 🙂
David Stonier-Gibson http://splatco.com
@David Stonier-Gibson
David, thank you for contributing to the debate. I sense a touch of the Devil’s Advocate, which is healthy.
The three basic principles which guided me in the design of SKC++ were that it should be:
– Easy to learn
– Easy to use
– Difficult to misuse
My own experience and that of other engineers that I have asked about it is that we like to reserve our time and creativity for the challenge facing us. We don’t want to waste too much time learning how a tool works, or agonising about its options; that should not be part of the challenge. I regard SKC++ primarily as a tool for Application Engineers.
Richness does have its place and there is an argument that you appeal to a greater market if you provide all the traditional, “expected” features as well as any new ones. However, my mission these days is not to sell millions of copies of SKC++ (though more than one or two would be nice), but to distil decades of experience into what I do and deliver only the best bits, thereby making my small contribution to improving embedded software quality. (For the historical enlightenment of those starting out in the profession, I might occasionally blog about the less good bits, but that’s another subject.)
Of course the problem with Occam’s Razor is that you can slice off too much. But to counter that by adding redundant features “just in case” is cowardice. There’s a thin line somewhere in between and that’s why I threw the Semaphore argument open.
Here are some other arguments for the lean approach:
– Quicker to market (though I still haven’t got there)
– Less to go wrong
– Easier to add features, on demand, than to take them away after publication
Who knows, I might make more money adding redundant features for traditionalists (or others stuck in their ways by choice or by circumstance) than I make from the basic product!