|
[Part 6 reviews various RTOS scheduling algorithms and explains the pros and cons of each. Part 8 shows how to analyze systems with aperiodic tasks. It also shows how to avoid priority inversion by using priority inheritance.]
Many DSP systems are multirate systems. This means there are multiple tasks in the DSP system running at different periodic rates. Multirate DSP systems can be managed using nonpreemptive as well as preemptive scheduling techniques. Nonpreemptive techniques include using state machines as well as cyclic executives.
Analyzing Scheduling Behavior in Preemptive Systems
Preemptive approaches include using scheduling algorithms similar to the ones described in part 6 (rate monotonic scheduling, deadline monotonic scheduling, etc).This article will overview techniques to analyze a number of tasks statically in a DSP system in order to schedule them in the most optimal way for system execution. In the sections that follow, we'll look at three different ways of determining whether a particular set of tasks will meet its deadlines: rate monotonic analysis, completion time analysis, and response time analysis.
Rate Monotonic Analysis
Some of the scheduling strategies presented earlier presented a means of scheduling but did not give any information on whether the deadlines would actually be met. Rate Monotonic analysis addresses how to determine whether a group of tasks, whose individual CPU utilization is known, will meet their deadlines. This approach assumes a priority preemption scheduling algorithm. The approach also assumes independent tasks (no communication or synchronization). [4].
In this discussion, each task discussed has the following properties:
- Each task is a periodic task which has a period T, which is the frequency with which it executes.
- An execution time C, which is the CPU time required during the period.
- A utilization U, which is the ratio C/T. A task is schedulable if all its deadlines are met (i.e., the task completes its execution before its period elapses.) A group of tasks is considered to be schedulable if each task can meet its deadlines.
Rate monotonic analysis (RMA) is a mathematical solution to the scheduling problem for periodic tasks with known cost. The assumption with the RMA approach is that the total utilization must always be less than or equal to 100%. [5]
For a set of independent periodic tasks, the rate monotonic algorithm assigns each task a fixed-priority based on its period, such that the shorter the period of a task, the higher the priority. For three tasks T1, T2, and T3 with periods of 5, 15 and 40 msec respectively the highest priority is given to the task T1, as it has the shortest period, the medium priority to task T2, and the lowest priority to task T3. Note the priority assignment is independent of the application's "priority," i.e., how important meeting this deadline is to the functioning of the system or user concerns.
Utilization bound theorem
The RMA approach to scheduling tasks uses a utilization bound theorem to determine schedulability. Using this theorem, a set of n independent periodic tasks scheduled by the rate monotonic algorithm will always meet its deadlines, for all task phasings, if the total utilization of the task set is lower than the bound given in Figure 1. This table shows the utilization bound for several examples of task numbers.
Figure 1. Utilization bound for different task sets.
This theory is a worst case approximation. For a randomly chosen group of tasks, it has been shown that the likely upper bound is 88%. The special case where all periods are harmonic has an upper bound of 100%. The algorithm is stable in conditions where there is a transient overload. In this case, there is a subset of the total number of tasks, namely those with the highest priorities that will still meet their deadlines.
A Very Useful Special Case
In the special case of all harmonic periods, RMS allows you to use 100% of the processor's throughput and still meet all deadlines. In other words, the utilization bound is 1.0 for harmonic task sets. A task set is said to be harmonic if the periods of all its tasks are either integral multiples or sub-multiples of one another. By simply assigning the task with a shorter period (higher rate) a fixed higher priority, then all tasks are guaranteed to meet their deadlines.
Examples of applications where the tasks tend to have harmonic periods include:
- Audio sample processing.
- Video capture and processing.
- Temperature and speed monitoring.
Footnotes
4. The restriction of no communication or synchronization may appear to be unrealistic, but there are techniques for dealing with this that will be discussed later.
5. Any more and you are exceeding the capacity of the CPU. Are you asking for more computing power than you have? If so, forget it!
|
