If you’ve been reading my articles or blog for a while, you’ve probably noticed a few pieces about the differences between mutexes and semaphores. The most concise presentation of these issues that I’ve made was published last year in Embedded Systems Design. That article, called Mutexes and Semaphores Demystified is also available at http://www.netrino.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore.
A new blogger in the embedded software area (Niall Cooling) is revisiting the mutex vs. semaphore subject and reading that caused me to come across a few other sources on the subject. (You can find his blog at http://www.feabhas.com/blog.) The “Toilet Example” that he cites via a link to another website contains one of the worst explanations of the use of semaphores I have seen. I don’t even know where to start rewriting it.
So I challenge you, dear RSS subscribers, can you individually or collectively (a) identify the flaws in the Toilet Example explanation at http://koti.mbnet.fi/niclasw/MutexSemaphore.html and (b) propose a proper implementable solution by way of a rewrite? I suggest we do this via the comment mechanism provided at the end of this blog post.
Tags: education, embedded, programming, rtos
Rename "toilet" to "bathroom". Not only will this resonate better with americans (where "toilet" is an appliance, not a room), it will allow more than one action after gaining access (e.g., washing up) and allow more divers imagining of what might happen.Introduce the gas station attendant, who is the key manager. A misbehaving program might forget to give the key back to the attendant. This would block all others from using the facility, and create a serious system problem while trying to unblock the queue.
Definition of resources and their keys are flawed. The given definition is N toilets all having similar key. So if N-1 toilets are occupied and Bob wants to use a toilet, he would be given a key. But he has no clue which toilet is unoccupied. The story could more be like, with N toilets with a green signal on its top indicating that it is usable. The consumers have to choose one of the toilets with green signal glowing. Immediately as a consumer chooses the toilet, the green signal is turned off, indicating the rest that the toilet is not free anymore.
A very concise explanation of the basic logical flaw, Sundar. Clearly, giving out a generic key to one of two identical "bathrooms" isn't going to be a comfortable way to operate.Note that if we had one men's room and another women's room, then they are no longer identical resources. The solution there is clear: protect each bathroom by a mutex of its own. Men wait on the men's room mutex and women on the women's room mutex. Think COM1 vs. COM2.So what is a practical solution to the identical bathroom problem? It may be helpful to think of them as equal-sized buffers. And note your solution should generalize to more than two.
I think the trouble with the bathroom problem is that each user only needs one bathroom at a time. Let me try re-defining the problem to be you have N identical resources and M users which need to be guaranteed to get a certain quantity of a resource before they can proceed.For example, a bakery might take orders from several customers that want different types of bread. In order to provide the freshest bread, the bakery only processes a customer's order when it can fulfill the entire order at once. Then, the bakery might use a semaphore to track the number of "free" baking tins. Each of the orders would pend on however many tins they required and once the pend completed, "pop" the desired number of tins off the free stack. When the order was completed and the tins washed up, they would be "pushed" back on the free stack and the free semaphore would be posted.Of course, push and pop would still need to be protected by mutex (but you don't need need N mutexes, just one).
Eric, I frequently want to solve the "give me one more buffer from the pool" problem. It is most useful design pattern. Although what you propose is technically a "generalization" of that pattern, I believe that the generalized problem is more expensive to solve than the more common case. Thus I would propose that we first focus on a compact efficient solution to the single bathroom needed case (how would I use both at the same time anyway!? ;-), then go for a more general design after that.Who's next? Anyone want to take a stab at writing up some C pseudo-code? You could use the APIs here: http://www.embeddedgurus.net/barr-code/2008/03/toward-better-mutex-api.html
It is not enough to give a key to the bathroom. You also have to tell the user which bathroom is associated with that specific key. Therefore, you would have to number/name each bathroom, tie a tag to each key which tells the corresponding bathroom for it. If we apply that to C what you we'll get is the following: 1. Each critical and shared resource needs to be distinguishable from all the other critical and shared resources.2. Each semaphore needs to correspond to a specific critical resource. So that when the resource is freed up the user knows which resource it can use.