Scheduling

Real-Time Scheduling

Reading

Real-time Scheduling

Intro and Definitions

Real-time systems have special scheduling considerations. The key difference is the existence of deadlines -- some real-world time by which a computational task must be accomplished. There are two general categories of tasks: Tasks in a real-time system can be further characterized by whether they recur or not: In general, processes in real-time systems are designed in such a way that the time to complete their tasks is well defined and predictable. Because real-time tasks may be periodic or aperiodic, and of varying duration, scheduling them properly is important to the system design. There are also two types of deadline:

Priority and Deadline Scheduling

There are two basic strategies for real-time scheduling, Priority and Earliest Deadline. Example. Consider an example system with two periodic tasks, A and B. An instance of task A arrives every 20ms, requires 10ms of execution time, and has a hard completion deadline 20ms after arrival. An instance of task B arrives every 50ms, has an execution time of 25ms, and a hard completion deadline of 50ms after arrival. The first few instances of A and B are show in the table:
Process Arrival
Time
Execution
Time
Completion
Deadline
A(1) 0 10 20
A(2) 20 10 40
A(3) 40 10 60
A(4) 60 10 80
A(5) 80 10 100
B(1) 0 25 50
B(2) 50 25 100

These periodic tasks could be scheduled as follows:

Real time scheduling (Stallings example).

Note the missed deadlines for fixed priority (A) and fixed priority (B), but no missed deadlines for earliest completion deadline scheduling.

Rate Monotonic Scheduling

When all the tasks in a system are periodic but the task frequencies vary, we can take a theoretical approach to schedulability, using a technique called Rate Monotonic Scheduling. RMS has the following requirements/assumptions:

RMS scheduling (Stallings).


Each task has a defined amount of time required for computation, and a defined arrival rate:

A periodic task P (Stallings).

We can compute all of the Utilization values for the tasks in the system, and make a determination about whether the set of tasks is schedulable or not. For RMS, it turns out that a set of n processes is guaranteed to be schedulable if: $$\frac{C_1}{T_1} + \frac{C_2}{T_2} + \dots + \frac{C_n}{T_n}\leq n(2^{1/n}-1)$$ Some values of the equation's right-hand side, tabulated vs. n, are show in the following table:

n n(21/n-1)
1 1.0
2 .828
3 .779
4 .756
5 .743
6 .734
0.693
Example: Consider a system with 4 periodic tasks: The total task utilization for the system is: .1 + .3 + .2 + .15 = .750. Since .750 < .756, the task set is guaranteed to be schedulable using RMS. Note, however, that the system designer still needs to develop the actual schedule.

Priority Inversion and Priority Inheritance

Priority inversion is not unique to real-time scheduling, but does come up in that environment. Priority inversion is the idea that a higher-priority process can be blocked by a lower-priority process due to a shared resource. Here is a general example:

Suppose there are two processes -- a high priority process, H, and a low priority process, L. When there is a high priority process ready to run, it is always scheduled over low priority processes (strict priority scheduling). But if H and L both use a shared resource that's protected by a semaphore or other concurrency primitive, the following situation could occur. L has the semaphore and is in its critical region, but gets pre-empted by the scheduler. H can't proceed because it is waiting on the semaphore, but L can't proceed either because it can't get scheduled, due to higher-priority processes. This can happen with just two processes if H employs busy waiting (which keeps it in the running state all the time) instead of blocking, or it can involve other, medium-priority processes.

Priority inversion errors are subtle, but they do occur. The most famous example involved NASA's Mars Pathfinder probe in 1997 (Image: NASA/JPL). A full description of the incident is available here.

There are a number of solutions to the priority inversion problem. The most robust general solution is Priority Inheritance. Whenever a higher-priority task has to wait on a resource shared with a lower-priority task, the lower-priority task is temporarily boosted to the higher priority while it uses the shared resource. Microsoft Windows uses a randomized version of this priority-boosting strategy, when ready tasks are holding resource locks (i.e., are in a critical section).

Modern real-time operating systems address the priority inversion problem explicitly, usually with some form of priority inheritance.

Summary / Key Points