Scheduling and schedulers
Dr. Bystrov
School of Electrical Electronic and Computer Engineering Newcastle University
Scheduling and schedulers
Copyright By PowCoder代写 加微信 powcoder
Introduction
Remember concurrent programming? How is concurrency implemented in a system with a single processor?
Remember concurrent models? How close to the “true concurrency” can we approach?
An Operating System (OS) – is it incomprehensibly complex?
Is it possible to guarantee compliance with the Real-Time constraints in some particular system?
What is Real-Time?
How to measure it?
Which scheduling algorithm to choose?
Is there the best scheduler for an application?
Scheduling and schedulers
Dimensions:
Hard vs. Soft Real-Time Time-Triggered vs. Event-Triggered Cooperative vs. Preemptive
Static vs. Dynamic (on/off-line) Optimal vs. heuristic
The permutations of the above dimensions give us the taxonomy of schedulers
Scheduling and schedulers
Real-Time constraints
usefulness
hard RT soft RT
Value or “usefulness” as a function of time It is important to meet the deadline
High or low performance is not important – “just do it by the deadline”
Scheduling and schedulers
Time-Triggered vs. Event-Triggered
B1 C1 A2 B2 C2 Time−Triggered Scheduler
timer ticks
Event−Triggered Scheduler
Scheduling and schedulers
Cooperative vs. Preemptive
Context switching
Cooperative
Preemptive
Scheduling and schedulers
Example: Taxonomy of TTS or ETS
Preemptive – non-preemptive: preemption means interrupting of one task with the other. Task priorities may be employed.
Static – dynamic: scheduling decision are based on parameters which can be fixed or not before task activation
Offline – online: scheduling decisions are made in advance or in the course of system operation
Optimal – heuristic: An optimal algorithm minimises some given cost function defined for the task set. Feasibility is a simple example of the cost function. Heuristic algorithms use rules, which do not guarantee optimality.
Scheduling and schedulers
Example: TTS (1,2)
(a) Timeline scheduler A
BBBB (b) Rate Monotonic scheduler
Scheduling and schedulers
Example: ETS, EDF, preemptive
release preemption deadlines
r1 r2 r3 d3 d1d2
J1 J2 J3 J2
context switching
Scheduling and schedulers
Task parameters (1)
Task Ji or τi
Arrival time ai or ri (Release Time, Request) ↑ Computation Time Ci (exec. without interruption)
Abs. Deadline di ↓ Rel. Deadline Di, Di = di − ri ↓ Start Time si
Finishing Time fi
Scheduling and schedulers
Task parameters (2)
Response Time Ri, Ri = fi − ri
Criticality: hard/soft
Lateness Li, Li = fi − di (negative is good!) Tardiness or Exceeding time Ei, Ei = max(0, Li)
LaxityorSlackTimeXi,Xi =di−ai−Ci
(the max time a task can be delayed on its activation to complete within its deadline)
Scheduling and schedulers
Task parameters (3)
Critical Instant – the time at which the release of the task will produce the largest response time
Critical Time Zone – the interval between the critical instant and the response time of the corresponding request of the task
Relative Release Jitter – the max deviation of the start time of two consecutive instances
RRJi = maxk (si,k − ri,k) − (si,k−1 − ri,k−1)
Absolute Release Jitter – the max deviation of the start time among all instances
ARJi = maxk(si,k − ri,k) − mink(si,k − ri,k)
The same for the Execution and Finishing Jitter, Absolute or Relative.
Scheduling and schedulers
Example: Construct a schedule (1)
Construct an EDF (Earliest Deadline first) schedule. In this table Ci denotes execution time, Di – relative deadline, Ti – period and τi – task name. Use the non-preemptive execution model.
task Ci Di Ti
τ1 2 5 6 τ2 2 4 8 τ3 4 8 12
Scheduling and schedulers
Example: Construct a schedule (2)
Scheduling and schedulers
Example: calculate task parameters
Absolute Release Jitter for τ1 is 2 Absolute Finishing Jitter for τ2 is 2 Absolute Execution Jitter for τ3 is 0.
Scheduling and schedulers
Two “keys” to the proof:
RM optimality (1)
“Given two periodic tasks τ1 and τ2, with T1 < T2, if the schedule is feasible by an arbitrary priority assignment, then it is also feasible by RM. That is, RM is optimal.” [Buttazzo book]
First step: show that a critical instant for any task occurs whenever the task is released simultaneously with all higher-priority tasks.
Schedulability is checked on critical instants!
Second step: show that if a task set is schedulable by an arbitrary priority assignment, then it is also schedulable by RM.
Scheduling and schedulers
RM optimality (2)
Scheduling and schedulers
RM optimality (3)
Start with an inverted w.r.t. RM priority, i.e. when
C1 + C2 ≤ T1, then back to RM and consider two cases
(a)C1