Chapter 6 discusses activity synchronization of two or more threads of execution. Such synchronization helps tasks cooperate in order to produce an efficient real-time system. In many cases, however, task activity synchronization alone does not yield a sufficiently responsive application. Tasks must also be able to exchange messages. To facilitate inter-task data communication, kernels provide a message queue object and message queue management services.
This chapter discusses the following:
· defining message queues,
· message queue states,
· message queue content,
· typical message queue operations, and
· typical message queue use.
A message queue is a buffer-like object through which tasks and ISRs send and receive messages to communicate and synchornize with data. A message queue is like a pipeline. It temporarily holds messages from a sender until the intended receiver is ready to read them. This temporary buffering decouples a sending and receiving task; that is, it frees the tasks from having to send and receive messages simultaneously.
As with semaphore introduced in Chapter 6, a message queue has several associated components that the kernel uses to manage the queue. When a message queue is first created, it is assigned an associated queue control block (QCB), a message queue name, a unique ID, memory buffers, a queue length, a maximum message length, and one or more task-waiting lists, as illustrated in Figure 7.1.
Figure 7.1: A message queue, its associated parameters, and supporting data structures.
It is the kernel’s job to assign a unique ID to a message queue and to create its QCB and task-waiting list. The kernel also takes developer-supplied parameters-such as the length of the queue and the maximum message length-to determine how much memory is required for the message queue. After the kernel has this information, it allocates memory for the message queue from either a pool of system memory or some private memory space.
The message queue itself consists of a number of elements, each of which can hold a single message. The elements holding the first and last messages are called the head and tail respectively. Some elements of the queue may be empty (not containing a message). The total number of elements (empty or not) in the queue is the total length of the queue. The developer specified the queue length when the queue was created.
As Figure 7.1 shows, a message queue has two associated task-waiting lists. The receiving task-waiting list consists of tasks that wait on the queue when it is empty. The sending list consists of tasks that wait on the queue when it is full. Empty and full message-queue states, as well as other key concepts, are discussed in more detail next.
As with other kernel objects, message queues follow the logic of a simple FSM, as shown in Figure 7.2 When a message queue is first created, the FSM is in the empty state. If a task attempts to receive messages from this message queue while the queue is empty, the task blocks and, if it chooses to, is held on the message queue's task-waiting list, in either a FIFO or priority-based order.
Figure 7.2: The state diagram for a message queue.
In this scenario, if another task sends a message to the message queue, the message is delivered directly to the blocked task. The blocked task is then removed from the task-waiting list and moved to either the ready or the running state. The message queue in this case remains empty because it has successfully delivered the message.
If another message is sent to the same message queue and no tasks are waiting in the message queue's task-waiting list, the message queue's state becomes not empty.
As additional messages arrive at the queue, the queue eventually fills up until it has exhausted its free space. At this point, the number of messages in the queue is equal to the queue's length, and the message queue's state becomes full. While a message queue is in this state, any task sending messages to it will not be successful unless some other task first requests a message from that queue, thus freeing a queue element.
In some kernel implementations when a task attempts to send a message to a full message queue, the sending function returns an error code to that task. Other kernel implementations allow such a task to block, moving the blocked task into the sending task-waiting list, which is separate from the receiving task-waiting list.
Figure 7.3: Message copying and memory use for sending and receiving messages.
Message queues can be used to send and receive a variety of data. Some examples include:
· a temperature value from a sensor,
· a bitmap to draw on a display,
· a text message to print to an LCD,
· a keyboard event, and
· a data packet to send over the network.
Some of these messages can be quite long and may exceed the maximum message length, which is determined when the queue is created. (Maximum message length should not be confused with total queue length, which is the total number of messages the queue can hold.) One way to overcome the limit on message length is to send a pointer to the data, rather than the data itself. Even if a long message might fit into the queue, it is sometimes better to send a pointer instead in order to improve both performance and memory utilization.
When a task sends a message to another task, the message normally is copied twice, as shown in Figure 7.3 The first time, the message is copied when the message is sent from the sending task’s memory area to the message queue’s memory area. The second copy occurs when the message is copied from the message queue’s memory area to the receiving task’s memory area.
An exception to this situation is if the receiving task is already blocked waiting at the message queue. Depending on a kernel’s implementation, the message might be copied just once in this case-from the sending task’s memory area to the receiving task’s memory area, bypassing the copy to the message queue’s memory area.
Because copying data can be expensive in terms of performance and memory requirements, keep copying to a minimum in a real-time embedded system by keeping messages small or, if that is not feasible, by using a pointer instead.
Different kernels store message queues in different locations in memory. One kernel might use a system pool, in which the messages of all queues are stored in one large shared area of memory. Another kernel might use separate memory areas, called private buffers, for each message queue.
Using a system pool can be advantageous if it is certain that all message queues will never be filled to capacity at the same time. The advantage occurs because system pools typically save on memory use. The downside is that a message queue with large messages can easily use most of the pooled memory, not leaving enough memory for other message queues. Indications that this problem is occurring include a message queue that is not full that starts rejecting messages sent to it or a full message queue that continues to accept more messages.
Using private buffers, on the other hand, requires enough reserved memory area for the full capacity of every message queue that will be created. This approach clearly uses up more memory; however, it also ensures that messages do not get overwritten and that room is available for all messages, resulting in better reliability than the pool approach.
Typical message queue operations include the following:
· creating and deleting message queues,
· sending and receiving messages, and
· obtaining message queue information.
Message queues can be created and deleted by using two simple calls, as shown in Table 7.1.
Table 7.1: Message queue creation and deletion operations.
| Operation | Description |
|---|---|
| Create | Creates a message queue |
| Delete | Deletes a message queue |
When created, message queues are treated as global objects and are not owned by any particular task. Typically, the queue to be used by each group of tasks or ISRs is assigned in the design.
When creating a message queue, a developer needs to make some initial decisions about the length of the message queue, the maximum size of the messages it can handle, and the waiting order for tasks when they block on a message queue.
Deleting a message queue automatically unblocks waiting tasks. The blocking call in each of these tasks returns with an error. Messages that were queued are lost when the queue is deleted.
The most common uses for a message queue are sending and receiving messages. These operations are performed in different ways, some of which are listed in Table 7.2.
Table 7.2: Sending and receiving messages.
| Operation | Description |
|---|---|
| Send | Sends a message to a message queue |
| Receive | Receives a message from a message queue |
| Broadcast | Broadcasts messages |
When sending messages, a kernel typically fills a message queue from head to tail in FIFO order, as shown in Figure 7.4. Each new message is placed at the end of the queue.
Figure 7.4: Sending messages in FIFO or LIFO order.
Many message-queue implementations allow urgent messages to go straight to the head of the queue. If all arriving messages are urgent, they all go to the head of the queue, and the queuing order effectively becomes last-in/first-out (LIFO). Many message-queue implementations also allow ISRs to send messages to a message queue. In any case, messages are sent to a message queue in the following ways:
· not block (ISRs and tasks),
· block with a timeout (tasks only), and
· block forever (tasks only).
At times, messages must be sent without blocking the sender. If a message queue is already full, the send call returns with an error, and the task or ISR making the call continues executing. This type of approach to sending messages is the only way to send messages from ISRs, because ISRs cannot block.
Most times, however, the system should be designed so that a task will block if it attempts to send a message to a queue that is full. Setting the task to block either forever or for a specified timeout accomplishes this step. (Figure 7.5). The blocked task is placed in the message queue’s task-waiting list, which is set up in either FIFO or priority-based order.
Figure 7.5: FIFO and priority-based task-waiting lists.
In the case of a task set to block forever when sending a message, the task blocks until a message queue element becomes free (e.g., a receiving task takes a message out of the queue). In the case of a task set to block for a specified time, the task is unblocked if either a queue element becomes free or the timeout expires, in which case an error is returned.
As with sending messages, tasks can receive messages with different blocking policies-the same way as they send them-with a policy of not blocking, blocking with a timeout, or blocking forever. Note, however, that in this case, the blocking occurs due to the message queue being empty, and the receiving tasks wait in either a FIFO or prioritybased order. The diagram for the receiving tasks is similar to Figure 7.5, except that the blocked receiving tasks are what fills the task list.
For the message queue to become full, either the receiving task list must be empty or the rate at which messages are posted in the message queue must be greater than the rate at which messages are removed. Only when the message queue is full does the task-waiting list for sending tasks start to fill. Conversely, for the task-waiting list for receiving tasks to start to fill, the message queue must be empty.
Messages can be read from the head of a message queue in two different ways:
· destructive read, and
· non-destructive read.
In a destructive read, when a task successfully receives a message from a queue, the task permanently removes the message from the message queue’s storage buffer. In a non-destructive read, a receiving task peeks at the message at the head of the queue without removing it. Both ways of reading a message can be useful; however, not all kernel implementations support the non-destructive read.
Some kernels support additional ways of sending and receiving messages. One way is the example of peeking at a message. Other kernels allow broadcast messaging, explained later in this chapter.
Obtaining message queue information can be done from an application by using the operations listed in Table 7.3.
Table 7.3: Obtaining message queue information operations.
| Operation | Description |
|---|---|
| Show queue info | Gets information on a message queue |
| Show queue’s task-waiting list | Gets a list of tasks in the queue’s task-waiting list |
Different kernels allow developers to obtain different types of information about a message queue, including the message queue ID, the queuing order used for blocked tasks (FIFO or priority-based), and the number of messages queued. Some calls might even allow developers to get a full list of messages that have been queued up.
As with other calls that get information about a particular kernel object, be careful when using these calls. The information is dynamic and might have changed by the time it’s viewed. These types of calls should only be used for debugging purposes.
The following are typical ways to use message queues within an application:
· non-interlocked, one-way data communication,
· interlocked, one-way data communication,
· interlocked, two-way data communication, and
· broadcast communication.
Note that this is not an exhaustive list of the data communication patterns involving message queues. The following sections discuss each of these simple cases.
One of the simplest scenarios for message-based communications requires a sending task (also called the message source), a message queue, and a receiving task (also called a message sink), as illustrated in Figure 7.6.
Figure 7.6: Non-interlocked, one-way data communication.
This type of communication is also called non-interlocked (or loosely coupled), one-way data communication. The activities of tSourceTask and tSinkTask are not synchronized. TSourceTask simply sends a message; it does not require acknowledgement from tSinkTask.
The pseudo code for this scenario is provided in Listing 7.1.
Listing 7.1: Pseudo code for non-interlocked, one-way data communication.
tSourceTask () {
:
Send message to message queue
:
}
tSinkTask () {
:
Receive message from message queue
:
}
If tSinkTask is set to a higher priority, it runs first until it blocks on an empty message queue. As soon as tSourceTask sends the message to the queue, tSinkTask receives the message and starts to execute again.
If tSinkTask is set to a lower priority, tSourceTask fills the message queue with messages. Eventually, tSourceTask can be made to block when sending a message to a full message queue. This action makes tSinkTask wake up and start taking messages out of the message queue.
ISRs typically use non-interlocked, one-way communication. A task such as tSinkTask runs and waits on the message queue. When the hardware triggers an ISR to run, the ISR puts one or more messages into the message queue. After the ISR completes running, tSinkTask gets an opportunity to run (if it’s the highest-priority task) and takes the messages out of the message queue.
Remember, when ISRs send messages to the message queue, they must do so in a non-blocking way. If the message queue becomes full, any additional messages that the ISR sends to the message queue are lost.
In some designs, a sending task might require a handshake (acknowledgement) that the receiving task has been successful in receiving the message. This process is called interlocked communication, in which the sending task sends a message and waits to see if the message is received.
This requirement can be useful for reliable communications or task synchronization. For example, if the message for some reason is not received correctly, the sending task can resend it. Using interlocked communication can close a synchronization loop. To do so, you can construct a continuous loop in which sending and receiving tasks operate in lockstep with each other. An example of one-way, interlocked data communication is illustrated in Figure 7.7.
Figure 7.7: Interlocked, one-way data communication.
In this case, tSourceTask and tSinkTask use a binary semaphore initially set to 0 and a message queue with a length of 1 (also called a mailbox). tSourceTask sends the message to the message queue and blocks on the binary semaphore. tSinkTask receives the message and increments the binary semaphore. The semaphore that has just been made available wakes up tSourceTask. tSourceTask, which executes and posts another message into the message queue, blocking again afterward on the binary semaphore.
The pseudo code for interlocked, one-way data communication is provided in Listing 7.2.
The semaphore in this case acts as a simple synchronization object that ensures that tSourceTask and tSinkTask are in lockstep. This synchronization mechanism also acts as a simple acknowledgement to tSourceTask that it’s okay to send the next message.
Sometimes data must flow bidirectionally between tasks, which is called interlocked, two-way data communication (also called full-duplex or tightly coupled communication). This form of communication can be useful when designing a client/server-based system. A diagram is provided in Figure 7.8.
Figure 7.8: Interlocked, two-way data communication.
Listing 7.2: Pseudo code for interlocked, one-way data communication.
tSourceTask() {
:
Send message to message queue
Acquire binary semaphore
:
}
tSinkTask () {
:
Receive message from message queue
Give binary semaphore
:
}
In this case, tClientTask sends a request to tServerTask via a message queue. tServer-Task fulfills that request by sending a message back to tClientTask.
The pseudo code is provided in Listing 7.3.
Listing 7.3: Pseudo code for interlocked, two-way data communication.
tClientTask () {
:
Send a message to the requests queue
Wait for message from the server queue
:
}
tServerTask () {
:
Receive a message from the requests queue
Send a message to the client queue
:
}
Note that two separate message queues are required for full-duplex communication. If any kind of data needs to be exchanged, message queues are required; otherwise, a simple semaphore can be used to synchronize acknowledgement.
In the simple client/server example, tServerTask is typically set to a higher priority, allowing it to quickly fulfill client requests. If multiple clients need to be set up, all clients can use the client message queue to post requests, while tServerTask uses a separate message queue to fulfill the different clients’ requests.
Some message-queue implementations allow developers to broadcast a copy of the same message to multiple tasks, as shown in Figure 7.9.
Figure 7.9: Broadcasting messages.
Message broadcasting is a one-to-many-task relationship. tBroadcastTask sends the message on which multiple tSink-Task are waiting.
Pseudo code for broadcasting messages is provided in Listing 7.4.
Listing 7.4: Pseudo code for broadcasting messages.
tBroadcastTask () {
:
Send broadcast message to queue
:
}
Note: similar code for tSignalTasks 1, 2, and 3.
tSignalTask () {
:
Receive message on queue
:
}
In this scenario, tSinkTask 1, 2, and 3 have all made calls to block on the broadcast message queue, waiting for a message. When tBroadcastTask executes, it sends one message to the message queue, resulting in all three waiting tasks exiting the blocked state.
Note that not all message queue implementations might support the broadcasting facility. Refer to the RTOS manual to see what types of message-queue-management services and operations are supported.
Some points to remember include the following:
· Message queues are buffer-like kernel objects used for data communication and synchronization between two tasks or between an ISR and a task.
· Message queues have an associated message queue control block (QCB), a name, a unique ID, memory buffers, a message queue length, a maximum message length, and one or more task-waiting lists.
· The beginning and end of message queues are called the head and tail, respectively; each buffer that can hold one message is called a message-queue element.
· Message queues are empty when created, full when all message queue elements contain messages, and not empty when some elements are still available for holding new messages.
· Sending messages to full message queues can cause the sending task to block, and receiving messages from an empty message queue can cause a receiving task to block
· Tasks can send to and receive from message queues without blocking, via blocking with a timeout, or via blocking forever. An ISR can only send messages without blocking.
· The task-waiting list associated with a message-queue can release tasks (unblock them) in FIFO or priority-based order.When messages are sent from one task to another, the message is typically copied twice: once from the sending task’s memory area to the message queue’s and a second time from the message queue’s memory area to the task’s.
· The data itself can either be sent as the message or as a pointer to the data as the message. The first case is better suited for smaller messages, and the latter case is better suited for large messages.
· Common message-queue operations include creating and deleting message queues, sending to and receiving from message queues, and obtaining message queue information.
· Urgent messages are inserted at the head of the queue if urgent messages are supported by the message-queue implementation.
· Some common ways to use message queues for data based communication include non-interlocked and interlocked queues providing one-way or two-way data communication.