Overall Stucture of Real Time Systems
Task 1
... ...
Scheduler
Task n
RTOS/Run-Time System
Hardware
How to schedule the Tasks such that given timing constraints are satisfied?
1
The goal of task scheduling is to ensure given constraints
User requirements:
Timing constraints Energy consumption Economical constraints Period or frequency Execution time (resource requirement) Code size Input/output relations Precedence constraints
speed of the processor/number of CPU cycles Number of processors Memory size Memory bandwidth Communication bandwidth Caches
Task parameters (kind of application requirements)
Design/Implementation constraints
Platform constraints
So far
RTOS features
Deterministic Responsiveness Users control over OS policies Controlled Code size
OS standard functions Task synchronization (priority inversion, deadlocks etc) Task scheduling Real-Time Facilities (e.g. Ada, delay, delay until) Concurrency/multitasking (e.g. Ada tasking) Communication/synchronization (e.g. Ada Rendezvous) Consistency in data sharing (e.g. Ada protected data type)
Priority inversion problem (unbounded blocking)
RTOS functions
RT programming languages
Resource sharing and priority ceiling protocols
Solutions: NPP, BIP, HLP, PCP
Todays topic
Real-Time Scheduling:
Basic concepts and basic algorithms
My plan
Simple task model
Basic scheduling theory: summary Liu and Laylands classic results Response time analysis
Periodic tasks (recurring tasks)
Multiprocessor/multi-core scheduling
Task models
Non periodic/Aperiodic Tasks
Appear once only
Basic task model (3 parameters):
A: arrving time C: computing time (resource requirement) D: deadline (relative deadline)
Constraints on task sets
Timing constraints: deadline for each task,
Relative to arriving time Absolute deadline
Precedence constraints
Precedence graphs Input/output relation
Mutual exclusion Resource access protocols
Resource constraints
Scheduling Problems
Given a set of tasks (ready queue)
1. 2.
3.
Check if all deadlines can be met (schedulability check) If yes, construct a feasible schedule to meet all deadlines If yes, construct an optimal schedule e.g. minimizing response times
Tasks with the same arrival time
Assume a list of tasks (A, C1, D1)(A, C2, D2) ...(A, Cn,Dn) that arrive at the same time i.e. A
How to find a feasible schedule? (OBS: there may be many feasible schedules)
EDF [Jackson 1955]
EDF: order tasks with nondecreasing deadlines.
Example: (1,10)(2,3)(3,5)
Schedule: (2,3)(3,5)(1,10)
FACT: EDF is optimal
If EDF cannt find a feasible schedule for a task set, then no other algorithm can, which means that the task set is non schedulable.
10
EDF: Schedulability test
Order tasks in increasing order of deadlines If C1+...+Ck <=Dk for all k, the task set is schedulable Response time for task i, Ri =C1+...+Ci Prove that EDD is optimal ?
11
EDF: Examples
(2, 4)(1,5)(6,10) is schedulable:
Feasible schedule: (2,4)(1,5)(6,10) Note that (1,5)(2,4)(6,10) is also feasible
(1,10)(3,3)(2,5) is schedulable
The feasible schedule: (3,3)(2,5)(1,10) Why not shortest task first?
(4,6)(1,10)(3,5) is not schedulable
(3,5)(4,6)(1,10) is not feasible: 3+4 > 6!
12
EDF: optimality
Assume that Ri is the finishing time of task i, i.e. response time. Let Li = Ri-Di (the lateness for task i) FACT: EDF is optimal, minimizing the maximum lateness Lmax= MAXi(Li)
Note that even a task set is non schedulable, EDF may minimize the maximal lateness (minimizes e.g. the loss for soft tasks)
13
Tasks with different arrival times
Assume a list of tasks S= (A1, C1, D1)(A2,C2, D2) ...(An,Cn,Dn)
Preemptive EDF [Horn 1974]:
Whenever new tasks arrive, sort the ready queue according to earlist deadlines Run the first task of the queue
FACT: Preemptive EDF is optimal [Dertouzos 1974] in finding feasible schedules.
14
Preemptive EDF: Schedulability test
At any time, order the tasks according to EDF (A1, C1, D1) ... (Ai,Ci,Di)
If C1+...+Ck <=Dk for all k=1,2...i, then the task
set is schedulable at the moment
If S is schedulable at all time points at which tasks arrive, S is schedulable
15
Preemptive EDF: Example
Consider (1, 5, 11)(2,1,3)(3, 4,8)
Deadlines are relative to arrival times
At 1, (5,11) At 2, (1,3)(4,10) At 3, (4,8)(4,9)
16
Preemptive EDF: Optimality
Assume that Ri is the finishing time/response time of task i. Let Li = Ri-Di (the lateness for task i)
FACT: preemptive EDF is optimal in minimizing the maximum lateness Lmax= MAXi(Li)
17
Non preemptive EDF
Run a task until its finished and then sort the queue according to EDF
+ Easy to implement, less overhead (no more context switch
than necessay)
However it is not optimal, it may not find the feasible schedule even it exists.
18
Non-preemptive EDF: example
0 4
T1 A 0
T2 1
EDF Schedule
C D
4 7
2 5
Feasible Schedule
6 Missing the deadline 5!
CPU idling
19
Work-conserving Non-preemptive EDF: Optimal?
If we only consider non-idle algorithms (CPU waiting only if no tasks to run), is EDF is optimal? Unfortunately no! Example
T1= (0, 10, 100) T2= (0,1,101) T3= (1,4,4) Run T1,T3,T2: the 3rd task will miss its deadline Run T2,T3,T1: it is a feasible schedule
20
To construct optimal non-preemptive Schedule: complete search, NP-hard is needed The decision should be made according to all the parameters in the whole list of tasks The worst case is to test all possible combinations of n tasks (NP-hard, difficult for large n)
21
Practical methods: Backtrack whenever needed
Search until a non-schedulable situation occur, then backtrack [Bratleys algorithm]
simple and easy to implement but may not find a schedule if n is too big (worst case)
22
Example (Bratleys alg.)
T1 T2 T3 T4 A 4 1 1 0
T1 7 T2 6 T1 8 T3 T2 4 T3 6 T4 6 T1
6
2 2 T4 3 T2 5 T3 7 T1
C D
2 7
1 5
2 6
2 4
T2
23
Heuristic methods
Similar to Bratleys alg. But
Use heuristic function H to guide the search until a feasible schedule is found, otherwise backtrack: add a new node in the search tree if the node has smallest value according to H e.g H(task i) = Ci, Ai, Di etc [Spring alg.] However it may be difficult to find the right H
24
Example Heuristics
H(Ti) H(Ti) H(Ti) H(Ti) ...
= = = =
Ai Ci Di Di +w*Ci
FIFO SJF EDF EDF+SJF
25
EDF: + and
Preemptive EDF
Simple (+) Optimal (+) No need for computing times (+) difficult to implement efficiently (-) Need a list of timers, one per task, Overheads for context switch
Non-preemptive EDF
Minimal context switch (+) It is not optimal (-)
26
Other scheduling algorithms
Classical ones
HPF (priorities = degrees of importance of tasks) Weighted Round Robin
LRT (Latest Release Time or reverse EDF) LST (Least Slack Time first)
27
Latest Release Time (reversed EDF)
Release time = arrival time Idea: no advantage to completing any hard task sooner than necessary. We may want to postpone the execution of hard tasks e.g to improve response times for soft tasks. LRT: Schedule tasks from the latest deadline to earliest deadline. Treat deadlines as release times and arrival times as Deadlines. The latest Deadline first FACT: LRT is optimal in finding feasible schedule (for preemptive tasks)
28
LRT: Example
T1 T2 T3 A C D 0 4 11 12 3 4
T1
20
18
11
20 18 17
T2
18 17
13
11
(D=absolute deadline)
T3
17 13
Reverse time: we get the schedule: T1(9,11)T2(11,13)T3(13,17)T2(17,18)T1(18,20) OBS: from 0 to 9, soft tasks may be running!
29
LRT: + and
It needs Arrival times (-) It got to be an off-line algorithm (-) Only for preemptive tasks (-) It could optimize Response times for soft tasks (+)
30
Least slack time first (LST)
Let Si = Di-Ci (the Slack time for task i)
Si is the maximal (tolerable) time that task i can be delayed
Idea: there is no point to complete a task earlier than its deadline. Other (soft) tasks may be executed first
Slack stealing
LST: order the queue with nondecreasing slack times FACT: preemptive LST is optimal in finding feasible schedules
31
LST: Example
T1 T2 T3 A C D 0 4 8 3 9 4
T1
4 S=15-9-2=4 at 9
20 15 15
T2
8 9
S=15-13-2=0 at 13
(D=absolute deadline)
S=15-9-4=2 at 9 T3
13 9 Comment: a task should run until a Slack reaches 0 (to avoid context switch) And if more than one 0-slack: nonschedulable
17
32
LST: + and
It needs Computing times (-) Only for preemptive tasks (-) Not easy to implement! (-) But it can run on-line (+) and it may improve response times?
33
So far, we have looked at only Independent Tasks
Meaning that we can compute them in arbitrary orderings only if the orderings (schedules) are feasible All algorithms we have studied so far are applicable only to independent tasks
34
Summary: scheduling independent tasks
Task types Same arrival times Preepmtive Different arrival times EDF, Horn 74 O(n**2), Optimal LST, LRT optimal Non preemptive Different arrival times Tree search Bratley71 O(n*n!), optimal Spring, Stankovic et al 87 O(n2), Heuristic
Algorithms For Independent tasks
EDF,Jackson55 O(n log n), optimal
35
Dependent tasks
We often have conditions or constraints on tasks e.g.
A must be computed before B B must be computed before C and D
Such conditions are called precedence constraints which can be represented as Directed Acyclic Graphs (DAG) known as Precedence graphs Such graphs are also known as Task Graph
36
Dependent tasks: Examples
Input/output relation (conjunctive/disjunctive incomming edges)
Some task is waiting for output of the others, data flow diagrams
T2
sampling T1
T4
T6 T7 output
T3
T5
37
Precedence graph: Example
A must be computed before B B must be computed before C and D
A
B C
38
Precedence graph: Examples
D Not a precedence graph!
Conjunct and Disjunct join: We will only consider conjunct join!
39
AND/OR-precedence graphs
AND-node, all incomming edges must be finished first OR-node: some of the incomming edges must be finished Similarly, outgoing edges may trigger tasks in a disjunctive or conjunctive manner
40
Scheduling under Timing and Precedence constraints
Feasible schedules should meet
Timing constraints: deadlines and also Precedence constraints: Precedence graphs
Overlapping area of blue and red is what we need Precedence constraints restrict the search area (Guiding!)
Schedules satisfying Precedence constraints
All possible schedules (feasible/infeasible)
Schedules Satisfying Timing constraints
41
Dependent tasks with the same arrival times
Assume a list of tasks: (A,C1,D1)(A,C2,D2) ...(A,Cn,Dn) In addition to the deadlines D1...Dn, the tasks are also constrained by a DAG Solution: Latest Deadline First (LDF), Lawler 1973 FACT: LDF is optimal (in finding feasible schedules)
42
Latest Deadline First (LDF)
It constructs a schedule from tail to head using a queue:
1.
Pick up a task from the current DAG, that
Has the latest deadline and Does not precede any other tasks (a leaf!)
2.
Remove the selected task from the DAG and put it to the queue
Repeat the two steps until the DAG contains no more tasks. Then the queue is a potentilly feasible schedule. The last task selected should be run first. Note that this is similar to LRT
43
LDF: Example
T1 2
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
T4 3
T2 5
T3 4
T5 5
T6 6
44
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
T2 5 T1 2
T3 4
T4 3
T5 5
T6 6
LDF: T6
45
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
T2 5 T1 2
T3 4
T4 3
T5 5
LDF: T6
46
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
T2 5 T1 2
T3 4
T4 3
T5 5
LDF: T6,T5
47
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
T2 5 T1 2
T3 4
T4 3
LDF: T6,T5
48
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
T2 5 T1 2
T4 3
LDF: T6,T5,T3
49
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
T2 5 T1 2
LDF: T6,T5,T3,T4
50
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
T1 2
LDF: T6,T5,T3,T4,T2
51
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
LDF: T6,T5,T3,T4,T2,T1
52
LDF: Example
T1 T2 T3 T4 T5 T6 C D 1 2 1 5 1 4 1 3 1 5 1 6
LDF: T6,T5,T3,T4,T2,T1
Feasible Schedule
53
Earlest Deadline First (EDF)
It is a variant of LDF, but start with the root of the DAG:
1.
2.
Pick up a task with earlest deadline among all nodes that have no fathers (the roots) Remove the selected task from the DAG and put it to the queue
Repeat the two steps until the DAG contains no more tasks. Then the queue is a feasible schedule.
Unfortunately, EDF is not optimal
The earliest deadline now may lead to longer deadline in future (see the following example)
54
LDF: Example
T1 2
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
T4 3
T2 5
T3 4
T5 5
T6 6
55
LDF: Example
T1 2
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
T4 3
T2 5
T3 4
T5 5
T6 6
EDF: T1
56
EDF: Example
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
T4 3
T2 5
T3 4
T5 5
T6 6
EDF: T1
57
LDF: Example
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
T4 3
T2 5
T5 5
T6 6
EDF: T1,T3
58
LDF: Example
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
T4 3 T5 5 T6 6
EDF: T1,T3,T2
59
LDF: Example
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
EDF: T1,T3,T2,T4,T5,T6
60
LDF: Example
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5
1
4
1
3
1
5
1
6
T4 will miss its Deadline: 3
LDF: T6,T5,T3,T4,T2,T1
Feasible
EDF: T1,T3,T2,T4,T5,T6
Infeasible
61
Dependent tasks with different arrival times
Assume a list of tasks: S = (A1,C1,D1)(A2,C2,D2)...(A3,Cn,Dn) In addition to the deadlines D1...Dn, the tasks are also constrained by a DAG Solution: Complete Search
The Bratleys algorithm (search and backtrack whenever needed)
62
Better algorithms?
Assume a list of tasks: S = (A1,C1,D1)(A2,C2,D2)...(A3,Cn,Dn) In addition to the deadlines D1...Dn, the tasks are also constrained by the task graph Idea:
Transform the task set S to an Independent task set S* such that S is schedulable under DAG iff S* is schedulable
63
Idea: how to transform S to S*?
Idea: If Ti ->Tj is in the DAG i.e. Ti must be executed before Tj, we replace the arrival time for Tj and deadline for Ti with
Aj* = max(Aj, Ai+Ci)
Tj can not be computed before the completion of Ti
Ti should be finished early enough to meet the deadline for Tj
Di*=min(Di,Dj-Cj)
64
Algorithm (EDF*): transform S to S*
Let arrival times and deadlines be absolute times Step 1: Transform the arrival times from roots to leafs
For all initial (root) nodes Ti, let Ai* = Ai REPEAT:
Pick up a node Tj whose fathers arrival times have been modified. If no such node, stop. Otherwise: Let Aj* =max(Aj, max{Ai*+Ci: Ti->Tj})
Step 2: Transform the deadlines from leafs to roots
For all terminal (leafs) nodes Tj, let Dj* = Dj REPEAT:
Pick up a node Ti all whose sons deadlines have been modified. If no such node, stop. Otherwise: Let Di* =min(Di, min{Dj*-Cj: Ti->Tj})
Step 3: use EDF to schedule S*=(A1*,C1,D1*)...(An*.Cn,Dn*)
65
EDF*: optimality
FACT:
S is schedulable under a DAG iff S* is schedulable EDF* is optimal in finding a feasible schedule
66
Example
T1 2
T1 T2 T3 T4 T5 T6 C
D A
1
2 0
1
5 1
1
4 0
1
3 2
1
5 1
1
6 0
T4 3
T2 5
T3 4
T5 5
T6 6
67
EDF*: Example(1)
T1 2
T1 T2 T3 T4 T5 T6 C
D A
1
2 0
1
5 1
1
4 0
1
3 2
1
5 1
1
6 0
T4 3
T2 5
T3 4
T5 5
T6 6
Step 1: Modifying the arrival times (top-down)
68
EDF*: Example(1)
T1 2
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5 1
1
4 1
1
3 2
1
5 2
1
6 2
T4 3
T2 5
T3 4
A* 0
T5 5
T6 6
Step 1: Modifying the arrival times (top-down)
69
EDF*: Example(2)
T1 2(1)
T1 T2 T3 T4 T5 T6 C
D
1
2
1
5 1
1
4 1
1
3 2
1
5 2
1
6 2
T4 3(3)
T2 5(2)
T3 4(4)
A* 0
T5 5(5)
T6 6(6)
Step 2: Modifying the deadlines (bottom-up)
70
EDF*: Example(2)
S*
T1 T2 T3 T4 T5 T6
T1 2(1)
1 2
1 4
1 3
1 5
1 6
D* 1
T2 5(2)
T3 4(4)
A* 0
2
T4 3(3) T5 5(5) T6 6(6)
Step 2: Modifying the deadlines (bottom-up)
71
EDF*: Example(3)
S*
T1 T2 T3 T4 T5 T6
T1 2(1)
1 2
1 4
1 3
1 5
1 6
D* 1
T2 5(2)
T3 4(4)
A* 0
2
T4 3(3) T5 5(5) T6 6(6)
Step 3: now we dont need the DAG any more!
72
EDF*: Example(3)
S*
T1 T2 T3 T4 T5 T6
1 2
1 4
1 3
1 5
1 6
D* 1
A* 0
Step 3: schedule S* using EDF
73
EDF*: Example(3)
S*
T1 T2 T3 T4 T5 T6
1 2
1 4
1 3
1 5
1 6
D* 1
A* 0
Finally we have a schedule: T1,T2,T4,T3,T5,T6
74
Summary: scheduling aperiodic tasks
Task types Same arrival times Preepmtive Different arrival times Non preemptive Different arrival times
Algorithms for EDF,Jackson55 Independent O(n log n), optimal tasks
EDF, Horn 74 O(n**2), Optimal LST, optimal LRT, optimal EDF* Chetto et al 90 O(n**2) optimal
Tree search Bratley71 O(n n!), optimal Spring, Stankovic et al 87 O(n**2) Heuristic As above
Algorithms for Dependent tasks
LDF, Lawler 73 O(n**2) Optimal
75
More about TASK GRAPH
Acyclic graphs or Trees where
Nodes are computation tasks Edges are communication links Each node is characterized by resource requirements and local deadline Each edge may have a communication delay End-to-End deadline: root to leaf
Constraints on task graphs
How to implement a Task graph?
Single processor systems (communication delay = 0) Multiprocessor systems?
Communication bus e.g. CAN BUS Shared memory, memory hiearchy Network-on-Chip
76
Example: task graph with communication delays
3
T2 5 T1 2
T1 T2 T3 T4 T5 T6 C
D
1
T3 4
1
2
1
5
1
4
1
3
1
5
1
6
T4 3
T5 5
T6 6
77
Example: task graph with communication delays
3
T2 5 T1 2
T1 T2 T3 T4 T5 T6 C
D
1
T3 4
1
2
1
5
1
4
1
3
1
5
1
6
T4 3
5
T5 5 T6 6
You may have to schedule the communication bandwidth
T7 13 78
