Counting Semaphores, Binary Semaphores and Mutexes explained

ChibiOS/RT, like other RTOSs, implements multiple synchronization primitives. Some primitives may appear similar and this can generate confusion when deciding which primitive is best suited for a given scenario.

Introduction

We will consider three synchronization mechanisms implemented in ChibiOS/RT:

  • Binary Semaphores.
  • Counting Semaphores.
  • Mutexes.

Note that other RTOSs may have implementation differences or even name them in a different way, there is not a standard about both terminology and exact behavior. Often the binary semaphore term is used as a synonym of mutex, this is not the case in ChibiOS/RT, there are fundamental differences as we will see.

Binary Semaphores

A binary semaphore is a synchronization object that can have only two states:

  • Not taken.
  • Taken.

Two operations are defined:

  • Take (chBSemWait() in ChibiOS/RT). Taking a binary semaphore brings it in the “taken” state, trying to take a semaphore that is already taken enters the invoking thread into a waiting queue.
  • Release (chBSemSignal() in ChibiOS/RT). Releasing a binary semaphore brings it in the “not taken” state if there are not queued threads. If there are queued threads then a thread is removed from the queue and resumed, the binary semaphore remains in the “taken” state. Releasing a semaphore that is already in its “not taken” state has no effect.

Binary Semaphores states diagram

Binary semaphores have no ownership attribute and can be released by any thread or interrupt handler regardless of who performed the last take operation. Because of this binary semaphores are often used to synchronize threads with external events implemented as ISRs, for example waiting for a packet from a network or waiting that a button is pressed.

Because there is no ownership concept a binary semaphore object can be created to be either in the “taken” or “not taken” state initially.

Counting Semaphores

A counting semaphore is a synchronization object that can have an arbitrarily large number of states. The internal state is defined by a signed integer variable, the counter. The counter value (N) has a precise meaning:

  • Negative, there are exactly -N threads queued on the semaphore.
  • Zero, no waiting threads, a wait operation would put in queue the invoking thread.
  • Positive, no waiting threads, a wait operation would not put in queue the invoking thread.

Two operations are defined for counting semaphores:

  • Wait (chSemWait() in ChibiOS/RT). This operation decreases the semaphore counter, if the result is negative then the invoking thread is queued.
  • Signal (chSemSignal() in ChibiOS/RT). This operation increases the semaphore counter, if the result is non-negative then a waiting thread is removed from the queue and resumed.

Counting Semaphores states diagram

Counting semaphores have no ownership attribute and can be signaled by any thread or interrupt handler regardless of who performed the last wait operation.

Because there is no ownership concept a counting semaphore object can be created with any initial counter value as long it is non-negative.

The counting semaphores are usually used as guards of resources available in a discrete quantity. For example the counter may represent the number of used slots into a circular queue, producer threads would “signal” the semaphores when inserting items in the queue, consumer threads would “wait” for an item to appear in queue, this would ensure that no consumer would be able to fetch an item from the queue if there are no items available. Note that this is exactly how I/O queues are implemented in ChibiOS/RT, very convenient.

Mutexes

A mutex is a synchronization object that can have only two states:

  • Not owned.
  • Owned.

Two operations are defined for mutexes:

  • Lock (chMtxLock() in ChibiOS/RT). This operation attempts to take ownership of a mutex, if the mutex is already owned by another thread then the invoking thread is queued.
  • Unlock (chMtxUnlock() in ChibiOS/RT). This operation relinquishes ownership of a mutex. If there are queued threads then a thread is removed from the queue and resumed, ownership is implicitly assigned to the thread.

Mutexes states diagram

Note that, unlike semaphores, mutexes do have owners. A mutex can be unlocked only by the thread that owns it, this precludes the use of mutexes from interrupt handles but enables the implementation of the Priority Inheritance protocol, most RTOSs implement this protocol in order to address the Priority Inversion problem. It must be said that few RTOSs implement this protocol fully (any number of threads and mutexes involved) and even less do that efficiently.

Mutexes have one single use, Mutual Exclusion, and are optimized for that. Semaphores can also handle mutual exclusion scenarios but are best used as a communication mechanism between threads or between ISRs and threads. Also see the following articles:

Comparison matrix

Features summary:

Feature Binary Semaphores Counter Semaphores Mutexes
Internal states 2 N 2
Use from ISRs yes yes no
Ownership no no yes
Priority Inheritance no*1 no*1 yes*2
Initialization either taken or not taken counter >= 0 always not owned
Queue organization*3 FIFO or priority FIFO or priority Priority
  1. In ChibiOS/RT if the option CH_USE_SEMAPHORES_PRIORITY is enabled then the semaphores queues are subject to reordering because priority inheritance triggered by a mutex operation.
  2. If implemented, ChibiOS/RT implements the Priority Inheritance protocol for any number of threads and mutexes.
  3. As implemented in ChibiOS/RT.

Notes regarding ChibiOS/RT

ChibiOS/RT extends the above mechanisms in several ways:

  • Both binary and counting semaphores have a “timeout” variant of the “wait” operation. This allows to terminate the wait if a semaphore is not signaled within a finite time. The timeout feature is especially useful when semaphores are used as an I/O synchronization primitive, most communication protocols require timeout handling.
  • Both binary and counting semaphores implement a “reset” operation that empties the waiting queue, all the waiting threads are resumed and the semaphore is reset to a known state.
  • Semaphore's “wait” operation returns an encoded message that allows to understand what happened:
    • RDY_OK, normal exit from a wait.
    • RDY_RESET, the semaphore has been reset while waiting.
    • RDY_TIMEOUT, timeout occurred while waiting.
  • The “unlock” operation on mutexes takes no parameters, ChibiOS/RT always unlocks caller's most recently locked mutex for efficiency and safe operations.
  • Mutexes implement also an “unlock all” operation that efficiently releases all the mutexes owned by the invoking thread.
  • Mutexes implement also an “try lock” operation that tries to lock a mutex but does not wait if the mutex is already owned by another thread.
  • Trying to lock a mutex that is already owned is a forbidden operation.
 
chibios/articles/semaphores_mutexes.txt · Last modified: 2012/06/05 19:49 by giovanni
 
Except where otherwise noted, content on this wiki is licensed under the following license:GNU Free Documentation License 1.3