If you've got a lot of tasks to do, and tight dead-lines to meet, what's the best way to prioritize them?
The scheduling algorithm you choose depends on your goals. Different algorithms yield different results. Let's suppose you're given ten jobs and each will take a day to finish. In ten days, you will have all of them done. But what if one or more has a deadline? If the ninth task given to you has a deadline in three days, then doing the tasks in the order you receive them will cause you to miss that deadline.
The purpose of a real-time scheduling algorithm is to ensure that critical timing constraints, such as deadlines and response time, are met. When necessary, decisions are made that favor the most critical timing constraints, even at the cost of violating others. Real-time scheduling is also used to allocate processor time between tasks in soft real-time embedded systems.
Many real-time systems use preemptive multitasking, especially those with an underlying real-time operating system (RTOS). Priorities are assigned to tasks, and the RTOS always executes the ready task with highest priority.
In this case, the scheduling algorithm is the method in which priorities are assigned. Most algorithms are classified as fixed priority, dynamic priority, or mixed priority. A fixed-priority algorithm assigns all priorities at design time, and those priorities remain constant for the lifetime of the task. A dynamic-priority algorithm assigns priorities at runtime, based on execution parameters of tasks, such as upcoming deadlines. A mixed-priority algorithm has both static and dynamic components. Needless to say, fixed-priority algorithms tend to be simpler than algorithms that must compute priorities on the fly.
To demonstrate the importance of a scheduling algorithm, consider a system with only two tasks, which we'll call t1 and t2 . Assume these are both periodic tasks with periods T1 and T2 , and each has a deadline that is the beginning of its next cycle. Task t1 has T1 = 50ms, and a worst-case execution time of C1 = 25ms. Task t2 has T2 = 100ms and C2 = 40ms. Note that the utilization, Ui , of task ti is Ci /Ti . Thus U1 = 50% and U2 = 40%. This means total requested utilization U = U1 + U2 = 90%. It seems logical that if utilization is less than 100%, there should be enough available CPU time to execute both tasks.
Let's consider a static priority scheduling algorithm. With two tasks, there are only two possibilities:
Case 1: Priority(t1 ) > Priority(t2 )
Case 2: Priority(t1 ) <>2 )
The two cases are shown in Figure1. In Case 1, both tasks meet their respective deadlines. In Case 2, however, t1 misses a deadline, despite 10% idle time. This illustrates the importance of priority assignment.
Figure 1: Cases of fixed-priority scheduling with two tasks, T1 =50, C1 =25, T2 =100, C2 =40
Getting your priorities straight
The rate monotonic algorithm (RMA) is a procedure for assigning fixed priorities to tasks to maximize their “schedulability.” A task set is considered schedulable if all tasks meet all deadlines all the time. The algorithm is simple:
Assign the priority of each task according to its period, so that the shorter the period the higher the priority.
In the example, the period of t1 is shorter than the period of t2 . Following RMA's rule, we assign the higher priority to t1 . This corresponds to Case 1 in Figure 1, which is the priority assignment that succeeded in meeting all deadlines.
RMA is the optimal fixed-priority algorithm. If a task set cannot be scheduled using the RMA algorithm, it cannot be scheduled using any fixed-priority algorithm.
One major limitation of fixed-priority scheduling is that it is not always possible to fully utilize the CPU. Even though RMA is the optimal fixed-priority scheme, it has a worst-case schedule bound of:
Wn = n(2(1/n) – 1)
where n is the number of tasks in a system. As you would expect, the worst-case schedulable bound for one task is 100%. But, as the number of tasks increases, the schedulable bound decreases, eventually approaching its limit of about 69.3% (ln 2, to be precise).
It is theoretically possible for a set of tasks to require just 70% CPU utilization in sum and still not meet all their deadlines. For example, consider the case shown in Figure 2. The only change is that both the period and execution time of t2 have been lowered. Based on RMA, task t1 is assigned higher priority. Despite only 90% utilization, task t2 misses its first deadline. Reversing priorities would not have improved the situation.
Figure 2: Some task sets aren't schedulable (T1 =50 C1 =25, T2 =75, C2 =30)
In this case, the only way to meet all deadlines is to use a dynamic scheduling algorithm, which, because it increases system complexity, is not available in many commercial RTOSes.
Sometimes a particular set of tasks wil have total utilization above the worst-case schedulable bound and still be schedulable with fixed priorities. Figure 1's Case 1 is a perfect example. Schedulability then depends on the specifics of the periods and execution times of each task in the set, which must be analyzed by hand. Only if the total utilization is less than Wn can you skip that step and assume that all the tasks will meet all their deadlines.
To benefit most from using a fixed-priority preemptive RTOS, consider the following rules of thumb:
- Always assign priorities according to RMA. Manually assigning fixed priorities will not give you a better solution.
- If total utilization is less than or equal to Wn, all tasks will meet all deadlines, so no additional work needs to be done.
- If total utilization is greater thanWn , an analysis of the specific task set is needed, to verify whether or not it will be schedulable.#
- To achieve 100% utilization when using fixed priorities, assign periods so that all tasks are harmonic. This means that for each task, its period is an exact multiple of every other task that has a shorter period.
The last rule of thumb provides a simple guideline for most efficient use of the processor. For example, a three-task set whose periods are 10, 20, and 40, respectively, is harmonic, and preferred over a task set with periods 10, 20, and 50.
David B. Stewart is chief technology officer of Embedded Research Solutions. He holds a PhD in computer engineering from Carnegie Mellon University. His e-mail address is .
Michael Barr is the former editor in chief of Embedded Systems Programming. He is also the author of Programming Embedded Systems in C and C++ (O'Reilly, 1999) and an adjunct faculty member at the University of Maryland.
1. Stewart, Dave. “Real Time,” Embedded Systems Programming, November 2001, p. 87.