Scheduling and schedulers
Dr. Bystrov
School of Electrical Electronic and Computer Engineering University of Newcastle upon Tyne
Scheduling and schedulers – p. 1/25
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 – p. 2/25
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 – p. 3/25
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 – p. 4/25
Time-Triggered vs. Event-Triggered
timer ticks
B1 C1 A2 B2 C2 Time−Triggered Scheduler
Event−Triggered Scheduler
Scheduling and schedulers – p. 5/25
Cooperative vs. Preemptive
Context switching
Cooperative
Preemptive
Scheduling and schedulers – p. 6/25
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 – p. 7/25
Example: TTS (1,2)
(a) Timeline scheduler A
BBBB (b) Rate Monotonic scheduler
Scheduling and schedulers – p. 8/25
Example: ETS, EDF, preemptive
release preemption deadlines
r1 r2 r3 d3 d1d2
J1 J2 J3 J2
context switching
Scheduling and schedulers – p. 9/25
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 – p. 10/25
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)
Laxity or Xi, Xi = di −ai −Ci
(the max time a task can be delayed on its activation to complete within its deadline)
Scheduling and schedulers – p. 11/25
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 – p. 12/25
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 – p. 13/25
Example: Construct a schedule (2)
Scheduling and schedulers – p. 14/25
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 – p. 15/25
RM optimality (1)
Read the book! Two “keys” to the proof:
“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 – p. 16/25
RM optimality (2)
Scheduling and schedulers – p. 17/25
RM optimality (3)
Consider two cases (the last ri is in the critical zone of τj), try to change the priority, it will not be better
Case (a) t
Scheduling and schedulers – p. 18/25
Periodic EDF optimality (1)
Preemption is crucial for optimality!
Scheduling and schedulers – p. 19/25
Periodic EDF optimality (2)
Theorem: A set of periodic tasks is schedulable with EDF iff
( 1 ) n C i ≤ 1 i=1 Ti
Scheduling and schedulers – p. 20/25
The necessary condition
It is simple – the CPU utilisation cannot exceed 1. Create an example!
Scheduling and schedulers – p. 21/25
The sufficient condition
Proof by contradiction:
Assume U < 1 and the set of tasks is not schedulable.
Construct the schedule, find an overrun and find the longest interval [t1, t2] of continuous utilisation directly preceding the overrun.
Observe, that t1 is the release time for some periodic instance.
Calculate the total computational time of all tasks in [t1, t2].
Do maths (or just explain) and find the contradiction
Scheduling and schedulers – p. 22/25
The sufficient condition (diag.)
idle t1 t2
Scheduling and schedulers – p. 23/25
The sufficient condition (maths)
(2) Cp(t1,t2)= Ck=n t2−t1Ci. rk ≥t1 ,dk ≤t2 i=1 Ti
The key to the proof is the following observation
(3) Cp(t1,t2)≤n t2 −t1Ci =(t2 −t1)U. i=1 Ti
Since a deadline is missed at t2, Cp(t1, t2) must be greater than the available CPU time (t2 − t1). Together with (2) and (3) it gives the following inequality:
(4) (t2 − t1) < Cp(t1, t2) ≤ (t2 − t1)U.
This is not be true under the initial assumption of U < 1.This concludes the proof.
Scheduling and schedulers – p. 24/25
Presentations
What is next?
Please read the book [Buttazzo] – all presentation topics, be prepared to discuss the presentations
Presentations: 15 min. each, additional time will be booked the next week.
Please email your presentation to me, use your last name as the name of the file.
Scheduling and schedulers – p. 25/25
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com