Queues, Semaphores, and Mutexes

The puzzle

The sensor task must tell the logger that a reading is ready; two tasks share one I²C bus; four DMA buffers are handed out to whoever needs one; an interrupt wakes a task when a packet arrives. An RTOS offers semaphores, mutexes, queues and notifications, and at first sight any of them seems to do any of these jobs. Most combinations even work in testing. Which one is right, and what goes wrong with the others?

STEP 1

Blocking instead of polling

In the main loop of unit 9, a task that waits for an interrupt polls a flag on every pass. With an RTOS, a task instead blocks on a kernel object: it calls “take” or “receive”, and if nothing is available the scheduler marks it blocked and runs something else. A blocked task uses no CPU time. When a handler or another task gives the semaphore or sends to the queue, the waiting task becomes ready and, if it is the most urgent, runs at once (lesson 3).

Every blocking call takes a timeout. FreeRTOS counts it in ticks (pdMS_TO_TICKS() converts); zero means “do not wait”, and portMAX_DELAY means wait for ever (when INCLUDE_vTaskSuspend is enabled). A timeout turns “the bus is stuck” into a return value the code can handle, instead of a task that silently never runs again.

STEP 2

Semaphores: signals and counts

A semaphore is a counter with two operations: give adds one, take subtracts one, or blocks while the count is zero.

A binary semaphore counts only to one. It is a signal: an interrupt handler gives it (xSemaphoreGiveFromISR()), the task takes it and blocks until then. Several gives before the task runs merge into one. FreeRTOS creates it empty, so it must be given before the first take succeeds.
A counting semaphore counts up to a maximum. It can count events so none are merged, or count free resources: initialise it to the number of buffers, take one to claim a buffer, give it back to release. The pico-sdk calls the count “permits”.

Nobody owns a semaphore: any task or handler may give it. That is exactly what signalling needs, and exactly what mutual exclusion does not.

STEP 3

Mutexes: ownership and priority inheritance

A mutex protects a resource that only one task may use at a time. Unlike a semaphore it has an owner, the task that took it, and that task must give it back. The kernel uses that ownership: while a more urgent task waits for the mutex, the owner temporarily runs at the waiter’s priority (priority inheritance, lesson 5), so the owner finishes and releases sooner.

Ownership also rules out interrupt handlers: a handler cannot block, and it is not a task that can own anything or inherit a priority. FreeRTOS states that mutexes “cannot be used from within interrupt service routines”; Zephyr’s mutexes are “not designed for use by ISRs”; the pico-sdk calls blocking mutex functions in a handler “generally a bad idea”. A recursive mutex can be taken again by its owner (and must be given back as many times); an ordinary one taken twice by the same task waits for itself: a deadlock, as the pico-sdk warns (or, with a timeout, a failure).

↑ This step uses the figure at the top of the page.

Hold a mutex for as short a time as possible, and never block on something else while holding it without thinking about lesson 5.

STEP 4

Queues: pass the data itself

A queue holds a fixed number of fixed-size items. Items are copied in and out: the sender can reuse its variable as soon as the send returns, and the receiver gets its own copy. Sending blocks while the queue is full (up to the timeout); receiving blocks while it is empty. xQueueSendFromISR() lets a handler send without blocking. A queue does the work of a ring buffer (unit 9, lesson 5), a counting semaphore and a lock in one object, which is why it is often the first choice between tasks.

A queue also enables the gatekeeper pattern: one task owns a resource (a UART, a display) and every other task sends it requests, so no lock is needed at all.

Task notifications in FreeRTOS are a lighter alternative when exactly one task is the receiver: each task has notification values that another task or a handler can set, increment or overwrite, and the task can block until one arrives. FreeRTOS describes them as usable as “light weight and fast binary or counting semaphores”.

STEP 5

When the queue is full

A burst of items can arrive faster than the receiver handles them. The queue absorbs the difference; if the burst is longer than the queue, the sender must either wait or give up.

INTERACTIVEA full queue: block the sender or lose the item

Queue length

Logger needs per item

When full, the sender

Readings in the burst 20

Peak 8 of 8; 2 lost.

A sensor task sends one reading per millisecond into a queue; a lower-priority logger task takes each reading out and needs a few milliseconds to write it. While the burst lasts the queue fills. When it is full, a send with a timeout blocks the sensor task until the logger makes room (nothing is lost, but the sensor task falls behind its schedule); a send with zero timeout returns “queue full” at once and the reading is dropped.

For a burst of $N$ items arriving at rate $r_{\text{in}}$ while the receiver drains at $r_{\text{out}} < r_{\text{in}}$ , the queue fills by about

Q_{\text{peak}} \approx N \left(1 - \frac{r_{\text{out}}}{r_{\text{in}}}\right)

With a timeout, a full queue pushes the delay back into the sender: fine for a logging task, harmful for a sampling task with its own deadline. With a zero timeout the send fails at once and the data is lost: keep a counter of failed sends so the loss is visible.

STEP 6

Critical sections

For a few instructions of shared data, a mutex is heavy. An RTOS critical section (taskENTER_CRITICAL() in FreeRTOS) masks interrupts, and with them task switches; on the Cortex-M0+ port it executes cpsid i, masking all of them, and keeps a nesting count, so it only re-enables interrupts when the outermost section ends. On the dual-core RP2040 SMP port, masking one core does not stop the other, so its critical sections also take a hardware spin lock. Use it for a few microseconds, like the critical sections of unit 9; use a mutex when the protected work is long or may block.

STEP 7

Worked example: sizing the reading queue

A sensor task sends 20 readings, one per millisecond; the logger needs 2 ms to write each one and has a lower priority. The logger takes a reading out of the queue when it starts on it, so over the 20 ms burst it removes about 10 of them, and the rest wait:

Q_{\text{peak}} \approx 20 \times \left(1 - \frac{0.5\ \text{ms}^{-1}}{1\ \text{ms}^{-1}}\right) = 10

The simulation agrees: the queue peaks at 10 items. A queue of 8 with a zero timeout loses 2 readings; with a timeout nothing is lost, but the sensor task is blocked and sends its last readings up to 3 ms late. A queue of 16 absorbs the burst either way. Whenever nothing is lost, the logger finishes the last reading 40 ms after the burst started, whatever the queue length: the length changes who waits and what is lost, not the total work.

MYTHS AND FACTS

Common misconceptions

A mutex is just a binary semaphore

A mutex has an owner and priority inheritance; a binary semaphore has neither, which makes it right for signalling and wrong for locking.

Queues pass pointers

FreeRTOS and pico-sdk queues copy the item; to pass a large buffer, queue a pointer to it and agree who owns the buffer.

Wait for ever is the safe timeout

It hides failures; a finite timeout gives the code a chance to report and recover.

A handler can take the mutex briefly

It cannot block, own a mutex or inherit a priority: signal a task with a semaphore, queue or notification instead.

Check yourself

Answer in your head, then open the card.

A UART handler gives a binary semaphore for every byte received, and the task takes it and reads one byte from a ring buffer. Bytes are sometimes left unread. Why, and what are two fixes?

Several gives before the task runs merge into one take, so the task reads one byte per wake-up. Either read everything available on each wake-up, or use a counting semaphore (or a queue of bytes) so each event is counted.

Why does FreeRTOS forbid taking a mutex in an interrupt handler?

A mutex has an owner that may have to wait and may inherit a priority; a handler cannot block and is not a task, so neither ownership nor inheritance can work.

A burst of 30 items arrives at 1 per ms, and the receiver handles one every 3 ms. About how many queue slots avoid any loss?

About 30 × (1 − 1/3) = 20 slots.

Four tasks share a pool of three identical radio buffers. Which primitive counts them, and what else is needed?

A counting semaphore initialised to 3 (or a queue holding pointers to the three free buffers). With the semaphore, picking which buffer to use still needs a short critical section or a free list; the queue hands out the buffer itself.

Sources (5)

FreeRTOS Kernel, include/semphr.h — binary semaphores are queues of length 1 with no data, for “pure synchronisation between tasks or between an interrupt and a task … For this reason this type of semaphore does not use a priority inheritance mechanism”; xSemaphoreCreateBinary() creates it so that it “must first be 'given' before it can be 'taken'”; xSemaphoreCreateMutex(): “This type of semaphore uses a priority inheritance mechanism so a task 'taking' a semaphore MUST ALWAYS 'give' the semaphore back … Mutex type semaphores cannot be used from within interrupt service routines”; “it is faster and more memory efficient to use a direct to task notification in place of a binary semaphore” in many scenarios; “A block time of portMAX_DELAY can be used to block indefinitely (provided INCLUDE_vTaskSuspend is set to 1 in FreeRTOSConfig.h)”
FreeRTOS Kernel, include/queue.h and include/task.h (task notifications) — “Items are queued by copy, not by reference”; xTicksToWait: “The call will return immediately if this is set to 0 and the queue is full”; notifications “can be used to send data to a task, or be used as light weight and fast binary or counting semaphores”; eSetValueWithOverwrite sets the value “even if the previous value has not yet been read”, eSetValueWithoutOverwrite only “if the previous value has been read”; a blocked task “does not consume any CPU time”
Raspberry Pi Ltd, pico-sdk 1.5.1, pico_sync/include/pico/mutex.h and sem.h — mutex_t “is a regular mutex that cannot be acquired recursively by the same owner (a deadlock will occur if you try)”; recursive_mutex_t can; “It is generally a bad idea to call blocking mutex_ or recursive_mutex_ functions from within an IRQ handler”; sem.h: a semaphore “holds a number of available permits”, capped at max_permits, and it is “preferable to only release semaphores from within an IRQ handler (i.e. avoid blocking)”
Zephyr Project documentation, doc/kernel/services/synchronization/mutexes.rst — a mutex has “A lock count” and “An owning thread”; it is reentrant; “it is considered good practice to hold the lock for as short a time as possible”; “Mutex objects are not designed for use by ISRs”; the owner is eligible for priority inheritance
FreeRTOS Kernel, portable/GCC/ARM_CM0/port.c and portmacro.h (critical sections) — vPortEnterCritical(): portDISABLE_INTERRUPTS() (cpsid i) and ulCriticalNesting++; vPortExitCritical() re-enables interrupts only when the nesting count returns to 0