Scheduling of Real-Time Systems
Real-time Systems Course
Gerhard Fohler
Real-Time Systems © Gerhard Fohler 2006 1
Overview
• Task states, life cycle
• Temporal definition of task, utilization
• Schedulability and scheduling policies
Real-Time Systems © Gerhard Fohler 2006 2
Lifecycle of task
executing
waiting ready
blocked
dormant
Real-Time Systems © Gerhard Fohler 2006 3
Task States
• Dormant • Ready
sleeping, task is in the Task can execute when
system, but not considered the dispatcher decides so;
for execution it is compete with other
event or period, or ready tasks for CPU
scheduling decision may • Executing (running)
“wake” him Uses CPU
• Waiting • Blocked
Task is waiting for event Task cannot execute
because it is waiting for
resources
Real-Time Systems © Gerhard Fohler 2006 4
Temporal Definition of Periodic Task
A periodic task can be described, for example, by 4
parameters:
• Ti period of task i
• Ri release time, relative from start of period
time at which task i may start to execute
• Di deadline interval, relative from start of period
time at which task i must be completed
• Ci worst case execution time
Real-Time Systems © Gerhard Fohler 2006 5
Utilization
• Portion of CPU needed for execution of a task set
• utilization of single task i
Ci
Ui =
Ti
• utilization of task set with n tasks
C 0 C1 Cn − 1 n −1 Ci
U= + + ... + =∑
T 0 T1 Tn − 1 i = 0 Ti
Real-Time Systems © Gerhard Fohler 2006 6
Utilization - Example
Task T C
A 10 1
B 4 1
C 2 1
Real-Time Systems © Gerhard Fohler 2006 7
Schedulability
Def.: A task set is schedulable, when all tasks meet their
deadlines during the lifetime of the task set (system).
• Can we say anything about schedulability yet?
Real-Time Systems © Gerhard Fohler 2006 8
Schedulability condition
• necessary condition
– has to hold, otherwise taskset for sure not schedulable
– but: if it holds, does not mean automatically that it is
schedulable
– if it does not hold, cannot be schedulable
U ≤1
Real-Time Systems © Gerhard Fohler 2006 9
Scheduling Policies
First Come First Serve
• CPU given to tasks in reverse order of request arrival
– CPU held by task until it finishes
– non preemptive
Real-Time Systems © Gerhard Fohler 2006 10
Scheduling Policies
• Time sliced
– CPU given to each task for a certain amount of time
– has to be preemptive
– assignment of slices to task with other policies
• e.g., round robin (RR) – time sliced plus FCFS
• TDMA on network
Real-Time Systems © Gerhard Fohler 2006 11
Scheduling Policies
• priority based
– priorities assigned to tasks
– task with highest priority gets CPU next
• if preemptiv: executes
• if non preemptiv: after current CPU holder stops
• prioties same during lifetime:
fixed priority FPS
• priorities may change during lifetime:
dynamic priority DPS
Real-Time Systems © Gerhard Fohler 2006 12
Scheduling Anamolies
• given task set
– optimally scheduled on multiprocessor
– priority assignment
– fixed number of processors
– fixed execution times
– precedence constraints
• what happens to response time if
– number of processors increased
– execution times decreased
– weakening precedence constraints
Real-Time Systems © Gerhard Fohler 2006 13
• more resources – shorter times
• always?
• Graham 1976
– can also increase response times
• if tasks have deadlines, adding resources does not
automatically help, it can get worse
Real-Time Systems © Gerhard Fohler 2006 14
J1 J9
J8
J2
precedence
J1 -> J9 J7
J4 -> J5 J3
J4 -> J6
J6
J4 –> J7
J4 -> J8
J4 J5
priority (Ji) > priority (Jk), i<k
Real-Time Systems © Gerhard Fohler 2006 15
precedence
J1 -> J9
J4 -> J5
J4 -> J6
J4 –> J7
J4 -> J8
J1 J9
J2 J4 J5 J7
J3 J6 J8
Real-Time Systems © Gerhard Fohler 2006 16
precedence
more processors J1 -> J9
J4 -> J5
J4 -> J6
J1 J8 J4 –> J7
J4 -> J8
J2 J5 J9
J3 J6
J4 J7
Real-Time Systems © Gerhard Fohler 2006 17
precedence
reduced computation times J1 -> J9
J4 -> J5
J4 -> J6
J4 –> J7
J4 -> J8
J1 J5 J8
J2 J4 J6 J9
J3 J7
Real-Time Systems © Gerhard Fohler 2006 18
precedence
weakend precedence constr. J1 -> J9
J4 -> J5
J4 -> J6
J4 –> J7
J4 -> J8
J1 J8 J9
J2 J4 J5
J3 J7 J6
Real-Time Systems © Gerhard Fohler 2006 19
precedence
more processors J1 -> J9
J4 -> J5
J4 -> J6
J4 –> J7
J4 -> J8
J1 J9
J2 J4 J5 J7
J3 J6 J8
Real-Time Systems © Gerhard Fohler 2006 20