Thread Scheduling

Depending on the current environment, an RTSS thread state might be waiting (i.e. for an event, resource, or amount of time), ready-to-run, or running. The scheduler uses priority levels to determine which ready-to-run thread will be allowed to run next. On a dedicated configuration, each RTSS processor has its own ready queue.

Priority Levels

The RTSS environment provides thread priority levels RT_PRIORITY_MIN (0) though RT_PRIORITY_MAX (127). A thread's priority level can be set using RtSetThreadPriority (hThread, level) where level can be RT_PRIORITY_MIN, RT_PRIORITY_MIN + 1, RT_PRIORITY_MIN + 2... RT_PRIORITY_MAX.

Example Application Environment

To illustrate how threads move in and out of the run state on a single processor, an application with three threads will be used. This example application environment includes:

Thread Th1, performing a critical task, at high priority level RT_MIN + 60
Thread Th2, performing an important task, at medium priority level RT_MIN + 40
Thread Th3, performing a maintenance task at low priority level RT_MIN + 20

In a simple environment, with no shared resources, any time that the highest priority thread Th1 is ready-to-run, it will be allowed to execute. When thread Th1 has completed its task, the next highest priority ready-to-run thread will be allowed to execute.

Priority Inversion

In a shared resource environment, two or more threads, such as Th1 and Th3, may need to share a single resource, whose access is controlled by mutex M1. In cases where a low priority thread has ownership of the shared resource that a high priority thread needs, the high priority thread will be blocked until the low priority thread has released the resource. This is called priority inversion since the relative priorities of the threads are effectively inverted.

The execution delay experienced by a critical thread in a priority inversion situation can be exacerbated if some other medium priority thread, which does not depend on the shared resource, takes precedence over the low priority thread. Until the low priority thread is allowed to run, the shared resource will not be released. This is illustrated as follows:

A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU. Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
An important (medium priority 30) thread Th2 becomes ready-to-run. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
A critical (high priority 60) thread Th1 becomes ready-to-run. Thread Th2 is returned to a ready-to-run state and thread Th1 begins to run.
Thread Th1 requests ownership of mutex M1 (by calling either RtWaitForSingleObject or RtWaitForMultipleObjects).
Since mutex M1 is currently owned by thread Th3, and not available, thread Th1 enters a wait state
The highest priority ready-to-run thread (which is now Th2) is started and runs until completion.
Thread Th3 is moved from a ready-to-run state, completes its use of the resource, and releases mutex M1.
Thread Th1 acquires mutex M1 and runs until completion.
When no higher priority threads are ready-to-run, thread Th3 is allowed to run again.

Priority Inversion Protocols

Even when developers carefully manage the use of shared resources, there may still be situations where priority inversion can arise and impact application behavior. Because of this, the RTX scheduler provides three system behavior options to minimize priority inversion:

Priority Promotion with Tiered Demotion - Elevates a low priority thread to the level of the highest priority thread that is waiting for the shared mutex. When the promoted thread has released the mutex requested by a higher priority thread, it is demoted to its native priority level, allowing the higher priority blocked thread to acquire the mutex and to run.
Priority Promotion with Limited Demotion - Elevates a low priority thread to the level of the highest priority thread that is waiting for the shared mutex. When the promoted thread has released all mutexes that it owns, it is demoted to its native priority level, allowing the higher priority blocked thread to acquire the mutex and to run.
Disable - Does not elevate priorities in cases where a higher priority thread is waiting on a mutex held by a lower priority thread.

Prior to RTX 2009 Service Pack 1, the only system behavior option available was Priority Promotion with Limited Demotion.

Priority Promotion with Tiered Demotion

When RTX priority promotion with tiered demotion is implemented, a lower-priority thread that owns a mutex needed by a higher priority thread will have its priority temporarily promoted to that of the high priority waiting thread until it has released the requested mutex.

This tiered implementation uses an internal mutex priority to keep track of priority promotion causing mutexes. On each call to RtReleaseMutex the thread’s priority will be checked to see if its priority can be demoted based on the internal priorities of the remaining mutexes held. This tiered demotion allows promoted priorities to be demoted as soon as possible, promoting threads only as high as necessary based on higher priority waiting threads. Because of the additional demotion checking, there is a small overhead cost with this protocol that is not present with limited or disabled demotion.

Priority promotion with tiered demotion in a scenario where two different priority threads share a resource controlled by a mutex is illustrated as follows:

A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU.Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
An important (medium priority 30) thread Th2 becomes ready-to-run. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
A critical (high priority 60) thread Th1 becomes ready-to-run. Thread Th2 is returned to a ready-to-run state and thread Th1 begins to run.
Th1 performs some work and then requests ownership of mutex M1.
When thread Th1 requests mutex M1 with a call to either RtWaitForSingleObject or RtWaitForMultipleObjects, the owner of mutex M1 (which is thread Th3) is promoted to the priority of the requesting thread (priority 60).
Thread Th3, now ready-to-run at priority 60, runs until it has finished using the shared resource and releases mutex M1. After calling RtReleaseMutex, thread Th3 returns to its native priority (priority 20).
Thread Th1 acquires mutex M1 and, as the highest priority ready-to-run thread, is able to run to completion.

NOTE: With tiered demotion, ownership of additional mutexes will not prevent thread Th3 from being returned to its native priority level after it has released the mutex that higher priority thread Th1 is waiting to acquire.

Priority promotion with tiered demotion in a scenario where a low priority thread has ownership of a single mutex that is needed by two higher priority threads, is illustrated as follows:

A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU.Thread Th3 begins by waiting for (RtWaitForSingleObject) and then acquiring ownership of mutex M1.
An important (medium priority 30) thread Th2 becomes ready-to-run, preempts thread Th3 and calls RtWaitForSingleObject or RtWaitForMultipleObjects, requesting ownership of mutex M1. Since the mutex is unavailable, thread Th2 goes into a wait state.
As a result of Thread Th2's call to RtWaitForSingleObject or RtWaitForMultipleObjects, thread Th3 is promoted to the priority (30) of thread Th2.
A critical (high priority 20) thread Th1 becomes ready-to-run, preempts thread Th3 and calls RtWaitForSingleObject or RtWaitForMultipleObjects, requesting ownership of mutex M1. Since the mutex is unavailable, thread Th1 goes into a wait state
As a result of Thread Th1's call to RtWaitForSingleObject or RtWaitForMultipleObjects, thread Th3 is promoted to the priority (60) of thread Th1.
Thread Th3 completes its use of the shared resource and releases ownership of mutex M1. As a result of its call to RtReleaseMutex, thread Th3 is demoted back to its native priority (20).
Thread Th1 runs until completion (releasing mutex M1).
Thread Th2 runs until completion (releasing mutex M1).
Thread Th3 runs until completion.

Priority Promotion with Limited Demotion

When RTX priority promotion with limited demotion is implemented, a lower-priority thread that owns a mutex needed by a higher priority thread will have its priority promoted until it has completed its use of all mutexes that it owns.

Limited demotion logic does not keep track of which mutex caused a thread’s priority to be promoted, it just keeps track that a promotion has occurred. This is done to reduce the overhead of checking for possible demotion on each RtReleaseMutex call. Because no tracking occurs if multiple mutexes are held by a promoted thread, that thread’s priority will not be demoted until all held mutexes are released.

This is illustrated as follows:

A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU. Thread Th3 begins by waiting for (RtWaitForMultipleObjects) and then acquiring ownership of mutexes M1 and M2.
An important (medium priority 30) thread Th2 becomes ready-to-run. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
A critical (high priority 60) thread Th1 becomes ready-to-run. Thread Th2 is returned to a ready-to-run state and thread Th1 begins to run.
When thread Th1 requests mutex M1 with a call to either RtWaitForSingleObject or RtWaitForMultipleObjects, the owner of mutex M1 (which is thread Th3) is promoted to the priority of the requesting thread (priority 60).
After thread Th3 has been promoted, it preempts thread Th2 and is allowed to continue running until it releases both mutexes that it owns. The final call to RtReleaseMutex causes thread Th3 to return to its native priority.
After thread Th3 returns to its native priority it is preempted by Thread Th1. Thread Th1 gains ownership of mutex M1 and runs as the highest priority thread until completion.
Thread Th2 runs until completion.
Thread Th3 runs until completion.

Priority Inversion Protocol - Disable

When priority promotion is disabled, the subsystem does not do anything to track thread priority in relation to shared resources. This can be useful when developers want total control of thread priority. If detailed attention is given to the management and use of each shared resource, an application developer may not require priority inversion prevention. However, when not activating a priority inversion protocol, developers should take extra care with their application implementation, as priority inversion can still occur.

Thread Scheduling in a Multiprocessor Environment

In a Multiprocessor environment, code should be designed so that it is unnecessary to activate a priority inversion protocol. By carefully assigning each thread to a specific processor, based upon the expected execution time and priority of its task, a lower priority blocking thread may be running on a different processor than the blocked higher priority thread. In this case, promotion of the thread's lower priority would not speed up release of the common mutex.

This is shown in the illustration below.