Introduction to Real-Time Systems & Scheduling Theory

A Very Short Introduction to Real-Time Systems & Real- Time Scheduling Theory Rui Liu Jan. 21 2015

What is a Real-Time System? A system with a dual notion of correctness: Logical correctness ( do the right thing ); Temporal correctness ( do it on time ). A system in which predictability is as important as performance.

A Simple Example A robot arm picking up objects from a conveyor belt.

Periodic Task System Set T = {T1, T2, Tn} (n=2) of periodic tasks scheduled on m (=1) core(s): Task Ti = (ei,pi)releases a job with exec. cost eievery pi time units. o Ti s utilization (or weight) is ui = ei/pi. o Total utilization is U(T) = Ti ei/pi. 5 2 T1 = (2,5) One Processor Here T2 = (9,15) 0 5 10 15 20 25 30 4

Periodic Task System Set T = {T1, T2} of periodic tasks scheduled on 1 core: Task Ti = (ei,pi)releases a job with exec. cost eievery pi time units. o Ti s utilization (or weight) is ui = ei/pi. o Total utilization is U(T) = Ti ei/pi. o Each job of Ti has a deadline at the next job release of Ti. 5 2 T1 = (2,5) One Processor Here T2 = (9,15) 0 5 10 15 20 25 30 5

Other Task System Types Sporadic: here, pi is a minimum separation between job releases of Ti. For periodic or sporadic, relative deadlines di can be implicit: di = pi (assumed unless stated otherwise); constrained: di < pi; Arbitrary: di ? pi. Also can have aperiodic (one-shot) jobs. hard aperiodic: job has a deadline

Sporadic vs. Periodic An implicit-deadline periodic task Ti with pi = 5 and ei = 2 could execute like this: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 = job release = job deadline If it is sporadic, it could release and execute like this: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 7

Notations & Definitions Ji,k is the kth job of Ti. ri,k is the release time of Ji,k. di,k is its (absolute) deadline. i is the time of the first release; called phase. A task system is synchronous if all phases are 0, and asynchronous otherwise. Completion Time = Time when a job completes execution. Response Time = Completion Time - ri,k Tardiness = max(0, Completion Time - di,k) Hyperperiod = LCM (least common multiple) of the task periods.

Real-Time Correctness Hard Real-Time: No deadline is missed. Soft Real-Time: Some deadline can be missed. Can be defined in different ways. We use the existence of bounded tardiness.

Task Dependencies We are mainly concerned with two main kinds of explicit dependencies: Critical Sections. Precedence Constraints. Also, there exist implicit dependencies (e.g. shared buses).

Scheduling & Schedulability Scheduling algorithm: produce a schedule for task system T. Ex: EDF (Earliest-Deadline-First) Schedulability test: test if a certain scheduling algorithm can schedule T without violating timing requirements. Ex: no timing requirement will be violated if T is scheduled with EDF a timing requirement will (or may) be violated yes Test for EDF T no 11

Schedulability and Optimality of Scheduling Algorithms A schedule is feasible if all timing requirements are met. A task set T is schedulable using scheduling algorithm A if A always produces a feasible schedule for T. A scheduling algorithm is optimal if it always produces a feasible schedule when one exists. 12

Feasibility Test & Schedulability Test A feasibility test indicates whether some algorithm (from a class of algorithms) can correctly schedule a given task set; A schedulability test indicates whether a specific algorithm (e.g., EDF) can correctly schedule a given task set. Such tests can either be exact or only sufficient. 13

Exact Test vs. Sufficient Test T is schedulable by some algorithm in C Exact: yes Feasibility test for some class C Task Set T no T is not schedulable by any algorithm in C yes T is schedulable by A Schedulability test for algorithm A Task Set T no T is not schedulable by A Sufficient: T is schedulable by some algorithm in C yes Feasibility test for some class C Task Set T no don t know yes T is schedulable by A Schedulability test for Algorithm A Task Set T no don t know 14

Categories of Schedulability Tests Polynomial time tests. Usually, utilization-based tests. Pseudo-polynomial time tests. Usually, tests that involve upper bounding processor demand over some pseudo-polynomial interval. Exponential time tests. Usually, tests that involve upper bounding processor demand over some exponentially large interval (e.g. the hyperperiod).

Platform For most of this part, we assume a uniprocessor platform. Some issues about real-time scheduling on multiprocessor will be brought up in next part.

Classification of Scheduling Algorithms All scheduling algorithms dynamic scheduling (or online, or priority driven, or event triggered) static scheduling (or offline, or clock driven, or time triggered) dynamic-priority scheduling static-priority scheduling

Clock Driven Scheduling Periodic tasks are scheduled using a pre- computed static schedule stored in a table Ti I if Ti is to be scheduled at time tk if no periodic task is scheduled at time tk T(tk) = Assume this table is given for now. Aperiodic jobs (if released) are scheduled in time intervals not used by periodic tasks.

Example Consider a system of four tasks, T1 = (1, 4), T2 = (1.8, 5,), T3 = (1, 20), T4 = (2, 20), with the following static schedule. schedule repeats T1 T3T2 T1 T2 T1 T2 T1 T1 T2 T4 0 4 8 12 16 20 The first few table entries would be: (0, T1), (1, T3), (2, T2), (3.8, I), (4, T1), Frame size is 2 in this example. Scheduling decisions are only made at frame boundaries.

Response Time of Aperiodic Jobs At first glance, it makes sense to give hard real-time jobs higher priority than aperiodic jobs. However, this may lengthen the response times of aperiodic jobs. aperiodic hard aperiodic hard hard deadline is still met but aperiodic job completes sooner

Slack Stealing Basic idea: there is no point in completing a hard real-time job early, as long as it finishes by its deadline. Let the total amount of time allocated to all the slices scheduled in frame k be xk. The slack available at the beginning of frame k is f xk. If the aperiodic job queue is nonempty, let aperiodic jobs execute in each frame whenever there is nonzero slack.

Example schedule repeats hard real-time jobs T1 T2 T1 T2 T3 T4 T1 T3 T1 T1 0 4 8 12 16 20 1.5 0.5 2.0 aperiodic jobs A2 A1 A3 0 4 8 12 16 20 without slack stealing T2 T1 T2 T1 T3 T3 T1 T1 T1 T4 0 4 8 12 16 20 with slack stealing T2 T2 T1T1 T3 T4 T1 T3 T1 T1 0 4 8 12 16 20

Summary of Clock Driven Scheduling Simple, free of anomalies, and easy to certify. As a result, predominant in many safety- critical applications (like airplanes). Disadvantages Very brittle. real-world tasks are hard to support. All tasks executing together must be a priori analyzed.

Classification of Scheduling Algorithms All scheduling algorithms dynamic scheduling (or online, or priority driven, or event triggered) static scheduling (or offline, or clock driven, or time triggered) dynamic-priority scheduling static-priority scheduling

Static-Priority Scheduling Each task is assigned a priority. Different jobs of a task are assigned the same priority. Tasks are indexed in decreasing priority order. If i < k, then Ti has higher priority than Tk.

Rate-Monotonic Tasks with smallerperiods have higher priorities. T1 T2 T3 T1 = (0.5, 3), T2 = (1, 4), T3 = (2, 6)

Deadline-Monotonic Tasks with smallerrelative deadlines have higher priorities. Same as RM for implicit-deadline systems. Example Schedule: Let s give T2a tighter deadline T 1= T2 T 2= T1 T 3 = T3 T1 = (0.5, 3), T2 = (1, 4, 2), T3 = (2, 6)

Non-optimality of RM and DM Neither RM nor DM is optimal. Simple proof: consider T1 = (1, 2) and T2 = (2.5, 5). Regardless of priority assignment, a deadline will be missed. However, the task system is feasible. No static-priority scheduling algorithm is optimal.

Utilization-based Schedulability Test Theorem A system of n independent, preemptable sporadic tasks with implicit deadlines can be feasibly scheduled on a processor by the RM algorithm if its total utilization U is at most URM(n) = n(21/n 1).

Pseudo-Polynomial Time Test Time-demand function of task Ti: For any fixed-priority algorithm A with di pi for all i Theorem: A system of sporadic, independent, preemptable tasks is schedulable on one processor by algorithm A if ( i:: ( t: 0 < t di:: wi(t) t)) holds.

Classification of Scheduling Algorithms All scheduling algorithms dynamic scheduling (or online, or priority driven, or event triggered) static scheduling (or offline, or clock driven, or time triggered) dynamic-priority scheduling static-priority scheduling

Dynamic-Priority Scheduling dynamic-priority scheduling Job level dynamic-priority (e.g. LLF) Job level fixed- priority (e.g. EDF)

Job Level-Fixed Dynamic- Priority Scheduling The priority of a job is determined at release time. Example: First In First Out(FIFO) Jobs priorities are ordered by release times. Earliest Deadline First(EDF): Jobs priorities are ordered by (absolute) deadlines.

Optimality of EDF When preemption is allowed and jobs do not contend for resources, the EDF algorithm can produce a feasible schedule of a set J of jobs with arbitrary release times and deadlines on a processor if and only if J has feasible schedules. Notes: Applies even if tasks are not periodic. If periodic, a task s relative deadline can be less than its period, equal to its period, or greater than its period. However, non-preemptive EDF is not optimal.

Two Famous Schedulability Tests Theorem A system T of preemptable, sporadic tasks with implicit deadlines is HRT-schedulable by EDF, if and only if U(T) 1. Useful when deadlines < periods Theorem A system T of preemptable, sporadic tasks is HRT-schedulable by EDF, if . ) p , min(d 1 k k k = n e 1 k Density

Coming up next Up to now, we have been focusing on uni-core CPU scheduling. Multiprocessor scheduling and scheduling with additional resources come in next part.

Thank you!