Real-Time Scheduling

Distinctive Embedded System Attributes
● Reactive: computations occur in response to external events
Periodic events (e.g. rotating machinery and control loops).
Aperiodic events (e.g. button click).
● Real Time: correctness is partially a function of time
Hard real time.
– Absolute deadline, beyond which answer is useless
– May include minimum time as well as maximum time
Soft real time.
– Approximate deadline
– Utility of answer degrades with time difference from deadline

Real-Time Review
● Real time is not just “real fast”
Real time means that correctness of result depends on both functional correctness and time that the result is delivered.
● Soft real time
Utility degrades with distance from deadline.
● Hard real time
System fails if deadline window is missed.
● Firm real time
Result has no utility outside deadline window, but system can withstand a few missed results.

Type of Real-Time Scheduling

Taxonomy of Real-Time Scheduling
● Dynamic vs. Static
Dynamic schedule computed at run-time based on tasks really executing.
Static schedule done at compile time for all possible tasks.
● Preemptive permits one task to preempt another one of lower priority

Schedulability
● NP-hard if there are any resources dependencies
Prove it definitely cannot be scheduled.
Find a schedule if it is easy to do.
Stuck in the middle somewhere.

Necessary and sufficient schedulability test

Scheduling Parameters
● Assume N CPUs available for execution of a single task set
● Set of tasks {Ti}
Periods pi.
Deadline di (completion deadline after task is queued).
Execution time ci (amount of CPU time to complete).
● Handy values:
Laxity li = di – ci (amount of slack time before Ti must begin execution).
Utilization factor ui = ci/pi(portion of CPU used).

Static Schedule
● Assume non-preemptive system with 5 Restrictions:
1. Tasks {Ti} are periodic, with hard deadlines and no jitter
2. Tasks are completely independent
3. Deadline = period pi = di
4. Computation time ci is known and constant
5. Context switching is free (zero cost) INCLUDING network messages to send context to another CPU(!)
● Consider least common multiple of periods pi
This considers all possible cases of period phase differences.
Worst case is time that is product of all periods; usually not that bad.
If you can figure out (somehow) how to schedule this, you win.
● Performance
Optimal if all tasks always run; can get up to 100% utilization.
If it runs once, it will always work.

EDF: Earliest Deadline First
● Assume a preemptive system with dynamic priorities, and (same 5 restrictions)
● Scheduling policy:
Always execute the task with the nearest deadline
● Performance
Optimal for uniprocessor (supports up to 100% of CPU usage in all situations)
If you’re overloaded, ensures that a lot of tasks don’t complete
– Gives everyone a chance to fail at the expense of the later tasks

Least Laxity
● Assume a preemptive system with dynamic priorities, and (same 5 restrictions)
● Scheduling policy:
Always execute the task with the smallest laxity.
● Performance:
Optimal for uniprocessor (supports up to 100% of CPU usage in all situations).
– Similar in properties to EDF
A little more general than EDF for multiprocessors.
– Takes into account that slack time is more meaningful than deadline for tasks of mixed computing sizes
Probably more graceful degradations.
– Laxity measure permits dumping tasks that are hopeless causes

EDF/Least Laxity Tradeoffs
● Pro:
If it works, it can get 100% efficiency (on a uniprocessor)
● Con:
It is not always feasible to prove that it will work in all cases.
– And having it work for a while doesn’t mean it will always work
Requires dynamic prioritization.
The laxity time hack for global priority has limits.
– May take too many bits to achieve fine-grain temporal ordering
– May take too many bits to achieve a long enough time horizon

Rate Monotonic
● Assume a preemptive system with static priorities, and (same 5 restrictions) plus

● Scheduling policy:
Highest static priority goes to shortest period; always execute highest priority.
● Performance:
Provides a guarantee for schedulability with CPU load of ~70%.
– Even with arbitrarily selected task periods
– Can do better if you know about periods & offsets
If all periods are multiple of shortest period, works for CPU load of 100%.