0
\$\begingroup\$

I understand the difference between a semaphore and a mutex (I think). Only the task that acquired the mutex can release it.

What if we had three identical ports that are shared amongst tasks and tasks don't care which port they use? We could initialise the counting mutex to three. And we could make sure that only a task that acquired one of these keys returned a key (just like we do with an ordinary mutex).

I must be missing something because, though it seems to make sense to me, I've never heard of a counting mutex.

\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

Because what you've described as a "counting mutex" is a semaphore.

A semaphore has a common resource with a limited number of identical copies; think of a library with 5 copies of a book. Users can go to the library and checkout a copy, and it doesn't matter which copy they get because they're all the same. However, only 5 users can have that book checked out at any one time because there are only 5 copies.

A mutex on the other hand is when you want "mutual exclusion", i.e. a user has exclusive ownership of a resource. Each resource is unique. So say now there is a library which owns only one copy of 5 different books. Each book could have a mutex associated with them because it matters which book you check out, and only one user can checkout a book at a time.

edit:

I suspect the Keil RTX mutex implements this by acquiring a primitive mutex, then once acquired the first thing is to set an ID of who "owns" that mutex. In this case, the library interface prevents users from releasing a mutex they don't own.

Implementing this for a semaphore is trickier, but should be doable. One way is to implement this might be to after acquiring a copy from the primitive semaphore, add your ID to an empty slot in a fixed-size list of what has been checked out. Then to check-back in, check this list for the task ID (optimization: store this spot local to the task so check-in is O(1)), and if you find it remove it from the list. Finally, release the primitive semaphore. Again, this would be a library interface design choice, not something inherent to a semaphore.

The difference now is that checkout is O(n) in the number of copies; this is a huge difference from O(1) for everything before. I don't think libraries want to burden all users with this unnecessary overhead, so most don't implement semaphores like this.

\$\endgroup\$
6
  • \$\begingroup\$ I understand the difference between the counting and the binary semaphore. However, what I'm thinking of is the difference between a semaphore and a mutex. A semaphore can have an initial value of zero, when it's being used for task synchronisation. A task then releases the semaphore, even though it didn't acquire it. This isn't allowed with a mutex as it's too dangerous. What I don't understand is why the concept of "you can only check one back in if you checked one out" can't be used with a mutex protecting a number of identical resources. \$\endgroup\$ Nov 13, 2014 at 16:08
  • \$\begingroup\$ Hopefully you should be writing your code as "Task checks out the semaphore, does something, then it returns the semaphore". This satisfies the requirement that only the task who has checked out a semaphore can return it. The same could be said of most popular mutex implementations; technically anyone can "unlock" them, but code should be written such that you don't unlock unless you've managed to acquire it already. In fact, another task can break mutual exclusion by simply never checking the mutex lock object. \$\endgroup\$ Nov 13, 2014 at 17:51
  • \$\begingroup\$ Keil's CMSIS RTX mutex implementation only allows the task that acquired the mutex to release it. osMutexRelease returns an error if another task tries to release the mutex. This of course prevents a bug from accidentally releasing a mutex. I just wonder why this safety feature isn't available for a counting mutex. \$\endgroup\$ Nov 13, 2014 at 19:59
  • \$\begingroup\$ see edit; this looks like a library interface design, which can be done for a semaphore as well. \$\endgroup\$ Nov 13, 2014 at 20:35
  • \$\begingroup\$ So, for something that wouldn't be used very often, it would add a lot of complexity to the OS. Is that basically it? \$\endgroup\$ Nov 13, 2014 at 21:24
0
\$\begingroup\$

A mutex is a specialization of a semaphore. It's a semaphore that is used to enforce mutually exclusive access to a resource. The implementation of a mutex service typically includes some extra features, beyond that of a semaphore, which support this specialization. One such feature is that the mutex can be released only by the task that obtained it. Another common feature of a mutex is support for a priority inheritance mechanism. (FreeRTOS, uC/OS-II, and ThreadX support this, for example). The task holding the mutex will be raised to the priority of the next task that attempts to obtain the mutex. The priority inheritance mechanism can help to relieve priority inversion problems. Another feature of some mutex implementations is that the same task can take the mutex multiple times. And then that task would have to release the mutex the same number of times before the mutex becomes available for another task. (FreeRTOS calls this feature a "recursive mutex".)

For your example application of multiple identical ports you should use a counting semaphore. The specialized features of a mutex aren't intended for protecting multiple identical resources. A mutex is specialized for protecting a single resource.

You could probably make a different specialization of a counting semaphore that would allow only tasks which have obtained the semaphore to release the semaphore. But I don't believe the other common mutex features, priority inheritance and recursion, would apply well to a counting semaphore.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.