Outline

• Real-time systems

• Real-time scheduling algorithms

– Fixed-priority algorithm (RM)
– Dynamic-priority algorithm (EDF)
 Real-Time Systems
• Definition
– Systems whose correctness depends on their temporal
aspects as well as their functional aspects

• Performance measure
– Timeliness on timing constraints (deadlines)
– Speed/average case performance are less significant.

• Key property
– Predictability on timing constraints
 Real-Time System Example
• Digital control systems
– periodically performs the following job:

senses the system status and

actuates the system according to its current status

Sensor
Control-Law
Computation
Actuator
 Real-Time Workload
• Job (unit of work)
– a computation, a file read, a message transmission, etc
• Attributes
– Resources required to make progress
– Timing parameters

Absolute
Released deadline
Execution time

Relative deadline
 Real-Time Task
• Task : a sequence of similar jobs
– Periodic task (p,e)
• Its jobs repeat regularly
• Period p = inter-release time (0 < p)
• Execution time e = maximum execution time (0 < e < p)
• Utilization U = e/p

0 5 10 15
 Deadlines: Hard vs. Soft
• Hard deadline
– Disastrous or very serious consequences may occur if
the deadline is missed
– Validation is essential : can all the deadlines be met,
even under worst-case scenario?
– Deterministic guarantees

• Soft deadline
– Ideally, the deadline should be met for maximum
performance. The performance degrades in case of
deadline misses.
– Best effort approaches / statistical guarantees
 Schedulability
• Property indicating whether a real-time system (a set
of real-time tasks) can meet their deadlines

(4,1)

(5,2)

(7,2)
 Real-Time Scheduling
• Determines the order of real-time task executions
• Static-priority scheduling
• Dynamic-priority scheduling

(4,1)

(5,2)
5 10 15
(7,2)
5 10 15
 RM (Rate Monotonic)
• Optimal static-priority scheduling
• It assigns priority according to period
• A task with a shorter period has a higher priority
• Executes a job with the shortest period

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 RM (Rate Monotonic)
• Executes a job with the shortest period

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 RM (Rate Monotonic)
• Executes a job with the shortest period

Deadline Miss !

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 Response Time
• Response time
– Duration from released time to finish time

T1 (4,1)

T2 (5,2)
5 10 15
T3 (10,2)
5 10 15
 Response Time
• Response time
– Duration from released time to finish time

Response Time

T1 (4,1)

T2 (5,2)
5 10 15
T3 (10,2)
5 10 15
 Response Time
• Response Time (ri) [Audsley et al., 1993]
 ri 
ri  ei      ek
TkHP (Ti )  pk 

• HP(Ti) : a set of higher-priority tasks than Ti

T1 (4,1)

T2 (5,2)
5 10
T3 (10,2)
5 10
 RM - Schedulability Analysis
• Real-time system is schedulable under RM
if and only if ri ≤ pi for all task Ti(pi,ei)

Joseph & Pandya,

“Finding response times in a real-time system”,
The Computer Journal, 1986.
 RM – Utilization Bound
• Real-time system is schedulable under RM if
∑Ui ≤ n (21/n-1)

Liu & Layland,

“Scheduling algorithms for multi-programming in a
hard-real-time environment”, Journal of ACM, 1973.
 RM – Utilization Bound
• Real-time system is schedulable under RM if
∑Ui ≤ n (21/n-1)

• Example: T1(4,1), T2(5,1), T3(10,1),

∑Ui = 1/4 + 1/5 + 1/10

= 0.55
3 (21/3-1) ≈ 0.78

Thus, {T1, T2, T3} is schedulable under RM.

 RM – Utilization Bound
• Real-time system is schedulable under RM if
∑Ui ≤ n (21/n-1)

RM Utilization Bounds
1.1
1
Utilization

0.9
0.8
0.7
0.6
0.5
1 4 16 64 256 1024 4096

The Number of Tasks

 EDF (Earliest Deadline First)
• Optimal dynamic priority scheduling
• A task with a shorter deadline has a higher priority
• Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
• Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
• Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
• Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
• Optimal scheduling algorithm
– if there is a schedule for a set of real-time tasks,
EDF can schedule it.

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 Processor Demand Bound
• Demand Bound Function : dbf(t)
– the maximum processor demand by workload over any
interval of length t
t

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF - Schedulability Analysis
• Real-time system is schedulable under EDF
if and only if dbf(t) ≤ t for all interval t

Baruah et al.
“Algorithms and complexity concerning the preemptive
scheduling of periodic, real-time tasks on one
processor”, Journal of Real-Time Systems, 1990.

• Demand Bound Function : dbf(t)

– the maximum processor demand by workload over any
interval of length t
 EDF – Utilization Bound
• Real-time system is schedulable under EDF if and only
if
∑Ui ≤ 1

Liu & Layland,

“Scheduling algorithms for multi-programming in a
hard-real-time environment”, Journal of ACM, 1973.
 EDF – Overload Conditions
• Domino effect during overload conditions
– Example: T1(4,3), T2(5,3), T3(6,3), T4(7,3)

Deadline Miss !

T1 T2 T3 T4
0 3 5 6 7
Better schedules :

T1 T3 T1 T4
0 3 5 6 7 0 3 5 6 7
 RM vs. EDF
• Rate Monotonic
– Simpler implementation, even in systems without explicit
support for timing constraints (periods, deadlines)
– Predictability for the highest priority tasks

• EDF
– Full processor utilization
– Misbehavior during overload conditions

• For more details: Buttazzo, “Rate monotonic vs. EDF:

Judgement Day”, EMSOFT 2003.