Real-Time Scheduling
Formal Model
[Some parts of this lecture are based on a real-time systems course
of Colin Perkins
http://csperkins.org/teaching/rtes/index.html]
1
Real-Time Scheduling – Formal Model
Introduce an abstract model of real-time systems
abstracts away unessential details
sets up consistent terminology
Three components of the model
A workload model that describes applications supported by
the system
i.e. jobs, tasks, ...
A resource model that describes the system resources
available to applications
i.e. processors, passive resources, ...
Algorithms that define how the application uses the
resources at all times
i.e. scheduling and resource access protocols
2
Basic Notions
A job is a unit of work that is scheduled and executed by
a system
compute a control law, transform sensor data, etc.
A task is a set of related jobs which jointly provide some
system function
check temperature periodically, keep a steady flow of water
A job executes on a processor
CPU, transmission link in a network, database server, etc.
A job may use some (shared) passive resources
file, database lock, shared variable etc.
3
Life Cycle of a Job
READY RUN
WAITING
COMPL.
scheduling
preemption
wait for a busy
resource
signal free
resource
release
completed
4
Jobs – Parameters
We consider finite, or countably infinte number of jobs J1, J2, . . .
Each job has several parameters.
There are four types of job parameters:
temporal
release time, execution time, deadlines
functional
Laxity type: hard and soft real-time
preemptability, (criticality)
interconnection
precedence constraints
resource
usage of processors and passive resources
5
Job Parameters – Execution Time
Execution time ei of a job Ji – the amount of time required to
complete the execution of Ji when it executes alone and has all
necessary resources
Value of ei depends upon complexity of the job and speed of the
processor on which it executes; may change for various reasons:
Conditional branches
Caches, pipelines, etc.
...
Execution times fall into an interval [e−
i
, e+
i
]; we assume that
we know this interval (WCET analysis) but not necessarily ei
We usually validate the system using only e+
i
for each job
i.e. assume ei = e+
i
6
Job Parameters – Release and Response Time
Release time ri – the instant in time when a job Ji becomes
available for execution
Release time may jitter, only an interval [r−
i
, r+
i
] is known
A job can be executed at any time at, or after, its release time,
provided its processor and resource demands are met
Completion time Ci – the instant in time when a job completes
its execution
Response time – the difference Ci − ri between the completion
time and the release time
Time
Ji Ji
r−
i r+
i
Release time ri Completion time Ci
Response time
7
Job Parameters – Deadlines
Absolute deadline di – the instant in time by which a job must
be completed
Relative deadline Di – the maximum allowable response time
i.e. Di = di − ri
Feasible interval is the interval (ri, di]
Time
Ji Ji
r−
i r+
i
Release time ri
Completion time Ci
Response time
Absolute deadline di
Rel. deadline Di
A timing constraint of a job is specified using release time
together with relative and absolute deadlines. 8
Laxity Type – Hard Real-Time
A hard real-time constraint specifies that a job should never
miss its deadline.
Examples: Flight control, railway signaling, anti-lock brakes, etc.
Several more precise definitions occur in literature:
A timing constraint is hard if the failure to meet it is considered
a fatal error
e.g. a bomb is dropped too late and hits civilians
A timing constraint is hard if the usefulness of the results falls off
abruptly (may even become negative) at the deadline
Here the nature of abruptness allows to soften the constraint
Definition 1
A timing constraint is hard if the user requires formal validation
that the job meets its timing constraint.
9
Laxity Type – Soft Real-Time
A soft real-time constraint specifies that a job could
occasionally miss its deadline
Examples: stock trading, multimedia, etc.
Several more precise definitions occur in literature:
A timing constraint is soft if the failure to meet it is undesirable
but acceptable if the probability is low
A timing constraint is soft if the usefulness of the results
decreases at a slower rate with tardiness of the job
e.g. the probability that a response time exceeds 50 ms is less than 0.2
Definition 2
A timing constraint is soft if either validation is not required, or
only a demonstration that a statistical constraint is met suffices.
10
Jobs – Preemptability
Jobs may be interrupted by higher priority jobs
A job is preemptable if its execution can be interrupted
A job is non-preemptable if it must run to completion once
started
(Some preemptable jobs have periods during which they cannot be
preempted)
The context switch time is the time to switch between jobs
(Most of the time we assume that this time is negligible)
Reasons for preemptability:
Jobs may have different levels of criticality
e.g. brakes vs radio tunning
Priorities may make part of scheduling algorithm
e.g. resource access control algorithms
11
Jobs – Precedence Constraints
Jobs may be constrained to execute in a particular order
This is known as a precedence constraint
A job Ji is a predecessor of another job Jk and Jk a
successor of Ji (denoted by Ji < Jk ) if Jk cannot begin
execution until the execution of Ji completes
Ji is an immediate predecessor of Jk if Ji < Jk and there is
no other job Jj such that Ji < Jj < Jk
Ji and Jk are independent when neither Ji < Jk nor Jk < Ji
A job with a precedence constraint becomes ready for
execution when its release time has passed and when all
predecessors have completed.
Example: authentication before retrieving an information, a signal
processing task in radar surveillance system precedes a tracker task
12
Tasks – Modeling Reactive Systems
Reactive systems – run for unlimited amount of time
A system parameter: number of tasks
may be known in advance (flight control)
may change during computation (air traffic control)
We consider three types of tasks
Periodic – jobs executed at regular intervals, hard deadlines
Aperiodic – jobs executed in random intervals, soft deadlines
Sporadic – jobs executed in random intervals, hard deadlines
... precise definitions later.
13
Processors
A processor, P, is an active component on which jobs are scheduled
The general case considered in literature:
m processors P1, . . . , Pm, each Pi has its type and speed.
We mostly concentrate on single processor scheduling
Efficient scheduling algorithms
In a sense subsumes multiprocessor scheduling where tasks are
assigned statically to individual processors
i.e. all jobs of every task are assigned to a single processor
Multi-processor scheduling is a rich area of current research, we
touch it only lightly (later).
14
Resources
A resource, R, is a passive entity upon which jobs may depend
In general, we consider n resources R1, . . . , Rn of distinct types
Each Ri is used in a mutually exclusive manner
A job that acquires a free resource locks the resource
Jobs that need a busy resource have to wait until the resource is
released
Once released, the resource may be used by another job
(i.e. it is not consumed)
(More generally, each resource may be used by k jobs concurrently, i.e., there are k
units of the resource)
Resource requirements of a job specify
which resources are used by the job
the time interval(s) during which each resource is required
(precise definitions later)
15
Scheduling
Schedule assigns, in every time instant, processors and
resources to jobs.
More formally, a schedule is a function
σ : {J1, . . .} × R+
0
→ P({P1, . . . , Pm, R1, . . . , Rn})
so that for every t ∈ R+
0
there are rational 0 ≤ t1 ≤ t ≤ t2 such
that σ(Ji, ·) is constant on [t1, t2).
(We also assume that there is the least time quantum in which scheduler
does not change its decisions, i.e. each of the intervals [t1, t2) is larger than a
fixed ε > 0.)
16
Valid and Feasible Schedule
A schedule is valid if it satisfies the following conditions:
Every processor is assigned to at most one job at any time
Every job is assigned to at most one processor at any time
No job is scheduled before its release time
The total amount of processor time assigned to a given job is
equal to its actual execution time
All the precedence and resource usage constraints are satisfied
A schedule is feasible if all jobs with hard real-time constraints
complete before their deadlines
A set of jobs is schedulable if there is a feasible schedule for
the set.
17
Scheduling – Algorithms
Scheduling algorithm computes a schedule for a set of jobs
A set of jobs is schedulable according to a scheduling algorithm
if the algorithm produces a feasible schedule
Sometimes efficiency of scheduling algorithms is measured using
a cost function:
the maximum/average response time
the maximum/average lateness – the difference between the
completion time and the absolute deadline, i.e. Ci − di
miss rate – the percentage of jobs that are executed but
completed too late
...
Definition 3
A scheduling algorithm is optimal if it always produces
a feasible schedule whenever such a schedule exists,
and if a cost function is given, minimizes the cost. 18
Real-Time Scheduling
Individual Jobs
19
Scheduling of Individual Jobs
We start with scheduling of finite sets of jobs {J1, . . . , Jm} for
execution on single processor systems
Each Ji has a release time ri, an execution time ei and
a relative deadline Di.
We assume hard real-time constraints
The question: Is there an optimal scheduling algorithm?
We proceed in the direction of growing generality:
1. No resources, independent, synchronized (i.e. ri = 0 for all i)
2. No resources, independent but not synchronized
3. No resources but possibly dependent
4. The general case
20
No resources, Independent, Synchronized
J1 J2 J3 J4 J5
ei 1 1 1 3 2
di 3 10 7 8 5
Is there a feasible schedule? Minimize maximal lateness.
Note: Preemption does not help in synchronized case
Theorem 4
If there are no resource contentions, then executing independent jobs
in the order of non-decreasing deadline (EDD) produces a feasible
schedule (if it exists) and minimizes the maximal lateness (always).
Proof.
Any feasible schedule σ can be transformed in finitely many steps to
EDD schedule whose lateness is ≤ the lateness of σ (whiteboard).
Is there any simple schedulability test?
{J1, . . . , Jn} where d1 ≤ · · · ≤ dn is schedulable iff
∀i ∈ {1, . . . , n} : i
k=1 ek ≤ di 21
No resources, Independent (No Synchro)
J1 J2 J3
ri 0 0 2
ei 1 2 2
di 2 5 4
find a (feasible) schedule (with and without preemption)
determine response time of each job in your schedule
determine lateness of each job in your schedule (is the
maximal lateness minimized?)
Recall that lateness of Ji is equal to Ci − di
Preemption makes a difference
22
No resources, Independent (No Synchro)
Earliest Deadline First (EDF) scheduling:
At any time instant, a job with the earliest absolute deadline is
executed
Here EDF works in the preemptive case but not in
the non-preemptive one.
J1 J2
ri 0 1
ei 4 2
di 7 5
23
No Resources, Dependent (No Synchro)
Theorem 5
If there are no resource contentions, jobs are independent and
preemption is allowed, the EDF algorithm finds a feasible
schedule (if it exists) and minimizes the maximal lateness.
Proof.
We show that any feasible schedule σ can be transformed in finitely
many steps to EDF schedule which is feasible and whose lateness is
≤ the lateness of σ.
Let σ be a feasible schedule but not EDF. Assume, w.l.o.g., that for
every k ∈ N at most one job is executed in the interval [k, k + 1) and
that all release times and deadlines are in N.
(Otherwise rescale by the least common multiple.)
24
No Resources, Dependent (No Synchro)
Proof cont.
We say that σ violates EDF at k if there are two jobs Ja and Jb
that satisfy:
Jb is executed in [k, k + 1)
Ja is executed in [ , + 1) for > k
da < db
We say that Ja and Jb witness the violation.
Let k ∈ N be the least time instant such that σ violates EDF at
k as witnessed by jobs Ja and Jb.
Assume, w.l.o.g. that Ja has the minimum deadline among all
jobs ready for execution at k.
Let us define a new schedule σ which is the same as σ except:
executes Ja in [k, k + 1)
executes Jb in [ , + 1)
Then σ does not violate EDF at any k ≤ k.
So finitely many transformations transform any feasible
schedule to EDF. 25
No resources, Independent (No Synchro)
The non-preemptive case is NP-hard.
Heuristics are needed, such as the Spring algorithm, that
usually work in much more general setting (with resources etc.)
Use the notion of partial schedule where only a subset of tasks
has been scheduled.
Exhaustive search through partial schedules
start with an empty schedule
in every step either
add a job which maximizes a heuristic function H among
jobs that have not yet been tried in this partial schedule
or backtrack if there is no such a job
After failure, backtrack to previous partial schedule
Heuristic function identifies plausible jobs to be scheduled
(earliest release, earliest deadline, etc.)
26
No resources, Dependent (No Synchro)
Theorem 6
Assume that there are no resource contentions and jobs are
preemptable. There is a polynomial time algorithm which decides
whether a feasible schedule exists and if yes, then computes one.
Idea: Reduce to independent jobs by changing release times
and deadlines. Then use EDF.
Observe that if Ji < Jk then replacing
rk with max{rk , ri + ei}
(Jk cannot be scheduled for execution before ri + ei because Ji cannot
be finished before ri + ei)
di with min{di, dk − ek }
(Ji must be finished before dk − ek so that Jk can be finished before dk )
does not change feasibility.
Replace systematically according to the precedence relation.
27
No Resources, Dependent (No Synchro)
Define r∗
k
, d∗
k
systematically as follows:
Pick Jk whose all predecessors have been processed and
compute r∗
k
:= max{rk , maxJi <Jk
r∗
i
+ ei}. Repeat for all jobs.
Pick Jk whose all successors have been processed and
compute d∗
k
:= min{dk , minJk <Ji
d∗
i
− ei}. Repeat for all jobs.
This gives a new set of jobs J∗
1
, . . . , J∗
m where each J∗
k
has the
release time r∗
k
and the absolute deadline d∗
k
.
We impose no precedence constraints on J∗
1
, . . . , J∗
m.
Lemma 7
{J1, . . . , Jm} is feasible iff {J∗
1
, . . . , J∗
m} is feasible. If EDF schedule
is feasible on {J∗
1
, . . . , J∗
m}, then the same schedule is feasible
on {J1, . . . , Jm}.
The same schedule means that whenever J∗
i
is scheduled at time t, then Ji is
scheduled at time t.
28
No Resources, Dependent (No Synchro)
Recall: r∗
k
:= max{rk , maxJi<Jk
r∗
i
+ ei} and
d∗
k
:= min{dk , minJk <Ji
d∗
i
− ei}
Proof of Lemma 7.
⇒: It is easy to show that in no feasible schedule on {J1, . . . , Jm} any
job Jk can be released before r∗
k
and completed before d∗
k
(otherwise,
precedence constraints would be violated). ⇐: Assume that EDF
σ is feasible on {J∗
1
, . . . , J∗
m}. Let us use σ on {J1, . . . , Jm}.
I.e. Ji is executed iff J∗
i
is executed.
Timing constraints of {J1, . . . , Jm} are satisfied since rk ≤ r∗
k
and
dk ≥ d∗
k
for all k.
Precedence constraints: Assume that Js < Jt . Then J∗
s
executes completely before J∗
t
since r∗
s < r∗
s + es ≤ r∗
t
and
d∗
s ≤ d∗
t
− et < d∗
t
and σ is EDF on {J∗
1
. . . , J∗
m}.
29
No Resources, Dependent (No Synchro)
J1 J2 J3 J4 J5 J6
ei 1 1 1 1 1 1
di 2 5 4 3 5 6
Dependencies:
J1
J2 J3
J4 J5 J6
Find a feasible schedule.
Recall: r∗
k
:= max{rk , maxJi<Jk
r∗
i
+ ei} and
d∗
k
:= min{dk , minJk <Ji
d∗
i
− ei}
30
Resources, Dependent, Not Synchronized
Even the preemptive case is NP-hard
reduce the non-preemptive case without resources to the
preemptive with resources
Use a common resource R.
Whenever a job starts its execution it locks the resource R.
Whenever a job finishes its execution it releases the
resourse R.
Could be solved using heuristics, e.g. the Spring algorithm.
31
Real-Time Scheduling
Scheduling of Reactive Systems
[Some parts of this lecture are based on a real-time systems course
of Colin Perkins
http://csperkins.org/teaching/rtes/index.html]
32
Reminder of Basic Notions
Jobs are executed on processors and need resources
Parameters of jobs
temporal:
release time – ri
execution time – ei
absolute deadline – di
derived params: relative deadline (Di), completion time,
response time, ...
functional:
laxity type: hard vs soft
preemptability
interconnection
precedence constraints (independence)
resource
what resources and when are used by the job
Tasks = sets of jobs
33
Reminder of Basic Notions
Schedule assigns, in every time instant, processors and
resources to jobs
valid schedule = correct (common sense)
Feasible schedule = valid and all hard real-time tasks meet
deadlines
Set of jobs is schedulable if there is a feasible schedule for it
Scheduling algorithm computes a schedule for a set of jobs
Scheduling algorithm is optimal if it always produces a feasible
schedule whenever such a schedule exists, and if a cost function
is given, minimizes the cost
34
Scheduling Reactive Systems
We have considered scheduling of individual jobs
From this point on we concentrate on reactive systems
i.e. systems that run for unlimited amount of time
Recall that a task is a set of related jobs that jointly provide
some system function.
We consider various types of tasks
Periodic
Aperiodic
Sporadic
Differ in execution time patterns for jobs in the tasks
Must be modeled differently
Differing scheduling algorithms
Differing impact on system performance
Differing constraints on scheduling
35
Periodic Tasks
A set of jobs that are executed repeatedly at regular time
intervals can be modeled as a periodic task
Time
Ji,1
ri,1
Ji,2
ri,2
Ji,3
ri,3
Ji,4
ri,4
· · ·
ϕi
Each periodic task Ti is a sequence of jobs
Ji,1, Ji,2, . . . Ji,n, . . .
The phase ϕi of a task Ti is the release time ri,1 of the first
job Ji,1 in the task Ti ;
tasks are in phase if their phases are equal
The period pi of a task Ti is the minimum length of all time
intervals between release times of consecutive jobs in Ti
The execution time ei of a task Ti is the maximum execution
time of all jobs in Ti
The relative deadline Di is relative deadline of all jobs in Ti
(The period and execution time of every periodic task in the system are
known with reasonable accuracy at all times)
36
Periodic Tasks – Notation
The 4-tuple Ti = (ϕi, pi, ei, Di) refers to a periodic task Ti with phase
ϕi, period pi, execution time ei, and relative deadline Di
For example: jobs of T1 = (1, 10, 3, 6) are
released at times 1, 11, 21, . . .,
execute for 3 time units,
have to be finished in 6 time units (the first by 7, the second by 17, ...)
Default phase of Ti is ϕi = 0 and default relative deadline is di = pi
T2 = (10, 3, 6) satisfies ϕ = 0, pi = 10, ei = 3, Di = 6, i.e. jobs of T2 are
released at times 0, 10, 20, . . .,
execute for 3 time units,
have to be finished in 6 time units (the first by 6, the second by 16, ...)
T3 = (10, 3) satisfies ϕ = 0, pi = 10, ei = 3, Di = 10, i.e. jobs of T3 are
released at times 0, 10, 20, . . .,
execute for 3 time units,
have to be finished in 10 time units (the first by 10, the second by 20, ...)
37
Periodic Tasks – Hyperperiod
The hyper-period H of a set of periodic tasks is the least
common multiple of their periods
If tasks are in phase, then H is the time instant after which the pattern of job
release/execution times starts to repeat
0 5 10 15 20 25 30
H H
38
Aperiodic and Sporadic Tasks
Many real-time systems are required to respond to
external events
The tasks resulting from such events are sporadic and
aperiodic tasks
Sporadic tasks – hard deadlines of jobs
e.g. autopilot on/off in aircraft
Aperiodic tasks – soft deadlines of jobs
e.g. sensitivity adjustment of radar surveilance system
Inter-arrival times between consecutive jobs are identically
and independently distributed according to a probability
distribution A(x)
Execution times of jobs are identically and independently
distributed according to a probability distribution B(x)
In the case of sporadic tasks, the usual goal is to decide,
whether a newly released job can be feasibly scheduled with
the remaining jobs in the system
In the case of aperiodic tasks, the usual goal is to minimize the
average response time 39
Scheduling – Classification of Algorithms
Off-line vs Online
Off-line – sched. algorithm is executed on the whole task
set before activation
Online – schedule is updated at runtime every time a new
task enters the system
Optimal vs Heuristic
Optimal – algorithm computes a feasible schedule and
minimizes cost of soft real-time jobs
Heuristic – algorithm is guided by heuristic function; tends
towards optimal schedule, may not give one
The main division is on
Clock-Driven
Priority-Driven
40
Scheduling – Clock-Driven
Decisions about what jobs execute when are made at specific
time instants
these instants are chosen before the system begins
execution
Usually regularly spaced, implemented using a periodic
timer interrupt
Scheduler awakes after each interrupt, schedules jobs to
execute for the next period, then blocks itself until the next
interrupt
E.g. the helicopter example with the interrupt every 1/180 th of a
second
Typically in clock-driven systems:
All parameters of the real-time jobs are fixed and known
A schedule of the jobs is computed off-line and is stored for
use at runtime; thus scheduling overhead at run-time can
be minimized
Simple and straight-forward, not flexible
41
Scheduling – Priority-Driven
Assign priorities to jobs, based on some algorithm
Make scheduling decisions based on the priorities, when events
such as releases and job completions occur
Priority scheduling algorithms are event-driven
Jobs are placed in one or more queues; at each event, the
ready job with the highest priority is executed
(The assignment of jobs to priority queues, along with rules such as
whether preemption is allowed, completely defines a priority-driven alg.)
Priority-driven algs. make locally optimal scheduling decisions
Locally optimal scheduling is often not globally optimal
Priority-driven algorithms never intentionally leave idle
processors
Typically in priority-driven systems:
Some parameters do not have to be fixed or known
A schedule is computed online; usually results in larger
scheduling overhead as opposed to clock-driven scheduling
Flexible – easy to add/remove tasks or modify parameters
42
Clock-Driven & Priority-Driven Example
T1 T2 T3
pi 3 5 10
ei 1 2 1
Clock-Driven:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
· · ·
· · ·
· · ·
Priority-driven: T1 T2 T3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
43
Real-Time Scheduling
Scheduling of Reactive Systems
Clock-Driven Scheduling
44
Current Assumptions
Fixed number, n, of periodic tasks T1, . . . , Tn
Parameters of periodic tasks are known a priori
Execution time ei,k of each job Ji,k in a task Ti is fixed
For a job Ji,k in a task Ti we have
ri,1 = ϕi = 0 (i.e., synchronized)
ri,k = ri,k−1 + pi
We allow aperiodic jobs
assume that the system maintains a single queue for
aperiodic jobs
Whenever the processor is available for aperiodic jobs, the
job at the head of this queue is executed
We treat sporadic jobs later
45
Static, Clock-Driven Scheduler
Construct a static schedule offline
The schedule specifies exactly when each job executes
The amount of time allocated to every job is equal to its
execution time
The schedule repeats each hyperperiod
i.e. it suffices to compute the schedule up to hyperperiod
Can use complex algorithms offline
Runtime of the scheduling algorithm is not relevant
Can compute a schedule that optimizes some
characteristics of the system
e.g. a schedule where the idle periods are nearly periodic (useful
to accommodate aperiodic jobs)
46
Example
T1 = (4, 1), T2 = (5, 1.8), T3 = (20, 1), T4 = (20, 2)
Hyperperiod H = 20
0 4 8 12 16 20 24
Aper.
T1
T2
T3
T4
47
Implementation of Static Scheduler
Store pre-computed schedule as a table
Each entry (tk , T(tk )) gives
a decision time tk
scheduling decision T(tk ) which is either a
task to be executed, or idle (denoted by I)
The system creates all tasks that are to be
executed:
Allocates memory for the code and data
Brings the code into memory
Scheduler sets the hardware timer to interrupt
at the first decision time t0 = 0
On receipt of an interrupt at tk :
Scheduler sets the timer interrupt to tk+1
If previous task overrunning, handle failure
If T(tk ) = I and aperiodic job waiting, start
executing it
Otherwise, start executing the next job in T(tk )
48
Example
T1 = (4, 1), T2 = (5, 1.8), T3 = (20, 1), T4 = (20, 2)
Hyperperiod H = 20
0 4 8 12 16 20 24
Aper.
T1
T2
T3
T4
tk 0.0 1.0 2.0 3.8 4.0 5.0 6.0 · · ·
T(tk ) T1 T3 T2 I T1 I T4 · · ·
49
Frame Based Scheduling
Arbitrary table-driven cyclic schedules flexible, but
inefficient
Relies on accurate timer interrupts, based on execution
times of tasks
High scheduling overhead
Easier to implement if a structure is imposed
Make scheduling decisions at periodic intervals (frames) of
length f
Execute a fixed list of jobs within each frame;
no preemption within frames
Gives two benefits:
Scheduler can easily check for overruns and missed
deadlines at the end of each frame.
Can use a periodic clock interrupt, rather than
programmable timer.
50
Frame Based Scheduling – Cyclic Executive
Modify previous table-driven scheduler to be frame based
Table that drives the scheduler has F entries, where
F = H/f
The k-th entry L(k) lists the names of the jobs that are to
be scheduled in frame k (L(k) is called scheduling block)
Each job is implemented by a procedure
Cyclic executive executed by the clock interrupt that
signals the start of a frame:
If an aperiodic job is executing, preempts it; if a periodic
overruns, handles the overrun
Determines the appropriate scheduling block for this frame
Executes the jobs in the scheduling block
Executes jobs from the head of the aperiodic job queue for
the remainder of the frame
Less overhead than pure table driven cyclic scheduler,
since only interrupted on frame boundaries, rather than on
each job
51
Frame Based Scheduling – Frame Size
How to choose the frame length?
(Assume that periods are in N and choose frame sizes in N.)
1. Necessary condition for avoiding preemption of jobs is
f ≥ max
i
ei
(i.e. we want each job to have a chance to finish within a frame)
2. To minimize the number of entries in the cyclic schedule, the
hyper-period should be an integer multiple of the frame size, i.e.
∃i : pi mod f = 0
3. To allow scheduler to check that jobs complete by their deadline,
at least one frame should lie between release time of a job and
its deadline, which is equivalent to
∀i : 2 ∗ f − gcd(pi, f) ≤ Di
All three constraints should be satisfied.
52
Frame Based Scheduling – Frame Size – Example
1. f ≥ maxi ei
2. ∃i : pi mod f = 0
3. ∀i : 2 ∗ f − gcd(pi, f) ≤ Di
Example 8
T1 = (4, 1.0), T2 = (5, 1.8), T3 = (20, 1.0), T4 = (20, 2.0)
Then f ∈ N satisfies 1.–3. iff f = 2.
With f = 2 is schedulable:
53
Frame Based Scheduling – Job Slices
Sometimes a system cannot meet all three frame size
constraints simultaneously (and even if it meets the
constraints, no non-preemptive schedule is feasible)
Can be solved by partitioning a job with large execution
time into slices with shorter execution times
This, in effect, allows preemption of the large job
Consider T1 = (4, 1), T2 = (5, 2, 7), T3 = (20, 5)
Cannot satisfy constraints: 1. ⇒ f ≥ 5 but 3. ⇒ f ≤ 4
Solve by splitting T3 into T3,1 = (20, 1), T3,2 = (20, 3), and
T3,3 = (20, 1)
(Other splits exist)
Result can be scheduled with f = 4
54
Building a Structured Cyclic Schedule
To construct a schedule, we have to make three kinds of design
decisions (that cannot be taken independently):
Choose a frame size based on constraints
Partition jobs into slices
Place slices into frames
There are efficient algorithms for solving these problems based
e.g. on a reduction to the network flow problem.
55
Scheduling Aperiodic Jobs
So far, aperiodic jobs scheduled in the background after all jobs
with hard deadlines
This may unnecessarily delay aperiodic jobs
Note: There is no advantage in completing periodic jobs early
Ideally, finish periodic jobs by their respective deadlines.
Slack Stealing:
Slack time in a frame = the time left in the frame after all
(remaining) slices execute
Schedule aperiodic jobs ahead of periodic in the slack time of
periodic jobs
The cyclic executive keeps track of the slack time left in
each frame as the aperiodic jobs execute, preempts them
with periodic jobs when there is no more slack
As long as there is slack remaining in a frame and the
aperiodic jobs queue is non-empty, the executive executes
aperiodic jobs, otherwise executes periodic
Reduces resp. time for aper. jobs, but requires accurate timers
56
Example
Assume that the aperiodic queue is never empty.
Aperiodic at the ends of frames:
0 4 8 12 16 20 24
Aper.
T1
T2
T3
T4
Slack stealing:
0 4 8 12 16 20 24
Aper.
T1
T2
T3
T4
57
Slack Stealing – cont.
Sl. S.
Standard
Rel. aper.
Period.
58
Frame Based Scheduling – Sporadic Jobs
Let us allow sporadic jobs
i.e. hard real-time jobs whose release and exec. times are not known a priori
The scheduler determines whether to accept a sporadic job when it
arrives (and its parameters become known)
Perform acceptance test to check whether the new sporadic job
can be feasibly scheduled with all the jobs (periodic and
sporadic) in the system at that time
Acceptance check done at the beginning of the next frame; has to keep
execution times of the parts of sporadic jobs that have already executed
If there is sufficient slack time in the frames before the new job’s
deadline, the new sporadic job is accepted; otherwise, rejected
Among themselves, sporadic jobs scheduled according to EDF
This is optimal for sporadic jobs
Note: rejection is often better than missing deadline
e.g. a robotic arm taking defective parts off a conveyor belt: if the arm cannot
meet deadline, the belt may be slowed down or stopped
59
S1(17, 4.5) released at 3 with abs. deadline 17 and execution time 4.5;
acceptance test at 4; must be scheduled in frames 2, 3, 4; total slack in
these frames is 4, i.e. rejected
S2(29, 4) released at 5 with abs. deadline 29 and exec. time 4; acc. test
at 8; total slack in frames 3-7 is 5.5, i.e. accepted
S3(22, 1.5) released at 11 with abs. deadline 22 and exec. time 1.5;
acc. test at 12;
2 units of slack in frames 4, 5 as S3 will be executed ahead of the
remaining parts of S2 by EDF – check whether there will be enough
slack for the remaining parts of S2, accepted
S4(44, 5.0) is rejected (only 4.5 slack left)
60
Handling Overruns
Overruns may happen due to failures
e.g. unexpectedly large data over which the system operates, hardware
failures, etc.
Ways to handle overruns:
Abort the overrun job at the beginning of the next frame;
log the failure; recover later
e.g. control law computation of a robust digital controller
Preempt the overrun job and finish it as an aperiodic job
use this when aborting job would cause “costly” inconsistencies
Let the overrun job finish – start of the next frame and the
execution jobs scheduled for this frame are delayed
This may cause other jobs to be delayed
depends on application
61
Clock-drive Scheduling: Conclusions
Advantages:
Conceptual simplicity
Complex dependencies, communication delays, and
resource contention among jobs can be considered when
constructing the static schedule
Entire schedule in a static table
No concurrency control or synchronization needed
Easy to validate, test and certify
Disadvantages:
Inflexible
If any parameter changes, the schedule must be usually
recomputed
Best suited for systems which are rarely modified (e.g. controllers)
Parameters of the jobs must be fixed
As opposed to most priority-driven schedulers
62
Real-Time Scheduling
Scheduling of Reactive Systems
Priority-Driven Scheduling
63
Current Assumptions
Single processor
Fixed number, n, of independent periodic tasks
i.e. there is no dependency relation among jobs
Jobs can be preempted at any time and never suspend
themselves
No aperiodic and sporadic jobs
No resource contentions
Moreover, unless otherwise stated, we assume that
Scheduling decisions take place precisely at
release of a job
completion of a job
(and nowhere else)
Context switch overhead is negligibly small
i.e. assumed to be zero
There is an unlimited number of priority levels
64
Fixed-Priority vs Dynamic-Priority Algorithms
A priority-driven scheduler is on-line
i.e. it does not precompute a schedule of the tasks
It assigns priorities to jobs after they are released and places the
jobs in a ready job queue in the priority order
with the highest priority jobs at the head of the queue
At each scheduling decision time, the scheduler updates the
ready job queue and then schedules and executes the job at the
head of the queue
i.e. one of the jobs with the highest priority
Fixed-priority = all jobs in a task are assigned the same priority
Dynamic-priority = jobs in a task may be assigned different priorities
Note: In our case, a priority assigned to a job does not change. There are
job-level dynamic priority algorithms that vary priorities of individual jobs – we
won’t consider such algorithms.
65
Fixed-priority Algorithms – Rate Monotonic
Best known fixed-priority algorithm is rate monotonic (RM) scheduling
that assigns priorities to tasks based on their periods
The shorter the period, the higher the priority
The rate is the inverse of the period, so jobs with higher rate
have higher priority
RM is very widely studied and used
Example 9
T1 = (4, 1), T2 = (5, 2), T3 = (20, 5)
with rates 1/4, 1/5, 1/20, respectively
The priorities: T1 T2 T3
0 4 8 12 16 20
T3
T2
T1
66
Fixed-priority Algorithms – Deadline Monotonic
The deadline monotonic (DM) algorithm assigns priorities to
tasks based on their relative deadlines
the shorter the deadline, the higher the priority
Observation: When relative deadline of every task matches its
period, then RM and DM give the same results
Proposition 1
When the relative deadlines are arbitrary DM can sometimes
produce a feasible schedule in cases where RM cannot.
67
Rate Monotonic vs Deadline Monotonic
T1 = (50, 50, 25, 100), T2 = (0, 62.5, 10, 20), T3 = (0, 125, 25, 50)
DM is optimal (with priorities T2 T3 T1):
50 100 150 200 250
0 62.5 125 187.5 250
0 125 250
20 82.5 145 207.5
50 175
T3
T2
T1
RM is not optimal (with priorities T1 T2 T3):
50 100 150 200 250
0 62.5 125 187.5 250
0 125 250
20 82.5 145 207.5
50 175
T3
T2
T1
68
Dynamic-priority Algorithms
Best known is earliest deadline first (EDF) that assigns
priorities based on current (absolute) deadlines
At the time of a scheduling decision, the job queue is
ordered by earliest deadline
Another one is the least slack time (LST)
The job queue is ordered by least slack time
Recall that the slack time of a job Ji at time t is equal to di − t − x where x is
the remaining computation time of Ji at time t
Comments:
There is also a strict LST which reassigns priorities to jobs whenever
their slacks change relative to each other – won’t consider
Standard “non real-time” algorithms such as FIFO and LIFO are also
dynamic-priority algorithms
We focus on EDF here, leave some LST for homework
69
EDF – Example
T1 = (2, 1) and T2 = (5, 2.5)
0 1 2 3 4 5 6 7 8 9 10
T2
T1
Note that the processor is 100% “utilized”, not surprising :-)
70
Summary of Priority-Driven Algorithms
We consider:
Dynamic-priority:
EDF = at the time of a scheduling decision, the job queue is
ordered by the earliest deadline
Fixed-priority:
RM = assigns priorities to tasks based on their periods
DM = assigns priorities to tasks based on their relative deadlines
(In all cases, ties are broken arbitrarily.)
We consider the following questions:
Are the algorithms optimal?
How to efficiently (or even online) test for schedulability?
To measure abilities of scheduling algorithms and to get fast online
tests of schedulability we use a notion of utilization
71
Utilization
Utilization ui of a periodic task Ti with period pi and
execution time ei is defined by ui := ei/pi
ui is the fraction of time a periodic task with period pi and execution time
ei keeps a processor busy
Total utilization UT of a set of tasks T = {T1, . . . , Tn} is
defined as the sum of utilizations of all tasks of T , i.e. by
UT
:=
n
i=1
ui
U is a schedulable utilization of an algorithm ALG if all sets
of tasks T satisfying UT ≤ U are schedulable by ALG.
Maximum schedulable utilization UALG of an algorithm ALG
is the supremum of schedulable utilizations of ALG.
If UT
< UALG, then T is schedulable by ALG.
If U > UALG, then there is T with UT
≤ U that is not
schedulable by ALG.
72
Utilization – Example
T1 = (2, 1) then u1 = 1
2
T1 = (11, 5, 2, 4) then u1 = 2
5
(i.e., the phase and deadline do not play any role)
T = {T1, T2, T3} where T1 = (2, 1), T2 = (6, 1), T3 = (8, 3)
then
UT
=
1
2
+
1
6
+
3
8
=
25
24
73
Real-Time Scheduling
Priority-Driven Scheduling
Dynamic-Priority
74
Optimality of EDF
Theorem 10
Let T = {T1, . . . , Tn} be a set of independent, preemptable
periodic tasks with Di ≥ pi for i = 1, . . . , n. The following
statements are equivalent:
1. T can be feasibly scheduled on one processor
2. UT ≤ 1
3. T is schedulable using EDF
(i.e., in particular, UEDF = 1)
Proof.
1.⇒2. We prove that UT
> 1 implies that T is not schedulable
2.⇒3. Next slides and whiteboard ...
3.⇒1. Trivial
75
Proof of 1.⇒2.
Assume that UT
= N
i=1
ei
pi
> 1.
Consider a time instant t > maxi ϕi
(i.e. a time when all tasks are already "running")
Observe that the number of jobs of Ti that are released in the time
interval [0, t] is
t−ϕi
pi
. Thus a single processor needs n
i=1
t−ϕi
pi
· ei
time units to finish all jobs released before or at t.
However,
n
i=1
t − ϕi
pi
·ei ≥
n
i=1
(t−ϕi)·
ei
pi
=
n
i=1
tui−ϕiui =
n
i=1
tui−
n
i=1
ϕiui = t·UT
−
n
i=1
ϕiui
Here n
i=1 ϕiui does not depend on t.
Note that limt→∞ t · UT
− n
i=1 ϕiui − t = ∞. So there exists t such
that t · UT
− n
i=1 ϕiui > t + maxi Di.
So in order to complete all jobs released before time t we need more
time than t + maxi Di. However, the latest deadline of a job released
before t is t + maxi Di. So at least one job misses its deadline.
76
Proof of 2.⇒3. – Simplified
Let us start with a proof of a special case (see the assumptions A1 and A2
below). Then a complete proof will be presented.
We prove ¬3.⇒ ¬2. assuming that Di = pi for i = 1, . . . , n.
(Note that the general case immediately follows.)
Assume that T is not schedulable according to EDF.
(Our goal is to show that UT
> 1.)
This means that there must be at least one job that misses its
deadline when EDF is used.
Simplifying assumptions:
A1 Suppose that all tasks are in phase, i.e. the phase ϕ = 0 for
every task T .
A2 Suppose that the first job Ji,1 of a task Ti misses its deadline.
By A1, Ji,1 is released at 0 and misses its deadline at pi. Assume
w.l.o.g. that this is the first time when a job misses its deadline.
(To simplify even further, you may (privately) assume that no other job has its
deadline at pi.)
77
Proof of 2.⇒3. – Simplified
Let G be the set of all jobs that are released in [0, pi] and have their
deadlines in [0, pi].
Crucial observations:
G contains Ji,1 and all jobs that preempt Ji,1.
(If there are more jobs with deadline pi, then these jobs do not have to
preempt Ji,1. Assume the worst case: all these jobs preempt Ji,1.)
The processor is never idle during [0, pi] and executes only jobs
of G.
Denote by EG the total execution time of G, that is, the sum of
execution times of all jobs in G.
Corollary of the crucial observation: EG > pi because otherwise
Ji,1 (and all jobs that preempt it) would complete by pi.
Let us compute EG.
78
Proof of 2.⇒3. – Simplified
Since we assume ϕ = 0 for every T , the first job of T is released
at 0, and thus
pi
p jobs of T belong to G.
E.g., if p = 2 and pi = 5 then three jobs of T are released in [0, 5] (at times
0, 2, 4) but only 2 = 5
2
=
pi
p
of them have their deadlines in [0, pi].
Thus the total execution time EG of all jobs in G is
EG =
n
=1
pi
p
e
But then
pi < EG =
n
=1
pi
p
e ≤
n
=1
pi
p
e ≤ pi
n
=1
u ≤ pi · UT
which implies that UT
> 1.
79
Proof of 2.⇒3. – Complete
Now let us drop the simplifying assumptions A1 and A2 !
Notation: Given a set of tasks L, we denote by L the set of all
jobs of the tasks in L.
We prove ¬3.⇒ ¬2. assuming that Di = pi for i = 1, . . . , n (note that
the general case immediately follows).
Assume that T is not schedulable by EDF. We show that UT
> 1.
Suppose that a job Ji,k of Ti misses its deadline at time t = ri,k + pi.
Assume that this is the earliest deadline miss.
Let T be the set of all tasks whose jobs have deadlines (and thus
also release times) in [ri,k , t]
(i.e., a task belongs to T iff at least one job of the task is released in [ri,k , t]).
Let t− be the end of the latest interval before t in which either jobs of
(T T ) are executed, or the processor is idle.
Then ri,k ≥ t− since all jobs of (T T ) waiting for execution during
[ri,k , t] have deadlines later than t (thus have lower priorities than Ji,k ).
80
Proof of 2.⇒3. – Complete (cont.)
It follows that
no job of (T T ) is executed in [t−, t],
(by definition of t−)
the processor is fully utilized in [t−, t].
(by definition of t−)
all jobs (that all must belong to T ) executed in [t−, t] are
released in [t−, t] and have their deadlines in [t−, t] since
no job of T executes just before t−,
all jobs of T released in [t−, ri,k ] have deadlines before t,
jobs of T released in [ri,k , t] with deadlines after t are not
executed in [ri,k , t] as they have lower priorities than Ji,k .
Let G be the set of all jobs that are released in [t−, t] and have their
deadlines in [t−, t].
Note that Ji,k ∈ G since ri,k ≥ t−.
Denote by EG the sum of all execution times of all jobs in G (the total
execution time of G).
81
Proof of 2.⇒3. – Complete (cont.)
Now EG > t − t− because otherwise Ji,k would complete in [t−, t].
How to compute EG?
For T ∈ T , denote by R the earliest release time of a job in T
during the interval [t−, t].
For every T ∈ T , exactly t−R
p jobs of T belong to G. (For every
T ∈ T T , exactly 0 jobs belong to G.)
Thus
EG =
T ∈T
t − R
p
e
As argued above:
t−t− < EG =
T ∈T
t − R
p
e ≤
T ∈T
t − t−
p
e ≤ (t−t−)
T ∈T
u ≤ (t−t−)UT
which implies that UT
> 1.
82
Density and EDF
What about tasks with Di < pi ?
Density of a task Ti with period pi, execution time ei and relative
deadline Di is defined by
ei/ min(Di, pi)
Total density ∆T of a set of tasks T is the sum of densities of
tasks in T
Note that if Di < pi for some i, then ∆T
> UT
Theorem 11
A set T of independent, preemptable, periodic tasks can be
feasibly scheduled on one processor if ∆T ≤ 1.
Note that this is NOT a necessary condition! (Example whiteb.)
83
Schedulability Test For EDF
The problem: Given a set of independent, preemptable, periodic
tasks T = {T1, . . . , Tn} where each Ti has a period pi, execution time
ei, and relative deadline Di, decide whether T is schedulable by EDF.
Solution using utilization and density:
If pi ≤ Di for each i, then it suffices to decide whether UT ≤ 1.
Otherwise, decide whether ∆T ≤ 1:
If yes, then T is schedulable with EDF
If not, then T does not have to be schedulable
Note that
Phases of tasks do not have to be specified
Parameters may vary: increasing periods or deadlines, or
decreasing execution times does not prevent schedulability
84
Schedulability Test for EDF – Example
Consider a digital robot controller
A control-law computation
takes no more than 8 ms
the sampling rate: 100 Hz, i.e. computes every 10 ms
Feasible? Trivially yes ....
Add Built-In Self-Test (BIST)
maximum execution time 50 ms
want a minimal period that is feasible (max one second)
With 250 ms still feasible ....
Add a telemetry task
maximum execution time 15 ms
want to minimize the deadline on telemetry
period may be large
Reducing BIST to once a second, deadline on telemetry
may be set to 100 ms ....
85
Real-Time Scheduling
Priority-Driven Scheduling
Fixed-Priority
86
Fixed-Priority Algorithms
Recall that we consider a set of n tasks T = {T1, . . . , Tn}
Any fixed-priority algorithm schedules tasks of T according to fixed
(distinct) priorities assigned to tasks.
We write Ti Tj whenever Ti has a higher priority than Tj.
To simplify our reasoning, assume that
all tasks are in phase, i.e. ϕk = 0 for all Tk .
We will remove this assumption at the end.
87
Fixed-Priority Algorithms – Reminder
Recall that Fixed-Priority Algorithms do not have to be optimal.
Consider T = {T1, T2} where T1 = (2, 1) and T2 = (5, 2.5)
UT
= 1 and thus T is schedulable by EDF
If T1 T2, then J2,1 misses its deadline
If T2 T1, then J1,1 misses its deadline
We consider the following algorithms:
RM = assigns priorities to tasks based on their periods
the priority is inversely proportional to the period pi
DM = assigns priorities to tasks based on their relative deadlines
the priority is inversely proportional to the relative deadline Di
(In all cases, ties are broken arbitrarily.)
We consider the following questions:
Are the algorithms optimal?
How to efficiently (or even online) test for schedulability?
88
Maximum Response Time
Which job of a task Ti has the maximum response time?
As all tasks are in phase, the first job of Ti is released together with
(first) jobs of all tasks that have higher priority than Ti.
This means, that Ji,1 is the most preempted of jobs in Ti.
It follows, that Ji,1 has the maximum response time.
Note that this relies heavily on the assumption that tasks are in phase!
Thus in order to decide whether T is schedulable, it suffices to test
for schedulability of the first jobs of all tasks.
89
Optimality of RM for Simply Periodic Tasks
Definition 12
A set {T1, . . . , Tn} is simply periodic if for every pair Ti, T satisfying
pi > p we have that pi is an integer multiple of p
Example 13
The helicopter control system from the first lecture.
Theorem 14
A set T of n simply periodic, independent, preemptable tasks with
Di = pi is schedulable on one processor according to RM iff UT
≤ 1.
i.e. on simply periodic tasks RM is as good as EDF
Note: Theorem 14 is true in general, no "in phase" assumption is needed.
90
Proof of Theorem 14
By Theorem 10, every schedulable set T satisfies UT
≤ 1.
We prove that if T is not schedulable according to RM, then UT
> 1.
Assume that a job Ji,1 of Ti misses its deadline at Di = pi. W.l.o.g., we
assume that T1 · · · Tn according to RM.
Let us compute the total execution time of Ji,1 and all jobs that
preempt it:
E = ei +
n
=i+1
pi
p
e =
n
=i
pi
p
e = pi
n
=i
u ≤ pi
n
=1
u = piUT
Now E > pi because otherwise Ji,1 meets its deadline. Thus
pi < E ≤ piUT
and we obtain UT
> 1.
91
Optimality of DM (RM) among Fixed-Priority Algs.
Theorem 15
A set of independent, preemptable periodic tasks with Di ≤ pi that are
in phase (i.e., ϕi = 0 for all i = 1, . . . , n) can be feasibly scheduled on
one processor according to DM if it can be feasibly scheduled by
some fixed-priority algorithm.
Proof.
Assume a fixed-priority feasible schedule with T1 · · · Tn.
Consider the least i such that the relative deadline Di of Ti is larger
than the relative deadline Di+1 of Ti+1.
Swap the priorities of Ti and Ti+1.
The resulting schedule is still feasible.
DM is obtained by using finitely many swaps.
Note: If the assumptions of the above theorem hold and all relative deadlines
are equal to periods, then RM is optimal among all fixed-priority algorithms.
Note: no "in phase" assumption is needed here.
92
Fixed-Priority Algorithms: Schedulability
We consider two schedulability tests:
Schedulable utilization URM of the RM algorithm.
Time-demand analysis based on response times.
93
Schedulable Utilization for RM
Theorem 16
Let us fix n ∈ N and consider only independent, preemptable
periodic tasks with Di = pi.
If T is a set of n tasks satisfying UT ≤ n(21/n − 1), then UT
is schedulable according to the RM algorithm.
For every U > n(21/n − 1) there is a set T of n tasks
satisfying UT ≤ U that is not schedulable by RM.
Note: Theorem 16 holds in general, no "in phase" assumption is needed.
94
Schedulable Utilization for RM
It follows that the maximum schedulable utilization URM over
independent, preemptable periodic tasks satisfies
URM = inf
n
n(21/n
− 1) = lim
n→∞
n(21/n
− 1) = ln 2 ≈ 0.693
Note that UT
≤ n(21/n
− 1) is a sufficient but not necessary condition for
schedulability of T using the RM algorithm (an example will be given later)
We say that a set of tasks T is RM-schedulable if it is
schedulable according to RM.
We say that T is RM-infeasible if it is not RM-schedulable.
95
Proof – Special Case
To simplify, we restrict to two tasks and always assume p2 ≤ 2p1.
(the latter condition is w.l.o.g., proof omitted)
Outline: Given p1, p2, e1, denote by max_e2 the maximum execution
time so that T = {(p1, e1), (p2, max_e2)} is RM-schedulable.
We define Up1,p2
e1
to be UT
where T = {(p1, e1), (p2, max_e2)}.
We say that T fully utilizes the processor, any increase in an execution time
causes RM-infeasibility.
Now we find the (global) minimum minU of Up1,p2
e1
.
Note that this suffices to obtain the desired result:
Given a set of tasks T = {(p1, e1), (p2, e2)} satisfying UT
≤ minU
we get UT
≤ minU ≤ Up1,p2
e1
, and thus the execution time e2
cannot be larger than max_e2. Thus, T is RM-schedulable.
Given U > minU, there must be p1, p2, e1 satisfying
minU ≤ Up1,p2
e1
< U where Up1,p2
e1
= UT
for a set of tasks
T = {(p1, e1), (p2, max_e2)}.
However, now increasing e1 by a sufficiently small ε > 0 makes
the set RM-infeasible without making utilization larger than U.
96
Proof – Special Case (Cont.)
Consider two cases depending on e1:
1. e1 < p2 − p1 :
Maximum RM-feasible max_e2 (with p1, p2, e1 fixed) is p2 − 2e1.
Which gives the utilization
Up1,p2
e1
=
e1
p1
+
max_e2
p2
=
e1
p1
+
p2 − 2e1
p2
=
e1
p1
+
p2
p2
−
2e1
p2
= 1 +
e1
p2
p2
p1
− 2
As
p2
p1
− 2 ≤ 0, the utilization Up1,p2
e1
is minimized by maximizing e1.
2. e1 ≥ p2 − p1 :
Maximum RM-feasible max_e2 (with p1, p2, e1 fixed) is p1 − e1. Which
gives the utilization
Up1,p2
e1
=
e1
p1
+
max_e2
p2
=
e1
p1
+
p1 − e1
p2
=
e1
p1
+
p1
p2
−
e1
p2
=
p1
p2
+
e1
p2
p2
p1
− 1
As
p2
p1
− 1 ≥ 0, the utilization Up1,p2
e1
is minimized by minimizing e1.
The minimum of Up1,p2
e1
is attained at e1 = p2 − p1.
(Both expressions defining U
p1,p2
e1
give the same value for e1 = p2 − p1.)
97
Proof – Special Case (Cont.)
Substitute e1 = p2 − p1 into the expression for Up1,p2
e1
:
Up1,p2
p2−p1
=
p1
p2
+
p2 − p1
p2
p2
p1
− 1 =
p1
p2
+ 1 −
p1
p2
p2
p1
− 1
=
p1
p2
+
p1
p2
p2
p1
− 1
p2
p1
− 1 =
p1
p2

1 +
p2
p1
− 1
2

Denoting G =
p2
p1
− 1 we obtain
Up1,p2
p2−p1
=
p1
p2
(1 + G2
) =
1 + G2
p2/p1
=
1 + G2
1 + G
Differentiating w.r.t. G we get
G2
+ 2G − 1
(1 + G)2
which attains minimum at G = −1 ±
√
2. Here only G = −1 +
√
2 > 0
is acceptable since the other root is negative.
98
Proof – Special Case (Cont.)
Thus the minimum value of Up1,p2
e1
is
1 + (
√
2 − 1)2
1 + (
√
2 − 1)
=
4 − 2
√
2
√
2
= 2(
√
2 − 1)
It is attained at periods satisfying
G =
p2
p1
− 1 =
√
2 − 1 i.e. satisfying p2 =
√
2p1.
The execution time e1 which at full utilization of the processor (due to
max_e2) gives the minimum utilization is
e1 = p2 − p1 = (
√
2 − 1)p1
and the corresponding max_e2 = p1 − e1 = p1 − (p2 − p1) = 2p1 − p2.
Scaling to p1 = 1, we obtain a completely determined example
p1 = 1 p2 =
√
2 ≈ 1.41 e1 =
√
2−1 ≈ 0.41 max_e2 = 2−
√
2 ≈ 0.59
that fully utilizes the processor (no execution time can be increased)
but has the minimum utilization 2(
√
2 − 1).
99
Proof Idea of Theorem 16
Fix periods p1 < · · · < pn so that (w.l.o.g.) pn ≤ 2p1. Then the
following set of tasks has the smallest utilization among all task sets
that fully utilize the processor (i.e., any increase in any execution time
makes the set unschedulable).
0 p1 2p1
0 p2
0 p3
0 pn−1
0 pn
...
T3
T2
T1
Tn
Tn−1
ek = pk+1 − pk for k = 1, . . . , n − 1
en = pn − 2
n−1
k=1
ek = 2p1 − pn
100
Time-Demand Analysis
Consider a set of n tasks T = {T1, . . . , Tn}.
Recall that we consider only independent, preemptable, in phase (i.e. ϕi = 0
for all i) tasks without resource contentions.
Assume that Di ≤ pi for every i, and consider an arbitrary
fixed-priority algorithm. W.l.o.g. assume T1 · · · Tn.
Idea: For every task Ti and every time instant t ≥ 0, compute the total
execution time wi(t) (the time demand) of the first job Ji,1 and of all
higher-priority jobs released up to time t.
If wi(t) ≤ t for some time t ≤ Di, then Ji,1 is schedulable, and hence all
jobs of Ti are schedulable.
101
Time-Demand Analysis
Consider one task Ti at a time, starting with highest priority and
working to lowest priority.
Focus on the first job Ji,1 of Ti.
If Ji,1 makes it, all jobs of Ti will make it due to ϕi = 0.
At time t for t ≥ 0, the processor time demand wi(t) for this job
and all higher-priority jobs released in [0, t] is bounded by
wi(t) = ei +
i−1
=1
t
p
e for 0 < t ≤ pi
(Note that the smallest t for which wi(t) ≤ t is the response time of Ji,1,
and hence the maximum response time of jobs in Ti).
If wi(t) ≤ t for some t ≤ Di, the job Ji,1 meets its deadline Di.
If wi(t) > t for all 0 < t ≤ Di, then the first job of the task cannot
complete by its deadline.
102
Time-Demand Analysis – Example
Example: T1 = (3, 1), T2 = (5, 1.5), T3 = (7, 1.25), T4 = (9, 0.5)
This is schedulable by RM even though
U{T1,...,T4}
= 0.85 > 0.757 = URM(4) 103
Time-Demand Analysis
The time-demand function wi(t) is a staircase function
Steps in the time-demand for a task occur at multiples of
the period for higher-priority tasks
The value of wi(t) − t linearly decreases from a step until
the next step
If our interest is the schedulability of a task, it suffices to
check if wi(t) ≤ t at the time instants when a higher-priority
job is released and at Di
Our schedulability test becomes:
Compute wi(t)
Check whether wi(t) ≤ t for some t equal either to Di, or to
j · pk where k = 1, 2, . . . , i and j = 1, 2, . . . , Di/pk
104
Time-Demand Analysis – Comments
Time-demand analysis schedulability test is more complex than
the schedulable utilization test but more general:
Works for any fixed-priority scheduling algorithm, provided
the tasks have short response time (Di ≤ pi)
Can be extended to tasks with arbitrary deadlines
Still more efficient than exhaustive simulation.
Assuming that the tasks are in phase the time demand analysis
is complete.
We have considered the time demand analysis for tasks in phase. In
particular, we used the fact that the first job has the maximum
response time.
This is not true if the jobs are not in phase, we need to identify the so
called critical instant, the time instant in which the system is most
loaded, and has its worst response time.
105
Critical Instant – Formally
Definition 17
A critical instant tcrit of a task Ti is a time instant in which a job Ji,k in
Ti is released so that Ji,k either does not meet its deadline, or has
the maximum response time of all jobs in Ti.
Theorem 18
In a fixed-priority system where every job completes before the next
job in the same task is released, a critical instant of a task Ti occurs
when one of its jobs Ji,k is released at the same time with a job from
every higher-priority task.
Note that the situation described in the theorem does not have to occur if
tasks are not in phase!
106
Critical Instant and Schedulability Tests
We use critical instants to get upper bounds on schedulability as
follows:
Set phases of all tasks to zero, which gives a new set of tasks
T = {T1
, . . . , Tn}
By Theorem 18, the response time of the first job Ji,1
of T1
in T is at
least as large as the response time of every job of Ti in T .
Decide schedulability of T , e.g. using the timed-demand
analysis.
If T if schedulable, then also T is schedulable.
If T is not schedulable, then T does not have to be
schedulable.
But may be schedulable, which make the time-demand analysis
incomplete in general for tasks not in phase.
107
Dynamic vs Fixed Priority
EDF
pros:
optimal
very simple and complete test for schedulability
cons:
difficult to predict which job misses its deadline
strictly following EDF in case of overloads assigns higher
priority to jobs that missed their deadlines
larger scheduling overhead
DM (RM)
pros:
easier to predict which job misses its deadline (in particular,
tasks are not blocked by lower priority tasks)
easy implementation with little scheduling overhead
(optimal in some cases often occurring in practice)
cons:
not optimal
incomplete and more involved tests for schedulability
108
Real-Time Scheduling
Priority-Driven Scheduling
Aperiodic Tasks
109
Current Assumptions
Single processor
Fixed number, n, of independent periodic tasks
Jobs can be preempted at any time and never suspend
themselves
No resource contentions
Aperiodic jobs exist
They are independent of each other, and of the periodic
tasks
They can be preempted at any time
There are no sporadic jobs (for now)
Jobs are scheduled using a priority driven algorithm
110
Scheduling Aperiodic Jobs
Consider:
A set T = {T1, . . . , Tn} of periodic tasks
An aperiodic task A
Recall that:
A schedule is feasible if all jobs with hard real-time
constraints complete before their deadlines
⇒ This includes all periodic jobs
A scheduling algorithm is optimal if it always produces a
feasible schedule whenever such a schedule exists, and if
a cost function is given, minimizes the cost
We assume that the periodic tasks are scheduled using a
priority-driven algorithm
111
Background Scheduling of Aperiodic Jobs
Aperiodic jobs are scheduled and executed only at times
when there are no periodic jobs ready for execution
Advantages
Clearly produces feasible schedules
Extremely simple to implement
Disadvantages
Not optimal since the execution of aperiodic jobs may be
unnecessarily delayed
Example: T1 = (3, 1), T2 = (10, 4)
112
Polled Execution of Aperiodic Jobs
We may use a polling server
A periodic job (ps, es) scheduled according to the periodic
algorithm, generally as the highest priority job
When executed, it examines the aperiodic job queue
If an aperiodic job is in the queue, it is executed for up to es
time units
If the aperiodic queue is empty, the polling server
self-suspends, giving up its execution slot
The server does not wake-up once it has self-suspended,
aperiodic jobs which become active during a period are not
considered for execution until the next period begins
Simple to prove correctness, performance less than ideal –
executes aperiodic jobs in particular timeslots
113
Polled Execution of Aperiodic Jobs
Example: T1 = (3, 1), T2 = (10, 4), poller = (2.5, 0.5)
Can we do better?
Yes, polling server is a special case of periodic-server for
aperiodic jobs.
114
Periodic Severs – Terminology
periodic server = a task that behaves much like a periodic task,
but is created for the purpose of executing aperiodic jobs
A periodic server, TS = (pS, eS)
pS is a period of the server
eS is the (maximal) budget of the server
The budget can be consumed and replenished; the budget
is exhausted when it reaches 0
(Periodic servers differ in how they consume and replenish the budget)
A periodic server is
backlogged whenever the aperiodic job queue is non-empty
idle if the queue is empty
eligible if it is backlogged and the budget is not exhausted
When a periodic server is eligible, it is scheduled as any
other periodic task with parameters (pS, eS)
115
Periodic Severs
Each periodic server is thus specified by
consumption rules: How the budget is consumed
replenishment rules: When and how the budget is
replenished
Polling server
consumption rules:
Whenever the server executes, the budget is consumed at
the rate one per unit time.
Whenever the server becomes idle, the budget gets
immediately exhausted
replenishment rule: At each time instant k · pS replenish
the budget to eS
116
Periodic Severs
Deferrable sever
Consumption rules:
The budget is consumed at the rate of one per unit time
whenever the server executes
Unused budget is retained throughout the period, to be
used whenever there are aperiodic jobs to execute
(i.e. instead of discarding the budget if no aperiodic job to execute
at start of period, keep in the hope a job arrives)
Replenishment rule:
The budget is set to eS at multiples of the period
i.e. time instants k · pS for k = 0, 1, 2, . . .
(Note that the server is not able tu cumulate the budget over
periods)
We consider both
Fixed-priority scheduling
Dynamic-priority scheduling (EDF)
117
Deferrable Server – RM
Here the tasks are scheduled using RM.
Is it possible to increase the budget of the server to 1.5 ?
118
Deferrable Server – RM
Consider T1 = (3.5, 1.5), T2 = (6.5, 0.5) and TDS = (3, 1)
A critical instant for T1 = (3.5, 1.5) looks as follows:
i.e. increasing the budget above 1 may cause T1 to miss its
deadline
119
Deferrable Server – Critical Instant
Lemma 19
Assume a fixed-priority scheduling algorithm. Assume that
Di ≤ pi and that the deferrable server (pS, eS) has the highest
priority among all tasks. Then a critical instant of every periodic
task Ti occurs at a time t0 when all of the following are true:
One of its jobs Ji,c is released at t0
A job in every higher-priority periodic task is released at t0
The budget of the server is eS at t0, one or more aperiodic
jobs are released at t0, and they keep the server
backlogged hereafter
The next replenishment time of the server is t0 + eS
120
Deferrable Server – Critical Instant
Assume TDS T1 T2 · · · Tn
(i.e. T1 has the highest pririty and Tn lowest)
121
Deferrable Server – Time Demand Analysis
Assume that the deferrable server has the highest priority
The definition of critical instant is identical to that for the
periodic tasks without the deferrable server +
the worst-case requirements for the server
Thus the expression for the time-demand function
becomes
wi(t) = ei +
i−1
k=1
t
pk
ek +eS +
t − eS
pS
eS for 0 < t ≤ pi
To determine whether the task Ti is schedulable, we simply
check whether wi(t) ≤ t for some t ≤ Di
Note that this is a sufficient condition, not necessary.
Check whether wi(t) ≤ t for some t equal either
to Di, or
to j · pk where k = 1, 2, . . . , i and j = 1, 2, . . . , Di/pk , or
to eS, eS + pS, eS + 2pS, . . . , eS + (Di − ei)/pS pS
122
Deferrable Server – Time Demand Analysis
TDS = (3, 1.0), T1 = (3.5, 1.5), T2 = (6.5, 0.5)
123
Deferrable Server – Schedulable Utilization
No maximum schedulable utilization is known in general
A special case:
A set T of n independent, preemptable periodic tasks
whose periods satisfy pS < p1 < · · · < pn < 2pS and
pn > pS + eS and whose relative deadlines are equal to
their respective periods, can be scheduled according to RM
with a deferrable server provided that
UT
≤ URM/DS(n) := (n − 1)


uS + 2
uS + 1
1
n−1
− 1


where uS = eS/pS
124
Deferrable Server – EDF
Here the tasks are scheduled using EDF.
TDS = (3, 1), T1 = (2, 3.5, 1.5), T2 = (6.5, 0.5)
125
Deferrable Server – EDF – Schedulability
Theorem 20
A set of n independent, preemptable, periodic tasks satisfying
pi ≤ Di for all 1 ≤ i ≤ n is schedulable with a deferrable server
with period pS, execution budget eS and utilization uS = eS/pS
according to the EDF algorithm if:
n
k=1
uk + uS 1 +
pS − eS
mini Di
≤ 1
126
Sporadic Server – Motivation
Problem with polling server: TPS = (pS, eS) executes
aperiodic tasks at the multiples of pS
Problem with deferrable server: TDS = (pS, eS) may delay
lower priority jobs longer than periodic task (pS, eS)
Therefore special version of time-demand analysis and utilization
bounds were needed.
Sporadic server TSS = (eS, pS)
may execute jobs “in the middle” of its period
never delays periodic tasks for longer time than the periodic
task (pS, eS)
Thus can be tested for schedulability as an ordinary periodic task.
Originally proposed by Sprunt, Sha, Lehoczky in 1989
original version contains a bug which allows longer delay of lower priority jobs
Part of POSIX standard
also incorrect as observed and (probably) corrected by Stanovich in 2010
127
Very Simple Sporadic Server
For simplicity, we consider only fixed priority scheduling, i.e. assume
T1 T2 · · · Tn and consider a sporadic server TSS = (pS, eS) with
the highest priority
Notation:
tr = the latest replenishment time
tf = first instant after tr at which server begins to execute
nr = a variable representing the next replenishment
Consumption rule: The budget is consumed (at the rate of one
per unit time) whenever the current time t satisfies t ≥ tf
Replenishment rules: At the beginning, tr = nr = 0
Whenever the current time is equal to nr , the budget is set
to eS and tr is set to the current time
At the first instant tf after tr at which the server starts
executing, nr is set to tf + pS
(Note that such server resembles a periodic task with the highest priority
whose jobs are released at times tf and execution times are at most eS ) 128
Very Simple Sporadic/Background Server
New notation:
tr = the latest replenishment time
tf = first instant after tr at which server begins to execute and at
least one task of T is not idle
nr = a variable representing the next replenishment
Consumption rule: The budget is consumed (at the rate of one
per unit time) whenever the current time t satisfies t ≥ tf and at
least one task of T is not idle
Replenishment rules: At the beginning, tr = nr = 0
Whenever the current time is equal to nr , the budget is set
to eS and tr is set to the current time
At the beginning of an idle interval of T , the budget is set to
eS and nr is set to the end of this interval
At the first instant tf after tr at which the server starts
executing and T is not idle, nr is set to tf + pS
This combines the very simple sporadic server with background scheduling.
129
Very Simple Sporadic Server
Correctness (informally):
Assuming that T never idles, the sporadic server resembles a
periodic task with the highest priority whose jobs are released
at times tf and execution times are at most eS
Whenever T idles, the sporadic server executes in the
background, i.e. does not block any periodic task, hence does
not consume the budget
Whenever an idle interval of T ends, we may treat this situation
as a restart of the system with possibly different phases of
tasks (so that it is safe to have the budget equal to eS)
Note that in both versions of the sporadic server, eS units of
execution time are available for aper. jobs every pS units of time
This means that if the server is always backlogged, then it executes for eS
time units every pS units of time
130
Real-Time Scheduling
Priority-Driven Scheduling
Sporadic Tasks
131
Current Assumptions
Single processor
Fixed number, n, of independent periodic tasks, T1, . . . , Tn
where Ti = (ϕi, pi, ei, Di)
Jobs can be preempted at any time and never suspend
themselves
No resource contentions
Sporadic tasks
Independent of the periodic tasks
Jobs can be preempted at any time
Aperiodic tasks
For simplicity scheduled in the background – i.e. we may ignore them
Jobs are scheduled using a priority driven algorithm
A sporadic job = a job of a sporadic task
132
Our situation
Based on the execution time and deadline of each newly arrived
sporadic job, decide whether to accept or reject the job
Accepting the job implies that the job will complete within its
deadline, without causing any periodic job or previously
accepted sporadic job to miss its deadline
Do not accept a sporadic job if cannot guarantee it will meet its
deadline 133
Scheduling Sporadic Jobs – Correctness and
Optimality
A correct schedule is one where all periodic tasks, and all
sporadic jobs that have been accepted, meet their deadlines
A scheduling algorithm supporting sporadic jobs is a correct
algorithm if it only produces correct schedules for the system
A sporadic job scheduling algorithm is optimal if it accepts a new
sporadic job, and schedules that job to complete by its deadline,
iff the new job can be correctly scheduled to complete in time
134
Model for Scheduling Sporadic Jobs with EDF
Assume that all jobs in the system are scheduled by EDF
if more sporadic jobs are released at the same time their
acceptance test is done in the EDF order
Definitions:
Sporadic jobs are denoted by S(r, d, e) where r is the
release time, d the (absolute) deadline, and e is the
maximum execution time
The density of S(r, d, e) is defined by e/(d − r)
The total density of a set of sporadic jobs is the sum of
densities of these jobs
The sporadic job S(r, d, e) is active at time t iff t ∈ (r, d]
Note that each job of a periodic task (ϕ, p, e, D) can be seen as a
sporadic job; to simplify, we assume that always D ≤ p.
This in turn means that there is always at most one job of a given task active
at a given time instant.
For every job of this task released at r with abs. deadline d, we obtain
the density e/(d − r) = e/D 135
Schedulability of Sporadic Jobs with EDF
Theorem 21
A set of independent preemptable sporadic jobs is schedulable
according to EDF if at every time instant t the total density of all
jobs active at time t is at most one.
Proof.
By contradiction, suppose that a job misses its deadline at t, no
deadlines missed before t
Let t−1 be the supremum of time instants before t when either the
system idles, or a job with a deadline after t executes
Suppose that jobs J1, . . . , Jk execute in [t−1, t] and that they are
ordered w.r.t. increasing deadline (Jk misses its deadline at t)
Let L be the number of releases and completions in [t−1, t], denote by
ti the i-th time instant when i-th such event occurs (then t−1 = t1, we
denote by tL+1 the time instant t)
Denote by Xi the set of all jobs that are active during the interval
(ti, ti+1] and let ∆i be their total density
The rest on whiteboard ....
136
Sporadic Jobs with EDF – Example
Note that the above theorem includes both the periodic as well
as sporadic jobs
This test is sufficient but not necessary
Example 22
Three sporadic jobs: S1(0, 2, 1), S2(0.5, 2.5, 1), S3(1, 3, 1)
Total density at time 1.5 is 1.5
Yet, the jobs are schedulable by EDF
137
Admission Control for Sporadic Jobs with EDF
Let ∆ be the total density of periodic tasks.
Assume that a new sporadic job S(t, d, e) is released at time t.
At time t there are n active sporadic jobs in the system
The EDF scheduler maintains a list of the jobs, in
non-decreasing order of their deadlines
The deadlines partition the time from t to ∞ into n + 1
discrete intervals I1, I2, . . . , In+1
I1 begins at t and ends at the earliest sporadic job deadline
For each 1 ≤ k ≤ n, each Ik+1 begins when the interval Ik
ends, and ends at the next deadline in the list (or ∞ for In+1)
The scheduler maintains the total density ∆S,k of sporadic
jobs active in each interval Ik
Let I be the interval containing the deadline d of the new
sporadic job S(t, d, e)
The scheduler accepts the job if e/(d − t) + ∆S,k ≤ 1 − ∆
for all k = 1, 2, . . . ,
i.e. accept if the new sporadic job can be added, without
increasing density of any intervals past 1
138
139
Admission Control for Sporadic Jobs with EDF
This acceptance test is not optimal: a sporadic job may be
rejected even though it could be scheduled.
The test is based on the density and hence is sufficient but
not necessary.
It is possible to derive a – much more complex –
expression for schedulability which takes into account
slack time, and is optimal. Unclear if the complexity is
worthwhile.
140
Sporadic Jobs with EDF
One way to schedule sporadic jobs in a fixed-priority system is
to use a sporadic server to execute them
Because the server (pS, eS) has eS units of processor time
every pS units of time, the scheduler can compute the least
amount of time available to every sporadic job in the system
Assume that sporadic jobs are ordered among themselves
according to EDF
When first sporadic job S1(t, dS,1, eS,1) arrives, there is at
least
(dS,1 − t)/pS eS
units of processor time available to the server before the
deadline of the job
Therefore it accepts S1 if the slack of the job
σS,1(t) = (dS,1 − t)/pS eS − eS,1 ≥ 0
141
Sporadic Jobs with EDF
To decide if a new job Si(t, dS,i, eS,i) is acceptable when
there are n sporadic jobs in the system, the scheduler first
computes the slack σS,i(t) of Si:
σS,i(t) = (dS,i − t)/pS eS − eS,i −
dS,k <dS,i
(eS,k − ξS,k )
where ξS,k is the execution time of the completed part of
the existing job Sk
Note that the sum is taken over sporadic jobs with earlier deadline as Si
since sporadic jobs are ordered according to EDF
The job cannot be accepted if σS,i(t) < 0
If σS,i(t) ≥ 0, the scheduler checks if any existing sporadic
job Sk with deadline equal to, or after dS,i may be adversely
affected by the acceptance of Si, i.e. check if σS,k (t) ≥ eS,i
142
Real-Time Scheduling
Resource Access Control
[Some parts of this lecture are based on a real-time systems course
of Colin Perkins
http://csperkins.org/teaching/rtes/index.html]
143
Current Assumptions
Single processor
Individual jobs
(that possibly belong to periodic/aperiodic/sporadic tasks)
Jobs can be preempted at any time and never suspend
themselves
Jobs are scheduled using a priority-driven algorithm
i.e., jobs are assigned priorities, scheduler executes jobs according to
these priorities
n resources R1, . . . , Rn of distinct types
used in non-preemptable and mutually exclusive manner;
serially reusable
144
Motivation & Notation
Resources may represent:
Hardware devices such as sensors and actuators
Disk or memory capacity, buffer space
Software resources: locks, queues, mutexes etc.
Assume a lock-based concurrency control mechanism
A job wanting to use a resource Rk executes L(Rk ) to lock the
resource Rk
When the job is finished with the resource Rk , unlocks this
resource by executing U(Rk )
If lock request fails, the requesting job is blocked and has to
wait, when the requested resource becomes available, it is
unblocked
In particular, a job holding a lock cannot be preempted by a higher
priority job needing that lock
The segment of a job that begins at a lock and ends at a matching
unlock is a critical section (CS)
CS must be properly nested if a job needs multiple resources 145
Example
J1, J2, J3 scheduled according to EDF.
At 0, J3 is ready and executes
At 1, J3 executes L(R) and is granted R
J2 is released at 2, preempts J3 and begins to execute
At 4, J2 executes L(R), becomes blocked, J3 executes
At 6, J1 becomes ready, preempts J3 and begins to execute
At 8, J1 executes L(R), becomes blocked, and J3 executes
At 9, J3 executes U(R) and both J1 and J2 are unblocked. J1 has higher
priority than J2 and executes
At 11, J executes U(R) and continues executing 146
Priority Inversion
Definition 23
Priority inversion occurs when
a high priority job
is blocked by a low priority job
which is subsequently preempted by a medium priority job
Then effectively the medium priority job executes with higher
priority than the high priority job even though they do not
contend for resources
There may be arbitrarily many medium priority jobs that
preempt the low priority job ⇒ uncontrolled priority inversion
147
Priority Inversion – Example
Uncontrolled priority inversion:
High priority job (J1) can be blocked by low priority job (J3) for
unknown amount of time depending on middle priority jobs (J2)
148
Deadlock
Definition 24 (suitable for resource access control)
A deadlock occurs when there is a set of jobs D such that each
job of D is waiting for a resource previously allocated by
another job of D.
Deadlocks can be
detected: regularly check for deadlock, e.g. search for
cycles in a resource allocation graph regularly
avoided: postpone unsafe requests for resources even
though they are available (banker’s algorithm,
priority-ceiling protocol)
prevented: many methods invalidating sufficient conditions
for deadlock (e.g., impose locking order on resources)
See your operating systems course for more information ....
149
Deadlock – Example
Deadlock can result from piecemeal acquisition of resources: classic
example of two jobs J1 and J2 both needing both resources R and R
J2 locks R and J1 locks R
J1 tries to get R and is blocked
J2 tries to get R and is blocked
150
Timing Anomalies due to Resources
Previous example, the critical section of J3 has length 4
... the critical section of J3 shortened to 2.5
... but response of J1 becomes longer! 151
Controlling Timing Anomalies
Contention for resources causes timing anomalies, priority
inversion and deadlock
Several protocols exist to control the anomalies
Non-preemptive CS
Priority inheritance protocol
Priority ceiling protocol
....
Terminology:
A job Jh is blocked by a job Jk when
the priority of Jk is lower than the priority of Jh and
Jk holds a resource R and
Jh executes L(R).
In such situation we sometimes say that Jh is blocked by
the corresponding critical section of Jk .
152
Non-preemptive Critical Sections
The protocol: when a job locks a resource, it is scheduled with
priority higher than all other jobs (i.e., is non-preemptive)
Example 25
Jobs J1, J2, J3 with release times 2, 5, 0, resp., and with
execution times 4, 5, 7, resp.
153
Non-preemptive Critical Sections – Features
no deadlock as no job holding a resource is ever preempted
no priority inversion:
A job Jh can be blocked (by a lower priority job) only at
release time.
(Indeed, if Jh is not blocked at the release time rh, it means that no
lower priority job holds any resource at rh. However, no lower
priority job can be executed before completion of Jh, and thus no
lower priority job may block Jh.)
If Jh is blocked at release time, then once the blocking
critical section completes, no lower priority job can block Jh.
It follows that any job can be blocked only once, at release
time, blocking time is bounded by duration of one critical
section of a lower priority job.
Advantage: very simple; easy to implement both in fixed and dynamic
priority; no prior knowledge of resource demands of jobs needed
Disadvantage: every job can be blocked by every lower-priority job
with a critical section, even if there is no resource conflict
154
Priority-Inheritance Protocol
Idea: adjust the scheduling priorities of jobs during resource
access, to reduce the duration of timing anomalies
(As opposed to non-preemptive CS protocol, this time the priority is not
always increased to maximum)
Notation:
assigned priority = priority assigned to a job according to
a standard scheduling algorithm
At any time t, each ready job Jk is scheduled and executes
at its current priority πk (t) which may differ from its
assigned priority and may vary with time
The current priority πk (t) of a job Jk may be raised to
the higher priority πh(t) of another job Jh
In such a situation, the lower-priority job Jk is said to inherit
the priority of the higher-priority job Jh, and Jk executes at
its inherited priority πh(t)
155
Priority-Inheritance Protocol
Scheduling rules:
Jobs are scheduled in a preemptable priority-driven manner
according to their current priorities
At release time, the current priority of a job is equal to its
assigned priority
The current priority remains equal to the assigned priority,
except when the priority-inheritance rule is invoked
Priority-inheritance rule:
When a job Jh becomes blocked on a resource R, the job
Jk which blocks Jh inherits the current priority πh(t) of Jh;
Jk executes at its inherited priority until it releases R;
at that time, the priority of Jk is set to the highest priority of
all jobs still blocked by Jk after releasing R.
(the resulting priority may still be an inherited priority)
Resource allocation: When a job J requests a resource R at t:
If R is free, R is allocated to J until J releases it
If R is not free, the request is denied and J is blocked
(Note that J is only denied R if the resource is held by another job.)
156
Priority-Inheritance Simple Example
non-preemptive CS:
priority-inheritance:
At 3, J1 is blocked by J3, J3 inherits priority of J1
At 5, J2 is released but cannot preempt J3 since the inherited priority of
J3 is higher than the (assigned) priority of J2
157
Priority-Inheritance Example
At 0, J5 starts executing at priority 5, at 1 it executes L(Black)
At 2, J4 preempts J5 and executes
At 3, J4 executes L(Shaded), J4 continues to execute
At 4, J3 preempts J4; at 5, J2 preempts J3
At 6, J2 executes L(Black) and is blocked by J5. Thus J5 inherits the
priority 2 of J2 and executes
158
Properties of Priority-Inheritance Protocol
Simple to implement, does not require prior knowledge of
resource requirements
Jobs exhibit two types of "blocking"
(Direct) blocking due to resource locks
i.e., a job J locks a resource R, Jh executes L(R) is directly
blocked by J on R
Priority-inheritance "blocking"
i.e., a job Jh is preempted by a lower-priority job that inherited a
higher priority
Jobs may exhibit transitive blocking
In the previous example, at 9, J5 blocks J4 and J4 blocks J1, hence J5
inherits the priority of J1
Deadlock is not prevented
In the previous example, let J5 request shaded at 6.5, then J4 and J5
become deadlocked
Can reduce blocking time (see next slide) compared to
non-preemptable CS but does not guarantee to minimize
blocking
159
Priority-Inheritance – Blocking Time (Optional)
z ,k = the k-th critical section of J
A job Jh is blocked by z ,k if Jh has higher assigned priority than J but
has to wait for J to exit z ,k in order to continue
β∗
h,
= the set of all maximal critical sections z ,k that may block Jh,
i.e., which correspond to resources that are (potentially) used by jobs
with priorities equal or higher than Jh.
(recall that CS are properly nested, maximal CS which may block Jh is the
one which is not contained within any other CS which may block Jh)
Theorem 26
Let Jh be a job and let Jh+1, . . . , Jh+m be jobs with lower priority than
Jh. Then Jh can be blocked for at most the duration of one critical
section in each of β∗
h,
where ∈ {h + 1, . . . , h + m}.
The theorem is a direct consequence of the next lemma.
160
Lemma 27
Jh can be blocked by J only if J is executing within a critical
section z ,k of β∗
h,
when Jh is released
Assume that Jh is released at t and J is in no CS of β∗
h,
at t. We
show that J never executes between t and completion of Jh:
If J is not in any CS at t, then its current priority at t is
equal to its assigned priority and cannot increase. Thus, J
has to wait for completion of Jh as the current priority of Jh
is always higher than the assigned priority of J .
If J is still in a CS at t, then this CS does not belong to β∗
h,
and thus cannot block Jh before completion and cannot
execute before completion of Jh.
Assume that J leaves z ,k ∈ β∗
h,
at time t. We show that J never
executes between t and completion of Jh:
If J is not in any CS at t, then, as above, J never executes
before completion of Jh and cannot block Jh.
If J is still in a CS at t, then this CS does not belong to β∗
h,
because otherwise z ,k would not be maximal. Thus J
cannot block Jh, and thus J is never executed before
completion of Jh. 161
Priority-Inheritance – The Worst Case
J1 is blocked for the total duration of all critical sections in all lower
priority jobs.
162
Priority-Ceiling Protocol
The goal: to furhter reduce blocking times due to resource contention
and to prevent deadlock
in its basic form priority-ceiling protocol works under the
assumption that the priorities of jobs and resources required by
all jobs are known apriori
can be extended to dynamic priority (job-level fixed priority), see later
Notation:
The priority ceiling of any resource Rk is the highest priority of all
the jobs that require Rk and is denoted by Π(Rk )
At any time t, the current priority ceiling Π(t) of the system is
equal to the highest priority ceiling of the resources that are in
use at the time
If all resources are free, Π(t) is equal to Ω, a newly introduced
priority level that is lower than the lowest priority level of all jobs
163
Priority-Ceiling Protocol
The scheduling and priority-inheritance rules are the same as for
priority-inheritance protocol
Scheduling rules:
Jobs are scheduled in a preemptable priority-driven manner
according to their current priorities
At release time, the current priority of a job is equal to its
assigned priority
The current priority remains equal to the assigned priority,
except when the priority-inheritance rule is invoked
Priority-inheritance rule:
When job Jh becomes blocked on a resource R, the job Jk
which blocks Jh inherits the current priority πh(t) of Jh;
Jk executes at its inherited priority until it releases R;
at that time, the priority of Jk is set to the highest priority of
all jobs still blocked by Jk after releasing R.
(which may still be an inherited priority)
164
Priority-Ceiling Protocol
Resource allocation rules:
When a job J requests a resource R held by another job, the
request fails and the requesting job blocks
When a job J requests a resource R at time t, and that resource
is free:
If J’s priority π(t) is strictly higher than current priority
ceiling Π(t), R is allocated to J
If J’s priority π(t) is not higher than Π(t), R is allocated to J
only if J is the job holding the resource(s) whose priority
ceiling is equal to Π(t), otherwise J is blocked
(Note that only one job may hold the resources whose priority
ceiling is equal to Π(t))
Note that unlike priority-inheritance protocol, the priority-ceiling
protocol can deny access to an available resource.
165
Priority-Ceiling Protocol
At 1, Π(t) = Ω, J5 executes L(Black), continues executing
At 3, Π(t) = 2, J4 executes L(Shaded); because the ceiling of the
system Π(t) is higher than the current priority of J4, job J4 is blocked, J5
inherits J4’s priority and executes at priority 4
At 4, J3 preempts J5; at 5, J2 preempts J3. At 6, J2 requests Black and
is directly blocked by J5. Consequently, J5 inherits priority 2 and
executes until preempted by J1
166
Priority-Ceiling Protocol
Theorem 28
Assume a system of preemptable jobs with fixed assigned
priorities. Then
deadlock may never occur,
a job can be blocked for at most the duration of one critical
section.
167
These situations cannot occur with priority ceiling protocol:
168
Differences between the priority-inheritance and
priority-ceiling
Priority-inheritance is greedy, while priority ceiling is not
The priority-ceiling protocol may withhold access to a free
resource, i.e., a job can be prevented from execution by a
lower-priority job which does not hold the requested
resource – avoidance "blocking"
The priority ceiling protocol forces a fixed order onto
resource accesses thus eliminating deadlock
169
Resources in Dynamic Priority Systems
The priority ceiling protocol assumes fixed and known priorities
In a dynamic priority system, the priorities of the periodic tasks
change over time, while the set of resources is required by
each task remains constant
As a consequence, the priority ceiling of each resource
changes over time
What happens if T1 uses resource X, but T2 does not?
Priority ceiling of X is 1 for 0 ≤ t ≤ 4, becomes 2 for
4 ≤ t ≤ 5, etc. even though the set of resources is required
by the tasks remains unchanged
170
Resources in Dynamic Priority Systems
If a system is job-level fixed priority, but task-level dynamic
priority, a priority ceiling protocol can still be applied
Each job in a task has a fixed priority once it is scheduled,
but may be scheduled at different priority to other jobs in
the task (e.g. EDF)
Update the priority ceilings of all resources each time a new
job is introduced; use until updated on next job release
Has been proven to prevent deadlocks and no job is ever
blocked for longer than the length of one critical section
But: very inefficient, since priority ceilings updated
frequently
May be better to use priority inheritance, accept longer
blocking
171
Schedulability Tests with Resources
How to adjust schedulability tests?
Add the blocking times to execution times of jobs; then run the
test as normal
The blocking time bi of a job Ji can be determined for all three
protocols:
non-preemptable CS ⇒ bi is bounded by the maximum
length of a critical section in lower priority jobs
priority-inheritance ⇒ bi is bounded by the total length of
the m longest critical sections where m is the number of
jobs that may block Ji
(For a more precise formulation see Theorem 2.)
priority-ceiling ⇒ bi is bounded by the maximum length of
a critical section
172
Mars Pathfinder vs Priority Inversion
Mars Pathfinder = a US spacecraft that landed
on Mars in July 4th, 1997.
Consisted of a lander and a lightweight
wheeled robotic Mars rover called Sojourner
What Happened:
Few days in to the mission, not long after Pathfinder started
gathering meteorological data, it began experiencing total
system resets, each resulting in losses of data.
Apparently a software problem caused these resets.
The system:
Pathfinder used the well-known real-time embedded
systems kernel VxWorks by Wind River.
VxWorks uses preemptive priority-based scheduling, in this
case a deadline monotonic algorithm.
Pathfinder contained an "information bus" (a shared
memory) used for communication, synchronized by locks.
173
Mars Pathfinder – The Problem
Problematic tasks:
A bus management task ran frequently with high priority to
move data in/out of the bus. If the bus has been locked,
then this thread itself had to wait.
A meteorological data gathering task ran as an infrequent,
low priority thread, and used the bus to publish its data.
The bus was also used by a communication task that ran
with medium priority.
Occasionally the communication task (medium priority) was
invoked at the precise time when the bus management task
(high priority) was blocked by the meteorological data gathering
task (low priority) – priority inversion!
The bus management task was blocked for considerable amount
of time by the communication task, which caused a watchdog
timer to go off, notice that the bus management task has not
been executed for some time, which typically means that
something had gone drastically wrong, and initiate a total system
reset.
174
Mars Pathfinder – Solution
JPL (Jet Propulsion Laboratory) engineers spent hours and
hours running the system on a spacecraft replica.
Early in the morning, after all but one engineer had gone home,
the engineer finally reproduced a system reset on the replica.
Solution: Turn the priority inheritance on!
This was done online using a C language interpreter which allowed to
execute C functions on-the-fly.
A short code changed a mutex initialization parameter from FALSE to
TRUE.
175
Real-Time Scheduling
Multiprocessor Real-Time Systems
176
Multiprocessor Real-time Systems
Many embedded systems are composed of many processors
(control systems in cars, aircraft, industrial systems etc.)
Today most processors in computers have multiple cores
The main reason is that increasing frequency of a single processor is
no more feasible (mostly due to power consumption problems, growing
leakage currents, memory problems etc.)
Applications must be developed specifically for multiprocessor
systems.
177
Multiprocessor Frustration
In case of real-time systems, multiple processors bring serious
difficulties concerning correctness, predictability and efficiency.
The “root of all evil” in global scheduling: (Liu, 1969)
Few of the results obtained for a single processor generalize
directly to the multiple processor case; bringing in additional
processors adds a new dimension to the scheduling problem.
The simple fact that a task can use only one processor even
when several processors are free at the same time adds a
surprising amount of difficulty to the scheduling of multiple
processors.
178
The Model
A job is a unit of work that is scheduled and executed by
a system
(Characterised by the release time ri, execution time ei and deadline di)
A task is a set of related jobs which jointly provide some
system function
Jobs execute on processors
In this lecture we consider m processors
Jobs may use some (shared) passive resources
179
Schedule
Schedule assigns, in every time instant, processors and resources to
jobs.
A schedule is feasible if all jobs with hard real-time constraints
complete before their deadlines.
A set of jobs is schedulable if there is a feasible schedule for the set.
A scheduling algorithm is optimal if it always produces a feasible
schedule whenever such a schedule exists.
(and if a cost function is given, minimizes the cost)
We also consider online scheduling algorithms that do not use any
knowlede about jobs that will be released in the future but are given
a complete information about jobs that have been released.
(e.g. EDF is online)
180
Multiprocessor Taxonomy
Identical processors: All processors identical, have the same
computing power
Uniform processors: Each processor is characterized by its own
computing capacity κ, completes κt units of execution after t
time units
Unrelated processors: There is an execution rate ρij associated
with each job-processor pair (Ji, Pj) so that Ji completes ρijt
units of execution by executing on Pj for t time units
In addition, cost of communication can be included etc.
181
Assumptions – Priority Driven Scheduling
Throughout this lecture we assume:
Unless otherwise stated, consider m identical processors
Jobs can be preempted at any time and never suspend
themselves
Context switch overhead is negligibly small
i.e. assumed to be zero
There is an unlimited number of priority levels
For simplicity, we assume independent jobs that do not contend
for resources
Unless otherwise stated, we assume that scheduling decisions take
place only when a job is released, or completed.
182
Multiprocessor Scheduling Taxonomy
Multiprocessor scheduling attempts to solve two problems:
the allocation problem, i.e., on which processor a given job
executes
the priority problem, i.e., when and in what order the jobs
execute
183
Issues
What results from single processor scheduling remain valid in
multiprocessor setting?
Are there simple optimal scheduling algorithms?
Are there optimal online scheduling algorithms
(i.e. those that do not know what jobs come in future)
Are there efficient tests for schedulability?
In this lecture we consider:
Individual jobs
Periodic tasks
Start with n individual jobs {J1, . . . , Jn}
184
Individual Jobs – Timing Anomalies
Priority order: J1 · · · J4
185
Individual Jobs – EDF
EDF on m identical processors: At any time instant, jobs with
the earliest absolute deadlines are executed on available processors.
(Recall: no job can be executed on more than one processor at a given time!)
Is this optimal? NO!
Example:
J1, J2, J3 where
ri = 0 for i ∈ {1, 2, 3}
e1 = e2 = 1 and e3 = 5
d1 = 1, d2 = 2, d3 = 5
186
Individual Jobs – Online Scheduling
Theorem 29
No optimal on-line scheduler can exist for a set of jobs with two or
more distinct deadlines on any m > 1 processor system.
Proof.
Assume m = 2 and consider three jobs J1, J2, J3 are released at time
0 with the following parameters:
e1 = e2 = 2 and e3 = 4
d1 = d2 = 4 and d3 = 8
Depending on scheduling in [0, 2], new tasks T4, T5 are released at 2:
If J3 is executed in [0, 2], then at 2 release J4, J5 with d4 = d5 = 4
and e4 = e5 = 2.
If J3 is not executed in [0, 2], then at 4 release J4, J5 with
d4 = d5 = 8 and e4 = e5 = 4.
In either case the schedule produced is not feasible. However, if the
scheduler is given either of the sets {J1, . . . , J5} at the beginning, then
there is a feasible schedule.
187
Individual Jobs – Speedup Helps(?)
Theorem 30
If a set of jobs is feasible on m identical processors, then the same
set of jobs will be scheduled to meet all deadlines by EDF on identical
processors in which the individual processors are (2 − 1
m ) times as
fast as in the original system.
The result is tight for EDF (assuming dynamic job priority):
Theorem 31
There are sets of jobs that can be feasibly scheduled on m identical
processors but EDF cannot schedule them on m processors that are
only (2 − 1
m − ε) faster for every ε > 0.
... there are also general lower bounds for online algorithms:
Theorem 32
There are sets of jobs that can be feasibly scheduled on m (here m is
even) identical processors but no online algorithm can schedule
them on m processors that are only (1 + ε) faster for every ε < 1
5 .
[Optimal Time-Critical Scheduling Via Resource Augmentation, Phillips et al, STOC 1997]
188
Reactive Systems
Consider fixed number, n, of independent periodic tasks
T = {T1, . . . , Tn}
i.e. there is no dependency relation among jobs
Unless otherwise stated, assume no phase and deadlines equal
to periods
Ignore aperiodic tasks
No sporadic tasks unless otherwise stated
Utilization ui of a periodic task Ti with period pi and execution time ei
is defined by ui := ei/pi
ui is the fraction of time a periodic task with period pi and execution time ei
keeps a processor busy
Total utilization UT
of a set of tasks T = {T1, . . . , Tn} is defined as the
sum of utilizations of all tasks of T , i.e. by UT
:= n
i=1 ui
Given a scheduling algorithm ALG, the schedulable utilization UALG of
ALG is the maximum number U such that for all T : UT ≤ U implies T
is schedulable by ALG.
189
Multiprocessor Scheduling Taxonomy
Allocation (migration type)
No migration: each task is allocated to a processor
(Task-level migration: jobs of a task may execute on different
processors; however, each job is assigned to a single processor)
Job-level migration: A single job can migrate and execute on
different processors
(however, parallel execution of one job is not permitted and migration
takes place only when the job is rescheduled)
Priority type
Fixed task-level priority (e.g. EDF)
Fixed job-level priority (e.g. RM)
(Dynamic job-level priority)
Partitioned scheduling = No migration
Global scheduling = job-level migration
190
Fundamental Limit – Fixed Job-Level Priority
Consider m processors and m + 1 tasks T = {T1, . . . , Tm+1}, each
Ti = (L, 2L − 1).
Then
UT = m+1
i=1 L/(2L −1) = (m +1) (L/(2L − 1)) = (m +1)/2·L/(L −1)
For very large L, this number is close to (m + 1)/2.
The set T is not schedulable using any fixed job-level priority
algorithm.
In other words, the schedulable utilization of fixed job-level priority
algorithms is at most (m + 1)/2, i.e., half of the processors capacity.
There are variants of EDF achieving this bound (see later slides).
191
Partitioned vs Global Scheduling
Most algorithms up to the end of 1990s based on partitioned
scheduling
no migration
From the end of 1990s, many results concerning global
scheduling
job-level migration
The task-level migration has not been much studied, so it is not covered in
this lecture.
We consider fixed job-level priority (e.g. EDF) and fixed
task-level priority (e.g. RM).
As before, we ignore dynamic job-level priority.
192
Partitioned Scheduling & Fixed Job-Level Priority
The algorithm proceeds in two phases:
1. Allocate tasks to processors, i.e., partition the set of tasks into m
possibly empty modules M1, . . . , Mm
2. Schedule tasks of each Mi on the processor i according to
a given single processor algorithm
The quality of task assignment is determined by the number of
assigned processors
Use EDF to schedule modules
Suffices to test whether the total utilization of each module is ≤ 1
(or, possibly, ≤ ˆU where ˆU < 1 in order to accomodate aperiodic jobs ...)
Finding an optimal schedule is equivalent to a simple uniform-size
bin-packing problem (and hence is NP-complete)
Similarly, we may use RM for fixed task-level priorities (total utilization in
modules ≤ log 2, etc.)
193
Global Scheduling
All ready jobs are kept in a global queue
When selected for execution, a job can be assigned to any
processor
When preempted, a job goes to the global queue (i.e.,
forgets on which processor it executed)
194
Global Scheduling – Fixed Job-Level Priority
Dhall’s effect:
Consider m > 1 processors
Let ε > 0
Consider a set of tasks T = {T1, . . . , Tm, Tm+1} such that
Ti = (2ε, 1) for 1 ≤ i ≤ m
Tm+1 = (1, 1 + ε)
T is schedulable
Stadnard EDF and RM schedules are not feasible (whiteb.)
However,
UT = m
2ε
1
+
1
1 + ε
which means that for small ε the utilization UT is close to 1
(i.e., UT /m is very small for m >> 0 processors)
195
How to avoid Dhall’s effect?
Note that RM and EDF only account for task periods and
ignore the execution time!
(Partial) Solution: Dhall’s effect can be avoided by giving
high priority to tasks with high utilization
Then in the previous example, Tm+1 is executed whenever
it comes and the other tasks are assigned to the remaining
processors – produces a feasible schedule
196
Global Scheduling – Fixed Job-Level Priority
Apparently there is a problem with long jobs due to Dhall’s effect.
There is an improved version of EDF called EDF-US(1/2) which
assigns the highest priority to tasks with ui ≥ 1/2
assigns priorities to the rest according to deadlines
which reaches the generic schedulable utilization bound (m + 1)/2.
197
Partitioned vs Global
Advantages of the global scheduling:
Load is automatically balanced
Better average response time (follows from queueing theory)
Disadvantages of the global scheduling:
Problems caused by migration (e.g. increased cache misses)
Schedulability tests more difficult (active area of research)
Is either of the approaches better from the schedulability standpoint?
198
Global Beats Partitioned
There are sets of tasks schedulable only with global scheduler:
T = {T1, T2, T3} where T1 = (1, 2), T2 = (2, 3), T3 = (2, 3),
can be scheduled using a global scheduler:
No feasible partitioned schedule exists, always at least one
processor gets tasks with total utilization higher than 1.
199
Partitioned Beats Global
There are task sets that can be scheduled only with partitioned
scheduler (assuming fixed task-level priority assignment):
T = {T1, . . . , T4} where
T1 = (2, 3), T2 = (3, 4), T3 = (5, 15), T4 = (5, 20), can be
scheduled using a fixed task-level priority partitioned schedule:
Global scheduling (fixed job-level priority): There are 9 jobs
released in the interval [0, 12). Any of the 9! possible priority
assignments leads to a deadline miss.
200
Optimal Algorithm?
There IS an optimal algorithm in the case of job-level migration &
dynamic job-level priority. However, the algorithm is time driven.
The priority fair (PFair) algorithm is optimal for periodic systems with
deadlines equal to periods
Idea (of PFair): In any interval (0, t] jobs of a task Ti with utilization ui
execute for amount of time W so that uit − 1 < W < uit + 1
(Here every parameter is assumed to be a natural number)
This is achieved by cutting time into small quanta and scheduling jobs
in these quanta so that the execution times are always (more or less)
in proportion.
There are other optimal algorithms, all of them suffer from a large
number of preemptions/migrations.
No optimal algorithms are known for more general settings: deadlines
bounded by periods, arbitrary deadlines.
Recall, that no optimal on-line scheduling possible
201
Real-Time Programming & RTOS
Concurrent and real-time programming tools
202
Concurrent Programming
Concurrency in real-time systems
typical architecture of embedded real-time system:
several input units
computation
output units
data logging/storing
i.e., handling several concurrent activities
concurrency occurs naturally in real-time systems
Support for concurrency in programming languages (Java, Ada, ...)
advantages: readability, OS independence, checking of interactions by
compiler, embedded computer may not have an OS
Support by libraries and the operating system (C/C++ with POSIX)
advantages: multi-language composition, language’s model of concurrency
may be difficult to implement on top of OS, OS API stadards imply portability
203
Processes and Threads
Process
running instance of a program,
executes its own virtual machine to avoid interference from
other processes,
contains information about program resources and
execution state, e.g.:
environment, working directory, ...
program instructions,
registers, heap, stack,
file descriptors,
signal actions, inter-process communication tools (pipes,
message boxes, etc.)
Thread
exists within a process, uses process resources ,
can be scheduled by OS and run as an independent entity,
keeps its own: execution stack, local data, etc.
share global data and resources with other threads of
the same process
204
Processes and threads in UNIX
205
Process (Thread) States
206
Communication and Synchronization
Communication
passing of information from one process (thread) to
another
typical methods: shared variables, message passing
Synchronization
satisfaction of constraints on the interleaving of actions of
processes
e.g. action of one process has to occur after an action of another one
typical methods: semaphores, monitors
Communication and synchronization are linked:
communication requires synchronization
synchronization corresponds to communication without
content
207
Communication: Shared Variables
Consistency problems:
unrestricted use of shared variables is unreliable
multiple update problem
example: shared variable X, assignment X := X + 1
load the current value of X into a register
increment the value of the register
store the value of the register back to X
two processes executing these instruction ⇒ certain
interleavings can produce inconsistent results
Solution:
parts of the process that access shared variables (i.e. critical
sections) must be executed indivisibly with respect to each other
required protection is called mutual exclusion
... one may use a special mutual ex. protocol (e.g. Peterson) or a
synchronization mechanism – semaphores, monitors
208
Synchronization: Semaphores
A sempahore contains an integer variable that, apart from
initialization, is accessed only through two standard operations:
wait() and signal().
semaphore is initialized to a non-negative value (typically 1)
wait() operation: decrements the semaphore value if the value
is positive; otherwise, if the value is zero, the caller becomes
blocked
signal() operation: increments the semaphore value; if the
value is not positive, then one process blocked by the
semaphore is unblocked (usually in FIFO order)
both wait and signal are atomic
Semaphores are elegant low-level primitive but error prone and hard
to debug (deadlock, missing signal, etc.)
For more details see an operating systems course.
209
Synchronization: Monitors
encapsulation and efficient condition synchronization
critical regions are written as procedures; all encapsulated in
a single object or module
procedure calls into the module are guaranteed to be mutually
exclusive
shared resources accessible only by these procedures
For more details (such as condition variables) see an operating
systems course.
210
Communication: Message Passing
Communication among two, or more processes where there is no
shared region between the two processes. Instead they communicate
by passing messages.
synchronous (rendezvous): send and receive operations are
blocking, no buffer required
asynchronous (no-wait): send operation is not blocking,
requires buffer space (mailbox)
remote invocation (extended rendezvous): sender is blocked
until reply is received
211
Synchronous Message Passing
212
Asynchronous Message Passing
213
Asynch. Message Passing with Bounded Buffer
214
Concurrent Programming is Complicated
Multi-threaded applications with shared data may have
numerous flaws.
Race condition
Two or more threads try to access the same shared data, the result
depends on the exact order in which their instructions are executed
Deadlock
occurs when two or more threads wait for each other, forming a cycle
and preventing all of them from making any forward progress
Starvation
an idefinite delay or permanent blocking of one or more runnable
threads in a multithreaded application
Livelock
occurs when threads are scheduled but are not making forward
progress because they are continuously reacting to each other’s state
changes
Usually difficult to find bugs and verify correctness.
215
Real-Time Aspects
time-aware systems make explicit references to the time
frame of the enclosing environment
e.g. a bank safe’s door are to be locked from midnight to nine o’clock
the "real-time" of the environment must be available
reactive systems are typically concerned with relative
times
an output has to be produced within 50 ms of an associated input
must be able to measure intervals
usually must synchronize with environment: input sampling
and output signalling must be done very regularly with
controlled variability
216
The Concept of Time
Real-time systems must have a concept of time – but what is time?
Measure of a time interval
Units?
seconds, milliseconds, cpu cycles, system "ticks"
Granularity, accuracy, stability of the clock source
Is "one second" a well defined measure?
"A second is the duration of 9,192,631,770 periods of the
radiation corresponding to the transition between the two
hyperfine levels of the ground state of the caesium-133
atom."
... temperature dependencies and relativistic effects
(the above definition refers to a caesium atom at rest, at
mean sea level and at a temperature of 0 K)
Skew and divergence among multiple clocks
Distributed systems and clock synchronization
Measuring time
external source (GPS, NTP, etc.)
internal – hardware clocks that count the number of
oscillations that occur in a quartz crystal
217
Requirements for Interaction with "time"
For RT programming, it is desirable to have:
access to clocks and representation of time
delays
timeouts
(deadline specification and real-time scheduling)
218
Access to Clock and Representation of Time
requires a hardware clock that can be read like a regular
external device
mostly offered by an OS service, if direct interfacing to
the hardware is not allowed
Example of time representation: (POSIX high resolution clock, counting
seconds and nanoseconds since 1970 with known resolution)
struct timespec {
time_t tv_sec;
long tv_nsec;
}
int clock_gettime( clockid_t clock_id,
struct timespec * tp );
int clock_settime( clockid_t id,
const struct timespec * tp );
Time is often kept by incrementing an integer variable, need to take
case of overflows (i.e. jumps to the past).
219
Delays
In addition to having access to a clock, need ability to
Delay execution until an arbitrary calendar time
What about daylight saving time changes? Problems with leap seconds.
Delay execution for a relative period of time
Delay for t seconds
Delay for t seconds after event e begins
220
A Repeated Task (An Attempt)
The goal is to do work repeatedly every 100 time units
while(1) {
delay(100);
do_work();
}
Does it work as intended? No, accumulates drift ...
Each turn in the loop will take at least 100 + x milliseconds,
where x is the time taken to perform do_work() 221
A Repeated Task (An Attempt)
The goal is to do work repeatedly every 100 time units
while(1) {
delay(100);
do_work();
}
Does it work as intended? No, accumulates drift ...
Delay is just lower bound, a delaying process is not guaranteed
access to the processor (the delay does not compensate for this)
222
Eliminating (Part of) The Drift: Timers
Set an alarm clock, do some work, and then wait for
whatever time is left before the alarm rings
This is done with timers
Thread is told to wait until the next ring – accumulating drift
is eliminated
Two types of timers
one-shot
After a specified interval call an associated function.
periodic (also called auto-reload timer in freeRTOS)
Call the associated function repeatedly, always after the specified
interval.
Even with timers, drift may still occur, but it does not
accumulate (local drift)
223
Timeouts
Synchronous blocking operations can include timeouts
Synchronization primitives
Semaphores, locks, etc.
... timeout usually generates an error/exception
Networking and other I/O calls
E.g. select() in POSIX
Monitors readiness of multiple file descriptors, is ready when the
corresponding operation with the file desc is possible without blocking.
Has a timeout argument that specifies the minimum interval that
select() should block waiting for a file descriptor to become ready.
May also provide an asynchronous timeout signal
Detect time overruns during execution of periodic and
sporadic tasks
224
Deadline specification and real-time scheduling
Clock driven scheduling trivial to implement via cyclic executive.
Other scheduling algorithms need OS and/or language support:
System calls create, destroy, suspend and resume tasks.
Implement tasks as either threads or processes.
Threads usually more beneficial than processes (with separate address
space and memory protection):
Processes not always supported by the hardware
Processes have longer context switch time
Threads can communicate using shared data (fast and
more predictable)
Scheduling support:
Preemptive scheduler with multiple priority levels
Support for aperiodic tasks (at least background
scheduling)
Support for sporadic tasks with acceptance tests, etc.
225
Jobs, Tasks and Threads
In theory, a system comprises a set of (abstract) tasks,
each task is a series of jobs
tasks are typed, have various parameters, react to events,
etc.
Acceptance test performed before admitting new tasks
In practice, a thread (or a process) is the basic unit of work
handled by the scheduler
Threads are the instantiation of tasks that have been
admitted to the system
How to map tasks to threads?
226
Periodic Tasks
Real-time tasks defined to execute periodically T = (φ, p, e, D)
It is clearly inefficient if the thread is created and destroyed
repeatedly every period
Some op. systems (funkOS) and programming languages
(Real-time Java & Ada) support periodic threads
the kernel (or VM) reinitializes such a thread and puts it to
sleep when the thread completes
The kernel releases the thread at the beginning of the next
period
This provides clean abstraction but needs support from OS
Thread instantiated once, performs job, sleeps until next period,
repeats
Lower overhead, but relies on programmer to handle timing
Hard to avoid timing drift due to sleep overuns
(see the discussion of delays earlier in this lecture)
Most common approach
227
Sporadic and Aperiodic Tasks
Events trigger sporadic and aperiodic tasks
Might be extenal (hardware) interrupts
Might be signalled by another task
Usual implementation:
OS executes periodic server thread
(background server, deferrable server, etc.)
OS maintains a “server queue” = a list of pointers which give
starting addresses of functions to be executed by the server
Upon the occurrence of an event that releases an aperiodic or
sporadic job, the event handler (usually an interrupt routine)
inserts a pointer to the corresponding function to the list
228
Real-Time Programming & RTOS
Real-Time Operating systems
229
Operating Systems – What You Should Know ...
An operating system is a collection of software that manages
computer hardware resources and provides common services
for computer programs.
Basic components multi-purpose OS:
Program execution & process management
processes (threads), IPC, scheduling, ...
Memory management
segmentation, paging, protection ...
Storage & other I/O management
files systems, device drivers, ...
Network management
network drivers, protocols, ...
Security
user IDs, privileges, ...
User interface
shell, GUI, ...
230
Operating Systems – What You Should Know ...
231
Implementing Real-Time Systems
Key fact from scheduler theory: need predictable behavior
Raw performance less critical than consistent and
predictable performance; hence focus on scheduling
algorithms, schedulability tests
Don’t want to fairly share resources – be unfair to ensure
deadlines met
Need to run on a wide range of – often custom – hardware
Often resource constrained:
limited memory, CPU, power consumption, size, weight, budget
Closed set of applications
(Do we need a wristwatches to play DVDs?)
Strong reliability requirements – may be safety critical
How to upgrade software in a car engine? A DVD player?
232
Implications on Operating Systems
General purpose operating systems not well suited for
real-time
Assume plentiful resources, fairly shared amongst
untrusted users
Serve multiple purposes
Exactly opposite of an RTOS!
Instead want an operating system that is:
Small and light on resources
Predictable
Customisable, modular and extensible
Reliable
... and that can be demonstrated or proven to be so
233
Implications on Operating Systems
Real-time operating systems typically either cyclic
executive or microkernel designs, rather than a traditional
monolithic kernel
Limited and well defined functionality
Easier to demonstrate correctness
Easier to customise
Provide rich support for concurrency & real-time control
Expose low-level system details to the applications
control of scheduling, interaction with hardware devices, ...
234
Cyclic Executive without Interrupts
The simplest real-time systems use a “nanokernel” design
Provides a minimal time service: scheduled clock pulse
with a fixed period
No tasking, virtual memory/memory protection etc.
Allows implementation of a static cyclic schedule, provided:
Tasks can be scheduled in a frame-based manner
All interactions with hardware to be done on a polled basis
Operating system becomes a single task cyclic executive
235
Microkernel Architecture
Cyclic executive widely used in low-end embedded devices
8 bit processors with kilobytes of memory
Often programmed in (something like) C via cross-compiler,
or assembler
Simple hardware interactions
Fixed, simple, and static task set to execute
Clock driven scheduler
But many real-time embedded systems are more complex,
need a sophisticated operating system with priority
scheduling
Common approach: a microkernel with priority scheduler
Configurable and robust, since architected around interactions between
cooperating system servers, rather than a monolithic kernel with ad-hoc
interactions
236
Microkernel Architecture
A microkernel RTOS typically provides:
Timing services, interrupt handling, support for hardware
interaction
Task management, scheduling
Messaging, signals
Synchronization and locking
Memory management (and sometimes also protection)
237
Example RTOS: FreeRTOS
RTOS for embedded devices (ported to many
microcontrollers from more than 20 manufacturers)
Distributed under GPL
Written in C, kernel consists of 3+1 C source files
(approx. 9000 lines of code including comments)
Largely configurable
238
Example RTOS: FreeRTOS
The OS is (more or less) a library of object modules;
the application and OS modules are linked together in
the resulting executable image
Prioritized scheduling of tasks
tasks correspond to threads (share the same address
space; have their own execution stacks)
highest priority executes; same priority ⇒ round robin
implicit idle task executing when no other task executes ⇒
may be assigned functionality of a background server
Synchronization using semaphores
Communication using message queues
Memory management
no memory protection in basic version (can be extended)
various implementations of memory management
memory can/cannot be freed after allocation, best fit vs
combination of adjacent memory block into a single one
That’s (almost) all .... 239
Example RTOS: FreeRTOS
Tiny memory requirements: e.g. IAR STR71x ARM7 port, full
optimisation, minimum configuration, four priorities ⇒
size of the scheduler = 236 bytes
each queue adds 76 bytes + storage area
each task 64 bytes + the stack size
240
Details of FreeRTOS Scheduling
The scheduler must be explicitly invoked by calling
void vTaskStartScheduler(void) from main().
The scheduler may also stop either due to error, or if one of the tasks
calls void vTaskEndScheduler(void).
It is possible to create a new task by calling
portBASE_TYPE xTaskCreate(
pdTASK_CODE pvTaskCode,
const char * const pcName,
unsigned short usStackDepth,
void *pvParameters,
unsigned portBASE_TYPE uxPriority,
xTaskHandle *pvCreatedTask);
pvTaskCode is a pointer to a function that will be executed as the task,
pcName is a human-readable name of the task, usStackDepth indicates
how many words must be reserved for the task stack, pvParameters is
a pointer to parameters of the task (without interpretation by the OS),
uxPriority is the assigned priority of the task (see resource control
lecture 7), pvCreatedTask is the task handle used by OS routines. 241
Details of FreeRTOS Scheduling
A task can be deleted by means of
void vTaskDelete(xTaskHandle pxTaskToDelete)
Like most other (non-POSIX-compliant) small real-time
systems, does not provide a task cancellation mechanism,
i.e. tasks cannot decline, or postpone deletion –
the deletion is immediate.
Memory is not freed immediately, only the idle task can do it
that must be executed occasionally.
A shared resource owned by a deleted task remains locked.
Priorities are handled by means of uxTaskPriorityGet and
uxTaskPrioritySet. FreeRTOS implements priority inheritance
protocol, the returned priorities are the current ones.
Tasks can be
suspended vTaskSuspend or vTaskSuspendAll
(suspends of but the calling one),
and resumed by vTaskResume or vTaskResumedAll.
Suspend/resume all can be used to implement non-preemptable critical
sections. 242
Clocks & Timers in FreeRTOS
portTickType xTaskGetTickCount(void)
Get current time, in ticks, since the scheduler was started.
The frequency of ticks is determined by configTICK_RATE_HZ
set w.r.t. the HW port.
void vTaskDelay(portTickType xTicksToDelay)
Blocks the calling task for the specified number of ticks.
void vTaskDelayUntil(
portTickType *pxPreviousWakeTime,
portTickType xTimeIncrement
);
Blocks the calling process for xTimeIncrement ticks since
the pxPreviousWakeTime.
(At the wakeup, the pxPreviousWakeTime is incremented by
xTimeIncrement so that it can be readily used to implement periodic
tasks.)
243
Real-Time Programming & RTOS
Real-Time Programming Languages
Brief Overview
244
C and POSIX
IEEE 1003 POSIX
"Portable Operating System Interface"
Defines a subset of Unix functionality, various (optional)
extensions added to support real-time scheduling, signals,
message queues, etc.
Widely implemented:
Unix variants and Linux
Dedicated real-time operating systems
Limited support in Windows
Several POSIX standards for real-time scheduling
POSIX 1003.1b ("real-time extensions")
POSIX 1003.1c ("pthreads")
POSIX 1003.1d ("additional real-time extensions")
Support a sub-set of scheduler features we have discussed
245
POSIX Scheduling API (Threads)
struct sched_param typically contains only sched_priority.
pthread_join suspends execution of the thread until termination of the
thread; retval of the terminating thread is available to any successfully
joined thread. 246
Threads: Example I
#include <pthread.h>
pthread_t id;
void *fun(void *arg) {
// Some code sequence
}
main() {
pthread_create(&id, NULL, fun, NULL);
// Some other code sequence
}
247
Threads: Example II
#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5
void *PrintHello(void *threadid)
{
printf("\n%d: Hello World!\n", threadid);
pthread_exit(NULL);
}
int main (int argc, char *argv[])
{
pthread_t threads[NUM_THREADS];
int rc, t;
for(t=0; t<NUM_THREADS; t++){
printf("Creating thread %d\n", t);
rc = pthread_create(&threads[t], NULL, PrintHello, (void *)t);
if (rc){
printf("ERROR; return code from pthread_create() is %d\n", rc);
exit(-1);
}
}
pthread_exit(NULL);
}
248
POSIX: Synchronization and Communication
Synchronization:
mutexes
(variables that can be locked/unlocked by threads),
(counting) semaphores,
condition variables,
(Used to wait for some condition. The waiting thread is put into a
queue until signaled on the condition variable by another thread.)
...
Communication:
signals (kill(pid,sig)),
message passing,
shared memory.
249
POSIX: Real-Time Support
Getting Time
time() = seconds since Jan 1 1970
gettimeofday() = seconds + nanoseconds since Jan 1
1970
tm = structure for holding human readable time
POSIX requires at least one clock of minimum resolution
50Hz (20ms)
250
POSIX: High Resolution Time & Timers
High resolution clock. Known clock resolution.
struct timespec {
time_t tv_sec;
long tv_nsec;
}
int clock_gettime( clockid_t clock_id,
struct timespec * tp );
int clock_settime( clockid_t id,
const struct timespec * tp );
Simple waiting: sleep, or
Sleep for the interval specified. May return earlier due to signal (in
which case remaining gives the remaining delay).
Accuracy of the delay not known (and not necessarily correlated to
clock_getres() value)
251
POSIX: Timers
type timer_t; can be set:
relative/absolute time
single alarm time and an optional repetition period
timer “rings” according to sevp (e.g. by sending a signal)
int timer_create(clockid_t clockid, struct sigevent *sevp,
timer_t *timerid);
int timer_settime(timer_t timerid, int flags,
const struct itimerspec *new_value,
struct itimerspec * old_value);
where
struct itimerspec {
struct timespec it_interval; /* Timer interval */
struct timespec it_value; /* Initial expiration */
};
252
POSIX Scheduling API
Four scheduling policies:
SCHED_FIFO = Fixed priority, pre-emptive, FIFO on the same
priority level
SCHED_RR = Fixed priority, pre-emptive, round robin on the
same priority level
SCHED_SPORADIC = Sporadic server
SCHED_OTHER = Unspecified (often the default time-sharing
scheduler)
A process can sched_yield() or otherwise block at any time
POSIX 1003.1b provides (largely) fixed priority scheduling
Priority can be changed using sched_set_param(), but this
is high overhead and is intended for reconfiguration rather
than for dynamic scheduling
No direct support for dynamic priority algorithms (e.g. EDF)
Limited set of priorities:
Use sched_get_priority_min(),
sched_get_priority_max() to determine the range
Guarantees at least 32 priority levels 253
Using POSIX Scheduling: Rate Monotonic
Rate monotonic and deadline monotonic schedules can be
naturally implemented using POSIX primitives
1. Assign priorities to tasks in the usual way for RM/DM
2. Query the range of allowed system priorities
sched_get_priority_min() and
sched_get_priority_max()
3. Map task set onto system priorities
Care needs to be taken if there are large numbers of tasks, since some
systems only support a few priority levels
4. Start tasks using assigned priorities and SCHED_FIFO
There is no explicit support for indicating deadlines, periods
EDF scheduling not supported by POSIX
254
Using POSIX Scheduling: Sporadic Server
POSIX 1003.1d defines a hybrid sporadic/background server
When server has budget, runs at sched_priority, otherwise
runs as a background server at sched_ss_low_priority
Set sched_ss_low_priority to be lower priority than real-time tasks, but
possibly higher than other non-real-time tasks in the system
Also defines the replenishment period and the initial budget
after replenishment
255
POSIX-compliant RTOS
Examples of POSIX-compliant implementations:
commercial:
VxWorks
QNX
OSE
Linux-related:
RTLINUX
RTAI
256
Latency
(Some) sources of hard to predict latency caused by the
system:
Interrupts
see next slide
System calls
RTOS should characterise WCET; kernel should be preemptable
Memory management: paging
avoid, either use segmentation with a fixed memory management
scheme, or memory locking
Caches
may introduce non-determinism; there are techniques for computing
WCET with processor caches
DMA
competes with processor for the memory bus, hard to predict who wins
257
Interrupts
The amount of time required to handle interrupt varies
Thus in most OS, interrupt handling is divided into two steps
Immediate interrupt service
very short; invokes a scheduled interrupt handling routine
Scheduled interrupt service
preemptable, scheduled as an ordinary job at a suitable priority
258
Immediate Interrupt Service
Interrupt latency is the time between interrupt request and execution
of the first instruction of the interrupt service routine
The total delay caused by interrupt is the sum of the following factors:
the time the processor takes to complete the current instruction,
do the necessary chores (flush pipeline and read the interrupt
vector), and jump to the trap handler and interrupt dispatcher
the time the kernel takes to disable interrupts
the time required to complete the immediate interrupt service
routines with higher-priority interrupts (if any) that occurred
simultaneously with this one
the time the kernel takes to save the context of the interrupted
thread, identify the interrupting device, and get the starting
address of the interrupt service routine
the time the kernel takes to start the interrupt service routine
259
Event Latency
260
Java
object-oriented programming language
developed by Sun Microsystems in the early 1990s
compiled to bytecode (for a virtual machine), which is
compiled to native machine code at runtime
syntax of Java is largely derived from C/C++
261
Concurrency: Threads
predefined class java.lang.Thread – provides the
mechanism by which threads are created
to avoid all threads having to be child classes of Thread, it
also uses a standard interface:
public interface Runnable {
public abstract void run();
}
any class which wishes to express concurrent execution
must implement this interface and provide the run()
method
262
Threads: Creation & Termination
Creation:
dynamic thread creation, arbitrary data to be passed as
parameters
thread hierarchies and thread groups can be created
Termination:
one thread can wait for another thread (the target) to
terminate by issuing the join method call on the target’s
thread object
the isAlive method allows a thread to determine if the
target thread has terminated
garbage collection cleans up objects which can no longer
be accessed
main program terminates when all its user threads have
terminated
263
Synchronized Methods
monitors are implemented in the context of classes and
objects
lock associated with each object; lock cannot be accessed
directly by the application but is affected by
the method modifier synchronized
block synchronization
synchronized method – access to the method can only
proceed once the lock associated with the object has been
obtained
non-synchronized methods do not require the lock, can be
called at any time
264
Waiting and Notifying
wait() always blocks the
calling thread and releases the
lock associated with the object
notify() wakes up one
waiting thread
which thread is woken is not defined
notifyAll() wakes up all
waiting threads
if no thread is waiting, then
notify() and notifyAll()
have no effect
265
Real-Time Java
Standard Java is not enough to handle real-time constraints
Java (and JVM) lacks semantic for standard real-time
programming techniques.
Embedded Java Specification was there, but merely a subset of
standard Java API.
There is a gap for a language real-time capable and equipped
with all Java’s powerful advantages.
IBM, Sun and other partners formed Real-time for Java Expert
Group sponsored by NIST in 1998
It came up with Real-Time Specification for Java (RTSJ) to fill
this gap for real-time systems
RTSJ proposed seven areas of enhancements to the standard
Java
266
RTSJ – Areas of Enhancement
1. Thread scheduling and dispatching
see the next slides
2. Memory management
immortal memory (no garbage collection), threads not preemptable by
garbage collector
3. Synchronization and resource sharing
priority inheritance and ceiling protocols
4. Asynchronous event handling, asynchronous transfer of
control, asynchronous thread termination
reaction to OS-level signals (POSIX), hardware interrupts and custom
events defined and fired by the application
5. Physical memory access
The resulting real-time extension needs a modified Java virtual
machine due to changes to memory model, garbage collector
and thread scheduling
267
Real-Time Java: Time
java.lang.System.currentTimeMilis returns the number
of milliseconds since Jan 1 1970
Real Time Java adds real time clocks with high resolution
time types
Timers
one shot timers ( javax.realtime.OneShotTimer )
periodic timers ( javax.realtime.PeriodicTimer )
Constructor:
Timer(HighResolutionTime t, Clock c, AsyncEventHandler handler)
... create a timer that fires at time t, according to Clock c and is handled by
the specified handler.
268
Real-Time Thread Scheduling
Extends Java with a schedulable interface and
RealtimeThread class, and numerous supporting libraries
⇒ Allows definition of timing and scheduling parameters,
and memory requirements of threads
Abstract Scheduler and SchedulingParameters classes
defined
Allows a range of schedulers to be developed
Current standards only allow system-defined schedulers;
cannot write a new scheduler without modifying the JVM
Current standards provide a pre-emptive fixed priority
scheduler (PriorityScheduler class)
Allows monitoring of execution times; missed deadlines;
CPU budgets
Allows thread priority to be changed programatically
Limited support for acceptance tests (isFeasible())
269
Real-Time Thread Scheduling
Class hierarchy to express
release timing parameters
Deadline monitoring:
missHandler if deadline
exceeded
Execution time monitoring:
cost = needed CPU time
overrunHandler if
execution time budget
exceeded
270
Real-Time Thread Scheduling
The RealtimeThread class extends Thread with extra
methods and parameters
Direct support for periodic threads
run() method will be a loop ending in a
waitForNextPeriod() call
... i.e. does not have to be implemented using sleep as e.g.
with POSIX API
271
Ada
designed for United States
Department of Defense during
1977-1983
targeted at embedded and
real-time systems
Ada 95 revision
used in critical systems
(avionics, weapon systems,
spacecrafts)
free compiler: gnat
Ada Lovelace
(1815-1852)
... see the lecture of Petr Holub.
272