Why is inter-task communication necessary?
Although multi-task systems theoretically allow tasks to run independently, it does not mean that tasks do not need any interaction with each other. On the contrary, more often than not, tasks need to exchange information with each other.
This includes but is not limited to the following scenarios:
-
Data transfer between tasks, for example, if Task A produces specific data, then Tasks B, C, and D need a channel to obtain the data produced by Task A.
-
Tasks need to execute in a specific order, for instance, Task B can only continue after Task A produces a certain condition, thus Task B must have a channel to perceive this condition. -
Tasks need to negotiate resource usage, for example, if Task A needs resource X, and Task B also needs resource X, but resource X can only be used by one task at a time, then A and B must have a channel to apply for exclusive use of this resource.
All these needs can be summarized in one sentence: tasks need to establish a set of mechanisms for mutual communication.
How to design inter-task communication
For the three scenarios mentioned above, how should we design inter-task communication? If we have never been exposed to any modern operating system theory, then using global variables is the easiest method to think of. After all, global variables can be shared between tasks, while local variables are only effective within the task processing function they belong to, and other tasks cannot see them.
If we have been exposed to modern operating system theory, we naturally understand some methods of inter-task communication, such as message queues, semaphores, and mutexes. When we look back, we may feel a subtle sensation: using global variables is a Stone Age method, too low-level.
This feeling is not surprising, but this article does not aim to debate personal viewpoints. My first job involved developing a game console on a 16-bit MCU, at a time when real-time operating systems were not as popular as they are now, and what we used was the traditional front-and-backend design. As a fresh graduate, my understanding of C language was still at the level of computer exams and completing assignments, and my knowledge of microcontrollers was merely at the level of turning on lights. So I never expected that such rich multimedia effects could be achieved on this 16-bit MCU through C language, nor did I expect that the front-and-backend system could also have such exquisite object-oriented design and event system design. The first year of work truly felt like an enlightening experience.
Back to the point, since multi-task operating systems create tasks, they must also create inter-task communication; otherwise, it would be an unfinished building.
Last week, I briefly talked about task scheduling in real-time systems (Task Scheduling from FreeRTOS). Two tasks are in different code execution paths, with independent stack spaces, scheduled by the scheduler. For two tasks to communicate, a medium is needed; what is this medium? The three main components of a computer: CPU, memory, and hard drive. CPU? It can only execute instructions. Hard drive? In embedded systems, this corresponds to Flash, which has a particularly slow access speed, especially for writing; using it to transmit information between tasks is a bit too heavy-handed. The only option left is memory. Yes, it is through memory that inter-task information transmission is accomplished.
Imagine that the operating system maintains a memory block that is visible to all tasks; when a task wants to communicate with other tasks, it places the information it wants to send into this memory block, and other tasks, if they want to know this information, can read from this memory block. If a task wants to respond to this information, it can also place the response in this memory block. This way, isn’t it possible for tasks to have a channel for exchanging information?
However, this design is clearly too crude. We need to consider the following issues:
1. If all tasks put things into this memory block, won’t it get chaotic?
2. When a task puts something into this memory block, does it want all tasks to know, or just a specific task?
3. If Task A and Task B have already agreed that there will be information exchange between them, how will they know when information is generated? Does the receiving party constantly query this memory block? If so, what is the appropriate query interval?
These questions are exactly what multi-task operating systems need to consider.
For the first question, we can design an abstract “channel” for information flow. Similar to a highway, it provides a “channel” for vehicles to travel. There can be more than one “channel,” and new channels can be created with unique identifiers. Programmers can help Task A and Task B agree in advance which “channel” to use for communication.
For the second question, since the “channel” has a unique identifier, if Task A and Task B have agreed in advance on which “channel” to use for communication, then a one-to-one relationship can be established. Of course, this one-to-one relationship is established during the programming phase. Because the “unique identifier” of the channel does not restrict any task from using it. If we want to solve this problem, it is not impossible; we could consider binding the “channel” to specific tasks when it is created. However, this is clearly a different new design, so we won’t digress.
For the third question, querying is unavoidable, but when this query finds no information, it is best to block the task, trigger task scheduling, and allow other tasks to execute. When other tasks generate information and find a task waiting for this information, it will also trigger task scheduling, allowing the blocked task to continue executing.
Thus, we have the prototype of the inter-task communication we envisioned. Next, let’s see how FreeRTOS actually does it.
Queues, Semaphores, and Mutexes in FreeRTOS
“Queues” are the main form of inter-task communication in FreeRTOS, used to send messages between tasks and between interrupts and tasks. As shown in the figure below (gif animation, please wait a moment), Task A sends multiple items to the queue in sequence, while Task B reads items from the queue in sequence.
What exactly are the items in the queue? — They can be any data structure. Note that these items are copied into the queue, so if the item is made up of a small data structure, it can be sent directly into the queue; if it consists of a large data structure, then a reference (pointer) to the item can be sent to the queue, as copying large amounts of data can affect efficiency.
An example code using the queue is as follows:
/* Define message structure */struct AMessage{ char ucMessageID; char ucData[ 20 ];} xMessage;/* Define a queue handle*/QueueHandle_t xStructQueue = NULL;void vCreateQueues( void ){ xMessage.ucMessageID = 0xab; memset( &( xMessage.ucData ), 0x12, 20 ); xStructQueue = xQueueCreate( /* The queue can hold 10 items. */ 10, /* The size of the item is the size of the xMessage structure*/ sizeof( xMessage ) );}/* Sending message task */void vATask( void *pvParameters ){struct AMessage *pxPointerToxMessage; /* Send message to xStructQueue queue */ xQueueSend( /* Queue handle */ xStructQueue, /* Address of the xMessage structure variable, the entire structure variable's value will be copied to the queue */ ( void * ) &xMessage, /* 0 indicates no blocking when the queue is full */ ( TickType_t ) 0 ); /* ... Rest of task code goes here. */}/* Receiving message task */void vADifferentTask( void *pvParameters ){struct AMessage xRxedStructure, *pxRxedPointer; if( xStructQueue != NULL ) { /* Receive message from xStructQueue queue, 10 indicates that when the queue is empty, it will block for 10 ticks waiting for the message to arrive */ if( xQueueReceive( xStructQueue, &( xRxedStructure ), ( TickType_t ) 10 ) == pdPASS ) { /* xRxedStructure now contains a copy of xMessage. */ } } /* ... Rest of task code goes here. */}Does this queue design look similar to our previous conception? Only more specific.
FreeRTOS’s semaphores and mutexes are also implemented based on queues.
Semaphores are divided into binary semaphores and counting semaphores. A binary semaphore can be viewed as a queue that can only hold one item, either “full” or “empty.” Tasks using binary semaphores do not care what is contained in the queue — they only want to know whether the queue is empty or full. Binary semaphores are typically used for synchronization between tasks.
Just as binary semaphores can be seen as queues of length 1, counting semaphores can be seen as queues of length greater than 1. Similarly, users of counting semaphores are not interested in the data stored in the queue; they only care whether the queue is empty.
Counting semaphores are typically used in two situations:
-
Event counting.
In this usage scenario, each time an event occurs, the event-generating program will “give” a semaphore (increasing the semaphore count), while the task processing the event will “take” a semaphore each time it processes an event (decreasing the semaphore count). Therefore, the count reflects the difference between the number of events that have occurred and the number of events that have been processed. In this case, the initial count value can be set to zero when creating the semaphore.
-
Resource management
In this usage scenario, the count reflects the number of available resources. To gain control of a resource, a task must first obtain a semaphore — simultaneously decreasing the semaphore count. When the count reaches zero, it indicates that no free resources are available. When a task finishes using a resource, it “returns” a semaphore — simultaneously increasing the semaphore count. In this case, the initial count value can be set to the maximum count value when creating the semaphore.
As for mutexes, they are very similar to binary semaphores. Binary semaphores are better at achieving synchronization, while mutexes help achieve simple mutual exclusion. Mutexes are binary semaphores that include a priority inheritance mechanism. If a high-priority task is blocked while trying to obtain a mutex currently held by a lower-priority task, the priority of the task holding the mutex will temporarily increase to that of the blocking task. This mechanism aims to ensure that high-priority tasks remain blocked for as short a time as possible, thus minimizing the occurrence of “priority inversion.”
Low-level implementation of queues
# Data carrying and management
When creating a queue, a segment of memory is requested from the system heap:
pxNewQueue = ( Queue_t * ) pvPortMalloc( sizeof( Queue_t ) + xQueueSizeInBytes );The queue structure defines pointers to the head of the storage area and the pointer to the free storage area:
int8_t * pcHead; /* Pointer to the head of the storage area */int8_t * pcWriteTo; /* Pointer to the free storage area */The queue structure defines the size of the items in the queue and the total number of items it can hold:
UBaseType_t uxLength; /* Total number of items, which is the capacity of the queue */UBaseType_t uxItemSize; /* Item size */volatile UBaseType_t uxMessagesWaiting; /* Current number of items in the queue */# Control over tasks
The queue structure defines two lists to record tasks that are blocked on the queue.
List_t xTasksWaitingToSend; /* List of tasks blocked on writing, sorted by task priority */List_t xTasksWaitingToReceive; /* List of tasks blocked on reading, sorted by task priority */When data is sent to the queue, if it finds that there are tasks blocked on the read list (because the queue is empty and cannot read data), it will unblock that task.
BaseType_t xQueueGenericSend( QueueHandle_t xQueue, const void * const pvItemToQueue, TickType_t xTicksToWait, const BaseType_t xCopyPosition ){ ... /* At this point, the queue has data and is no longer empty */ ... /* If there were tasks blocked while reading the queue, they can now be unblocked */ if( listLIST_IS_EMPTY( &( pxQueue->xTasksWaitingToReceive ) ) == pdFALSE ) { /* Schedule tasks, allowing the highest priority blocked task to run */ if( xTaskRemoveFromEventList( &( pxQueue->xTasksWaitingToReceive ) ) != pdFALSE ) { queueYIELD_IF_USING_PREEMPTION(); } ...Similarly, if it finds that the queue is full and cannot write data, it will block the task itself.
/* When writing data to the queue, if the queue is full */if( prvIsQueueFull( pxQueue ) != pdFALSE ){ /* Add the task to the blocked list */ vTaskPlaceOnEventList( &( pxQueue->xTasksWaitingToSend ), xTicksToWait );When receiving messages from the queue, if it finds that there are tasks blocked on the write list (because the queue is full and cannot write data), it will unblock that task.
BaseType_t xQueueReceive( QueueHandle_t xQueue, void * const pvBuffer, TickType_t xTicksToWait ){ ... /* At this point, the queue has free space and is no longer full */ ... /* If there were tasks blocked while writing to the queue, they can now be unblocked */ if( listLIST_IS_EMPTY( &( pxQueue->xTasksWaitingToSend ) ) == pdFALSE ) { /* Schedule tasks, allowing the highest priority blocked task to run */ if( xTaskRemoveFromEventList( &( pxQueue->xTasksWaitingToSend ) ) != pdFALSE ) { queueYIELD_IF_USING_PREEMPTION(); } ...Similarly, when it finds that the queue is empty, and it cannot read data, it will block the task itself.
/* When reading data from the queue, if the queue is empty */if( prvIsQueueEmpty( pxQueue ) != pdFALSE ){ /* Add the task to the blocked list */ vTaskPlaceOnEventList( &( pxQueue->xTasksWaitingToReceive ), xTicksToWait ); ...A fine horse cannot leap ten steps; a slow horse can drive ten times, and the effort lies in persistence. I hope this article can be of help to you.
— END —