3.6. Queues
FreeRTOS allows tasks to communicate and synchronize with each other using queues. Interrupt service routines (ISRs) also use queues for communication and synchronization.
The basic queue data structure is:
typedef struct QueueDefinition
{
signed char *pcHead; /* Points to the beginning of the queue
storage area. */
signed char *pcTail; /* Points to the byte at the end of the
queue storage area. One more byte is
allocated than necessary to store the
queue items; this is used as a marker. */
signed char *pcWriteTo; /* Points to the free next place in the
storage area. */
signed char *pcReadFrom; /* Points to the last place that a queued
item was read from. */
xList xTasksWaitingToSend; /* List of tasks that are blocked waiting
to post onto this queue. Stored in
priority order. */
xList xTasksWaitingToReceive; /* List of tasks that are blocked waiting
to read from this queue. Stored in
priority order. */
volatile unsigned portBASE_TYPE uxMessagesWaiting; /* The number of items currently
in the queue. */
unsigned portBASE_TYPE uxLength; /* The length of the queue
defined as the number of
items it will hold, not the
number of bytes. */
unsigned portBASE_TYPE uxItemSize; /* The size of each items that
the queue will hold. */
} xQUEUE;
This is a fairly standard queue with head and tail pointers, as well as pointers to keep track of where we've just read from and written to.
When creating a queue, the user specifies the length of the queue and the size of each item to be tracked by the queue. pcHead and pcTail are used to keep track of the queue's internal storage. Adding an item into a queue does a deep copy of the item into the queue's internal storage.
FreeRTOS makes a deep copy instead of storing a pointer to the item because the lifetime of the item inserted may be much shorter than the lifetime of the queue. For instance, consider a queue of simple integers inserted and removed using local variables across several function calls. If the queue stored pointers to the integers' local variables, the pointers would be invalid as soon as the integers' local variables went out of scope and the local variables' memory was used for some new value.
The user chooses what to queue. The user can queue copies of items if the items are small, like in the simple integer example in the previous paragraph, or the user can queue pointers to the items if the items are large. Note that in both cases FreeRTOS does a deep copy: if the user chooses to queue copies of items then the queue stores a deep copy of each item; if the user chooses to queue pointers then the queue stores a deep copy of the pointer. Of course, if the user stores pointers in the queue then the user is responsible for managing the memory associated with the pointers. The queue doesn't care what data you're storing in it, it just needs to know the data's size.
FreeRTOS supports blocking and non-blocking queue insertions and removals. Non-blocking operations return immediately with a "Did the queue insertion work?" or "Did the queue removal work?" status. Blocking operations are specified with a timeout. A task can block indefinitely or for a limited amount of time.
A blocked task—call it Task A—will remain blocked as long as its insert/remove operation cannot complete and its timeout (if any) has not expired. If an interrupt or another task modifies the queue so that Task A's operation could complete, Task A will be unblocked. If Task A's queue operation is still possible by the time it actually runs then Task A will complete its queue operation and return "success". However, by the time Task A actually runs, it is possible that a higher-priority task or interrupt has performed yet another operation on the queue that prevents Task A from performing its operation. In this case Task A will check its timeout and either resume blocking if the timeout hasn't expired, or return with a queue operation "failed" status.
It's important to note that the rest of the system keeps going while a task is blocking on a queue; other tasks and interrupts continue to run. This way the blocked task doesn't waste CPU cycles that could be used productively by other tasks and interrupts.
FreeRTOS uses the xTasksWaitingToSend list to keep track of tasks that are blocking on inserting into a queue. Each time an element is removed from a queue the xTasksWaitingToSend list is checked. If a task is waiting in that list the task is unblocked.
Similarly, xTasksWaitingToReceive keeps track of tasks that are blocking on removing from a queue. Each time a new element is inserted into a queue the xTasksWaitingToReceive list is checked. If a task is waiting in that list the task is unblocked.
Semaphores and Mutexes
FreeRTOS uses its queues for communication between and within tasks. FreeRTOS also uses its queues to implement semaphores and mutexes.
What's The Difference?
Semaphores and mutexes may sound like the same thing, but they're not. FreeRTOS implements them similarly, but they're intended to be used in different ways. How should they be used differently? Embedded systems guru Michael Barr says it best in his article, "Mutexes and Semaphores Demystified":
The correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. By contrast, tasks that use semaphores either signal ["send" in FreeRTOS terms] or wait ["receive" in FreeRTOS terms] - not both.
A mutex is used to protect a shared resource. A task acquires a mutex, uses the shared resource, then releases the mutex. No task can acquire a mutex while the mutex is being held by another task. This guarantees that only one task is allowed to use a shared resource at a time.
Semaphores are used by one task to signal another task. To quote Barr's article:
For example, Task 1 may contain code to post (i.e., signal or increment) a particular semaphore when the "power" button is pressed and Task 2, which wakes the display, pends on that same semaphore. In this scenario, one task is the producer of the event signal; the other the consumer.
If you're at all in doubt about semaphores and mutexes, please check out Michael's article.
Implementation
FreeRTOS implements an N-element semaphore as a queue that can hold N items. It doesn't store any actual data for the queue items; the semaphore just cares how many queue entries are currently occupied, which is tracked in the queue's uxMessagesWaiting field. It's doing "pure synchronization", as the FreeRTOS header file semphr.h calls it. Therefore the queue has a item size of zero bytes (uxItemSize == 0). Each semaphore access increments or decrements the uxMessagesWaiting field; no item or data copying is needed.
Like a semaphore, a mutex is also implemented as a queue, but several of the xQUEUE struct fields are overloaded using #defines:
/* Effectively make a union out of the xQUEUE structure. */ #define uxQueueType pcHead #define pxMutexHolder pcTail
Since a mutex doesn't store any data in the queue, it doesn't need any internal storage, and so the pcHead and pcTail fields aren't needed. FreeRTOS sets the uxQueueType field (really the pcHead field) to 0 to note that this queue is being used for a mutex. FreeRTOS uses the overloaded pcTail fields to implement priority inheritance for mutexes.
In case you're not familiar with priority inheritance, I'll quote Michael Barr again to define it, this time from his article, "Introduction to Priority Inversion":
[Priority inheritance] mandates that a lower-priority task inherit the priority of any higher-priority task pending on a resource they share. This priority change should take place as soon as the high-priority task begins to pend; it should end when the resource is released.
FreeRTOS implements priority inheritance using the pxMutexHolder field (which is really just the overloaded-by-#define pcTail field). FreeRTOS records the task that holds a mutex in the pxMutexHolder field. When a higher-priority task is found to be waiting on a mutex currently taken by a lower-priority task, FreeRTOS "upgrades" the lower-priority task to the priority of the higher-priority task until the mutex is available again.