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.