Scheduling

# Real-Time Scheduling

## 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:
• Hard Real Time Tasks: completion by the specified deadline is essential to correct operation of the system.
• Soft Real Time Tasks: completion by the specified deadline is desirable, but the system will continue to function if the deadline is missed.
Tasks in a real-time system can be further characterized by whether they recur or not:
• Periodic: tasks recur at regular, predictable intervals.
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:

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 ArrivalTime ExecutionTime 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:

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:
• The higher frequency tasks are given higher priority, and the lower frequency tasks are given lower priority (priority correlates strictly with frequency). Priorities are static (do not change).
• Processes due not share resources with each other (one task may not block on a resource held by another task).
• Deterministic deadlines are exactly equal to periods (i.e., a task's deadline conincides with the end of its period, when the next instance of that task will arrive).
• Context switch times are negligible.

RMS scheduling (Stallings).

Each task has a defined amount of time required for computation, and a defined arrival rate:
• Computation Time (C): The time required for the task to execute
• Task Period (T): The total time between recurring arrivals of the task
• Utilization (C/T): The fraction of the task period during which computation occurs.

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:
• Task P1: C1=10; T1=100; U1=.1
• Task P2: C1=15; T1=50; U1=.3
• Task P3: C1=10; T1=50; U1=.2
• Task P4: C1=30; T1=200; U1=.15
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

• Real-time scheduling involves both hard and soft real-time tasks, which may be periodic or aperiodic.
• Real-time schedulers are usually based on strict priority or earliest deadline (start or completion).
• A special form of real-time scheduling for periodic tasks is rate monotonic scheduling or RMS, which can provide schedulability assurances based on overall task utilization.
• An important problem that occurs in priority-based systems that also have shared resources is priority inversion. Well known solutions exist, a common one being priority inheritance.