Synchronization internals -- the semaphore

November 03, 2015

davidcec-November 03, 2015

This two-part series addresses the use and misuse of two of the most essential synchronization primitives in modern embedded systems, the mutex (Part 1) and the semaphore (this article). Mutexes and semaphores are provided by most current RTOSs, although they can be implemented on bare-metal systems as well. Their use is considered a best practice among experienced firmware engineers, because they can make code more intuitive, leading to better maintainability, improved logic flow and higher productivity. If you’ve been using flags, variables and super loops to react to changes and control events in your code, skillful use of mutexes, semaphores and threads can improve your work.

Semaphores are analogous to the classic, but outdated, example of phone books. Suppose that you are in an office with just 10 phone books (and no Internet). If you want to place a call, you need a phone book to look up the number. The stack of phone books, not the phone books themselves, is the semaphore. If there are phone books available in the stack, you can “take” one. When you’re done with it, you “give” it back. If there are no phone books available, you must wait until someone returns one of them to the stack. This is how semaphores work, too. I like this example better than the usual example of bathrooms and keys, because the issue of which key works in which bathroom confuses the example.

Now that we’ve established at least one use-case for semaphores, recall that, unlike mutexes, semaphores incorporate a built-in counter (a signed integer) that is typically initialized to some value N, where N is usually ≥ 1. This is useful for representing a specific number of resources that are to be controlled/protected.

So, semaphores have two basic operations:

  1. take() – Adjusts the resource counter downward and, if necessary, waits until a resource becomes available. This operation has the potential to block the calling code if no resources are available.
  2. give() – Adjusts the resource counter upward and, if necessary, signals a waiting task that a resource has become available. This operation is typically non-blocking.

 

As with the mutex lock() and unlock() operations, the semaphore take() and give() operations should always happen in matched pairs (but they can be in either order – more on that later). Semantically speaking, take() could just as well be called wait or acquire or lock, and give() could be called signal or release or unlock.

The idea is that as long as a semaphore counter is non-negative (i.e., >0), there are still resources remaining to be take()-en. A resource could be anything that is shared – even a worker thread. Once the counter goes negative, however, tasks have to wait until at least one of the resources becomes available again.

Semaphores are generally used in two classes of problems:

  1. Coordinating access to multiple shared resources, across one or more processes.
  2. Signaling or triggering events between one or more processes.

 

The phone book example from above is a classic case of problem class #1. Class #2 is slightly less intuitive, but very, very useful for building event-driven systems, and it is our next topic.

Semaphores Are Also For Signaling
As described in Part 1, mutexes can be used to protect a single resource from two or more threads of execution. Semaphores differ in that they aren’t owned by a single process, and they feature a built-in counter so they’re ideal for protecting things that be counted, such as any kind of limited resource in a computer program. Semaphores, though, can also be used for signaling events! What kind of signals can a semaphore communicate? The kind that awaken other tasks, which turns out to be extremely useful.

Next page >

 

< Previous
Page 1 of 3
Next >

Loading comments...