As discussed in Part 1 in this series, we need to look closely at how the priorities of threads impact the total number of context switches performed by a system by examining two cases: "Case-1", in which all threads (4) are assigned the same priority, and execute round-robin fashion and "Case-2," where the four threads are assigned unique priorities of 1, 2, 3, and 4.

Threads A, B, and C check for a message from Thread D in their respective message queues. If one is found, they retrieve it. If not, they wait until one arrives. After retrieving a message from their queue, they return to look for another.

The threads are suspended (i.e., no longer ready to run) if no message is available in the queue, and resumed when a message appears (sent from thread D). At all times, the highest priority thread that is ready to run is made active.

In Case-1, where all threads have the same priority, the threads run in a round-robin fashion where each thread runs until it is blocked waiting for another message to appear in its queue. In Case-2, the highest priority thread that is ready to run always runs.

To show how priority assignment affects performance, we need to count the number of context switches that are performed in each case, between successive iterations of Thread D. This will represent one complete "Cycle" of the application in which three messages are sent to, and retrieved by, each of threads A, B, and C, as depicted in this simplified flow-diagram in Figure 3, below:

Figure 3 - Operational flow of example program, showing "cycles" consisting of Thread D sending messages to Threads A, B, and C and Threads A, B, and C retrieving those messages

The operational code for this simple system would look something like the following (Figure 4, below):

Figure 4 - Pseudo code for example program. Note that Threads A, B, and C continuously loop retrieving messages from Thread D. Thread D sends a number of messages to each of the other threads, then relinquishes.

Case-1: All threads have the same priority (A=4, B=4, C=4, D=4)
In Case-1, we've assigned each thread a priority of 4. When all threads have the same priority, they will run in a round-robin fashion, in the order of their creation (A, B, C, D). In Figure 5 below , this execution event trace shows how the example operates:

Figure 5 - Event trace of Case-1: Equal Priorities. This shows each of Threads A, B, and C retrieving three messages, then Thread D sending each Thread three more messages. This cycle is repeated continuously

("Click here to view expanded image.)

As you can see in Figure 5, Threads A, B, and C each read 3 messages from their message queues. The "QR" ( queue_read) event indicates a successful read of one message from the queue.

But, after 3 messages are retrieved, the queue is empty, and the threads are blocked until Thread D sends more messages. The "IS" (internal suspend) event indicates that the RTOS suspends the thread and returns to its scheduler which initiates a context switch. Thread D, the "producer" thread, eventually gets to run, and sends more messages to the queues (as shown by the "QS" event).

Note that as each of the first three messages is sent by Thread D (as indicated by the "QS" event), there is an Internal Resume ("IR") event. This IR event refers to the fact that the thread waiting for that message now may proceed, once it gets its next turn in the round-robin sequence.

After the third message is sent (one to each waiting thread), the subsequent messages do not cause another IR, since those threads already have been resumed by the first message, which has not yet been retrieved.

In this case, there is exactly one context switch each time a thread completes its processing (is blocked waiting for a message to be put on its queue, or is finished sending messages in the case of Thread D), allowing the next thread in turn to run. The result is that there are a total of four context switches per cycle between Thread D's nth and n+1 "relinquish" operations.

Note, in the event trace shown below in Figure 6 below, the two "RO" events indicating Thread D's Relinquish Operations as it completes sending messages, forming the Start and Stop boundaries of one application cycle.

Figure 6 - Context Switch count for Case-1. Notice that only four context switches are required for a complete cycle of nine messages sent and received. The insert shows the count of various RTOS operations

("Click here to view expanded image.)

Context switches between RO events are numbered, and the total (4) is computed by the "performance Statistics" display superimposed in the upper-right of Figure 6. In Case-1, nine messages are sent, nine messages are received, and four context switches occur.

Case-2: All threads are given unique priorities
In Case-2, each thread is assigned a unique priority. Thread A=1, Thread B=2, Thread C=3, and Thread D=4. Since all threads have unique priorities, the highest priority thread that is ready to run is the one that the RTOS will run. Figure 7 below shows the event sequence for Case-2:

Figure 7 - Processing flow in Case-2. Note that after each message is sent by Thread D in this case, a preemption occurs and control is immediately transferred to the thread waiting for that message.

("Click here to view expanded image.)

An interesting situation occurs when unique priorities are assigned. Here, as we can see in Figure 7, each message that is sent by Thread D causes an immediate Internal Resume ("IR" event), just as in Case-1. Because Thread A is waiting for a message, when Thread D sends a message to Thread A, it makes Thread A ready to run.

But, since Thread A has a higher priority than Thread D, it becomes the highest priority thread that is ready to run. As a result, the RTOS preempts Thread D and performs a context switch to Thread A (Context Switch #1 as shown in Figure 8 below). This is different from the events of Case-1, where Thread A had the same priority as Thread D, and no preemption was caused as Thread D sent its message to Thread A.

Once Thread A retrieves its message from the queue ("QR" event), it once again goes into a suspended state, waiting for another message (as indicated by the Internal Suspend, or "IS" event in Figure 8 below), and the RTOS does another context switch (Context Switch #2) back to Thread D. This is repeated for Threads B and C, resulting in Context Switches #3, #4, #5, and #6). The scenario is repeated three times, resulting in Context Switches 7 "18. This completes a "cycle" of the application (from one Thread D Relinquish to the next).

Figure 8 - Context Switches for a complete Cycle in Case-2. Note additional RTOS event counts shown in the insert.

("Click here to view expanded image.)

In Case-2, eighteen context switches occur for the same nine messages, an increase of 350% system overhead. The unique priority assignment strategy results in a significantly greater number of context switches compared to the assignment of the same priority.

This can be seen between the two "RO" (Relinquish Operation) events noted in Figure 8, compared to the previous case where only four context switches occur.

Figure 9 - When tasks are assigned unique priorities, 350% more context switches occurred, resulting in a significantly less efficient system.

As noted in Figure 9 above, through the selection of thread priorities, the exact same application can have almost five times the number of context switches than it would have under optimal priority conditions.

Next in Part 3, we will look at the implications introduced by the use of unique priorities especially as regards the additional RTOS overhead that is imposed.

To read Part 1, go to: "The basics of context switching."

William E. Lamie is co-founder and CEO of Express Logic, Inc., and is the author of the ThreadX RTOS. Prior to founding Express Logic, Mr. Lamie was the author of the Nucleus RTOS and co-founder of Accelerated Technology, Inc. Mr. Lamie has over 20 years experience in embedded systems development, over 15 of which are in the development of real-time operating systems for embedded applications.