RT Semaphores

Semaphores are one of the most common features found in embedded RTOSes, of course there are differences in implementation and details.
ChibiOS/RT implements two variants of semaphores:

  • Counting Semaphores.
  • Binary Semaphores.

The user can use both types without restrictions.

Global Settings

Semaphores are affected by the following global settings:

CH_CFG_USE_SEMAPHORES This switch enables the semaphores API in the kernel (both counting and binary semaphores).
CH_CFG_USE_SEMAPHORES_PRIORITY If enabled then threads are queued by priority rather than in FIFO order on semaphores. The default is disabled.

Counting Semaphores

The counting semaphores have been first formalized by the Dutch computer scientist Edsger W. Dijkstra in 1965. Counting semaphores have an internal signed counter variable, the value of the variable is the semaphore internal state. The meaning of the counter is:

  • N < 0. The semaphore is taken and there are -N threads queued.
  • N == 0. The semaphore is taken but there are no threads queued.
  • N > 0. The semaphore is not taken and can be taken N times.

Basically the counter of a semaphore can guard a resource available in finite quantity.

Counting semaphores are regulated by the following state diagram:

Counting Semaphore States

Extensions

ChibiOS/RT implements an extended version of the Dijkstra semaphores, there are several enhancements over the initial definition:

  • Reset Operation. In addition to the classic Wait and Signal operations a new Reset operation has been added. This operation is able to reset a semaphore counter to any non-negative value, all waiting threads are dequeued, if any.
  • Timeouts. The Wait operation has an optional timeout parameter, a queued thread is able to be dequeued if a Signal or Reset is not performed within the specified time interval.
  • Message. The Wait operation returns a message code indicating the way the thread has been signaled:
    • MSG_OK. The thread has taken the resource normally.
    • MSG_RESET. The thread was queued and a Reset operation has been performed on the semaphore.
    • MSG_TIMEOUT. The thread was queued and a timeout occurred.
  • Atomic Signal and Wait. A Signal operation is performed on a semaphore and a Wait operation is performed on another semaphore atomically.

API

SEMAPHORE_DECL() Semaphore static initializer.
chSemObjectInit() Initializes a semaphore object of type semaphore_t.
chSemWait() Performs a Wait operation on the semaphore.
chSemWaitS() Performs a Wait operation on the semaphore (S-Class variant).
chSemWaitTimeout() Performs a Wait operation on the semaphore with timeout specification.
chSemWaitTimeoutS() Performs a Wait operation on the semaphore with timeout specification (S-Class variant).
chSemSignal() Performs a Signal operation on the semaphore.
chSemSignalI() Performs a Signal operation on the semaphore (I-Class variant).
chSemReset() Performs a Reset operation on the semaphore.
chSemResetI() Performs a Reset operation on the semaphore (I-Class variant).
chSemAddCounterI() Adds a constant to the semaphore counter, threads are dequeued as required (I-Class variant).
chSemSignalWait() Atomically performs a Signal on a semaphore and a Wait on another semaphore.
chSemGetCounterI() Returns the current value of the semaphore counter (I-Class variant).
chSemFastWaitI() Ultrafast version of Wait usable in those conditions where the counter is known to be greater than zero, it is a pure decrement (I-Class variant).
chSemFastSignalI() Ultrafast version of Signal usable in those conditions where the counter is known to be non-negative, it is a pure increment (I-Class variant).

Examples

Resources Allocator

Imagine having a finite set of resources, DMA channels for example, and wanting to implement an allocator of said DMA channels for use by device drivers. Each driver would:

  1. Allocate a channel.
  2. Perform the operation.
  3. Release the channel.

The problem is that there are more driver than channel and we don't want the operation to fail, so drivers will have to queue if a channel is not immediately available.

#define DMA_NUM_CHANNELS 16
 
static semaphore_t dmasem;
 
/*
 * Allocates a DMA channel. Users are supposed to use the channel and
 * then release it in a finite time.
 */
channel_t dmaAllocateChannel(void) {
 
  msg_t msg = chSemWaitTimeout(&dmasem, MS2ST(500));
  if (msg == MSG_TIMEOUT)
    panic("unreleased DMA channels";
 
  /* Get a channel from the pool, the semaphores guarantees there is at
     least one.*/
  return dma_get_channel();
}
 
/*
 * Returns a channel to the pool after use.
 */
void dmaReleaseChannel(channel_t channel) {
 
  /* Returning the channel to the pool.*/
  dma_return_channel(channel);
 
  /* Then signaling the sempaphore.*/
  chSemSignal(&dmasem);
}
 
/*
 * Initialization.
 */
void main(void) {
 
  /*
   * System initializations.
   * - Kernel initialization, the main() function becomes a thread and the
   *   RTOS is active.
   */
  chSysInit();
 
  /* Initializing the DMA semaphore to allow up to DMA_NUM_CHANNELS
     allocations.*/
  chSemObjectInit(&dmasem, DMA_CHANNELS);
 
  /* Continuing.*/
  ...;
}

Binary Semaphores

In ChibiOS/RT binary semaphores are built on counting semaphores using very efficient inline code. The counter of binary semaphores is not allowed to count beyond one thus the semaphore has only two possible states:

  • Taken, when its counter has a value of zero or lower than zero. A negative number represent the number of threads queued on the binary semaphore.
  • Not Taken, when its counter has a value of one.

Binary semaphores are regulated by the following state diagram:

 Binary Semaphore States

Extensions

ChibiOS/RT implements an extended version of the binary semaphores, there are several enhancements over the usual definition:

  • Reset Operation. In addition to the classic Wait and Signal operations a new Reset operation has been added. This operation is able to reset a semaphore state to either “taken” or “not taken”, all waiting threads are dequeued, if any.
  • Timeouts. The Wait operation has an optional timeout parameter, a queued thread is able to be dequeued if a Signal or Reset is not performed within the specified time interval.
  • Message. The Wait operation returns a message code indicating the way the thread has been signaled:
    • MSG_OK. The thread has taken the resource normally.
    • MSG_RESET. The thread was queued and a Reset operation has been performed on the semaphore.
    • MSG_TIMEOUT. The thread was queued and a timeout occurred.

API

BSEMAPHORE_DECL() Semaphore static initializer.
chBSemObjectInit() Initializes a semaphore object of type semaphore_t.
chBSemWait() Performs a Wait operation on the semaphore.
chBSemWaitS() Performs a Wait operation on the semaphore (S-Class variant).
chBSemWaitTimeout() Performs a Wait operation on the semaphore with timeout specification.
chBSemWaitTimeoutS() Performs a Wait operation on the semaphore with timeout specification (S-Class variant).
chBSemSignal() Performs a Signal operation on the semaphore.
chBSemSignalI() Performs a Signal operation on the semaphore (I-Class variant).
chBSemReset() Performs a Reset operation on the semaphore.
chBSemResetI() Performs a Reset operation on the semaphore (I-Class variant).
chBSemGetStateI() Return true if the semaphore is taken (I-Class variant).

Examples

Thread Serving an IRQ

/*
 * Synchronization semaphore.
 */
binary_semaphore_t uart_bsem;
 
/*
 * ISR serving the UART RX FIFO interrupt.
 */
CH_IRQ_HANDLER(UART_RX_IRQ) {
 
  CH_IRQ_PROLOGUE();
 
  /* If there is data available in the UART RX FIFO.*/
  if ((UART->SR & UART_SR_DATA_AVAILABLE) != 0) {
 
    /* Entering I-Locked state and signaling the semaphore.*/
    chSysLockFromISR();
    chBSemSignalI(&uart_bsem);
    chSysUnlockFromISR();
 
    /* Resetting interrupt source.*/
    UART->SR &= ~UART_SR_DATA_AVAILABLE;
  }
 
  CH_IRQ_EPILOGUE();
}
 
/*
 * IRQ serving thread, communication timeouts are handled.
 */
static THD_WORKING_AREA(waUartReceiveThread, 128);
static THD_FUNCTION(UartReceiveThread, arg) {
 
  while (true) {
    /* Waiting for an interrupt. If the interrupt has already occurred
       then the thread will not stop into chBSemWaitTimeout() because
       the binary semaphore would be in the "not taken" state.
       A 500mS timeout is programmed.*/
    msg_t msg = chBSemWaitTimeout(&uart_bsem, MS2ST(500));
 
    /* If a communication timeout occurred then some special handling
       is required.*/
    if (msg == MSG_TIMEOUT) {
      handle_comm_timeout();
      continue;
    }
 
    /* Empties the UART RX FIFO and processes all data before attempting
       taking the semaphore again.*/
    while ((UART->SR & UART_SR_RXFIFO_CNT) > 0) {
       process_data(UART->DR);
    }
  }
}
 
/*
 * Initialization.
 */
void main(void) {
 
  /*
   * System initializations.
   * - Kernel initialization, the main() function becomes a thread and the
   *   RTOS is active.
   */
  chSysInit();
 
  /* Initializing the UART semaphore in the "taken" state then starting
     the communication.*/
  chBSemObjectInit(&uart_bsem, true);
  uart_init();
 
  /* Starting the UART thread.*/
  chThdCreateStatic(waUartReceiveThread, sizeof(waUartReceiveThread),
                    NORMALPRIO + 1, UartReceiveThread, NULL);
 
  /* Continuing.*/
  ...;
}

Note that a counter semaphore should not used like in this example because the counter would count up after each interrupt and it could overflow if not decremented fast enough by the thread. The binary semaphore is safe because there is only a single “not taken” state, multiple signaling has no effect.