[Part 7 shows how to analyze scheduling behavior, and how to ensure tasks meet their deadlines.]
Analyzing More Complex Systems
Until now, the model used to determine the schedulability of tasks has been fairly simple:
- All tasks are periodic, with known periods.
- All tasks have a deadline equal to their period.
- Rate monotonic priority assignment.
- All tasks are completely independent of each other.
- Preemptive scheduling strategy.
- Application has a fixed set of priorities (static).
- All system overhead is included in the execution time.
- All tasks have a fixed worst-case execution time.
In reality, there are many examples of aperiodic as well as periodic events in real-time systems. An aperiodic task is assumed to execute once within some period Ta, which represents the minimum interarrival time of the event which activates the task. The CPU time Ca is the execution time caused by a single event. The utilization time is then a worst case utilization time and can be much less than the actual. From a schedulability analysis viewpoint, an aperiodic task is equivalent to a periodic task whose period is equal to Ta and whose execution time is Ca.
An aperiodic task often needs to respond much quicker than the minimum arrival time. An example would be an error signal which interrupts very infrequently, but when it does it needs to be handled with urgency. This breaks the assumption we have made that the deadline is equal to the period. Now the deadline is less than the period. This is referred to as rate monotonic priority inversion. A rate monotonic task i can only be pre-empted once by a task with rate monotonic priority inversion as the monotonic task has a shorter period. At most the task can be blocked for the execution time of the task with the rate monotonic priority inversion. The worst case assumption is made that every lower priority task tl is blocked once by every aperiodic task with monotonic priority inversion.
Deadline Monotonic Scheduling
Deadline monotonic priority assigns the highest priorities to the jobs with the shortest deadlines:
The priorities are fixed and assigned before the application begins. It can be proven this is an optimal scheduling algorithm for deadlines less than or equal to the period T using the static scheduling model (Rate monotonic is a special case when all Di = T).
To test whether a task set is schedulable under the Deadline Monotonic policy, apply the following Deadline Monotonic scheduling to the task set:
The Deadline Monotonic scheduling algorithm tests if all jobs will meet their deadlines under worst case conditions (critical task phasings). The worst case response time includes the delays encountered by each task by preemption from other higher priority tasks in the system. This algorithm can easily be extended to include other delay factors such as context switch times, blocking due to waiting on system resources, and other scheduler overhead and latencies:
Example: dynamic vs. static scheduling
Rate Monotonic Scheduling has shown to be optimal among static priority policies. However, some task sets that aren't schedulable using RMS can be scheduled using dynamic strategies. An example is a task set where the deadline for completing processing is not the task period (the deadline is some time shorter than the task period). In this example, we'll show a task set that can be scheduled under the deadline monotonic priority policy, but not under RMS.
Consider the following task set:
Using the Deadline Monotonic approach to scheduling, the task execution profile is shown in Figure 1. All tasks meet their respective deadlines using this approach.
Figure 1. Example of deadline monotonic scheduling.
Now consider the same task set, this time prioritized using the Rate Monotonic approach to scheduling. The task priorities change using the RMA approach, as shown below: