IA158 Real Time Systems
Tomáš Brázdil
1
Organization of This Course
Sources:
Lectures (slides, notes)
based on several sources (hard to obtain)
slides are prepared for lectures, lots of stuff on whiteboard
(⇒ attend the lectures)
2
Organization of This Course
Sources:
Lectures (slides, notes)
based on several sources (hard to obtain)
slides are prepared for lectures, lots of stuff on whiteboard
(⇒ attend the lectures)
Homework:
a larger project, probably with LEGO mindstorms
2
Organization of This Course
Sources:
Lectures (slides, notes)
based on several sources (hard to obtain)
slides are prepared for lectures, lots of stuff on whiteboard
(⇒ attend the lectures)
Homework:
a larger project, probably with LEGO mindstorms
Evaluation:
Homework project
(have to do to be allowed to the exam)
Oral exam
2
Real-Time Systems
Definition 1 (Time)
Mirriam-Webster: Time is the measured or measurable period during
which an action, process, or condition exists or continues.
3
Real-Time Systems
Definition 1 (Time)
Mirriam-Webster: Time is the measured or measurable period during
which an action, process, or condition exists or continues.
Definition 2 (Real-time)
Real-time is a quantitative notion of time measured using
a physical clock.
Example: After an event occurs (eg. temperature exceeds 500 degrees) the
corresponding action (cooling) must take place within 100ms.
Compare with qualitative notion of time (before, after, eventually, etc.)
3
Real-Time Systems
Definition 1 (Time)
Mirriam-Webster: Time is the measured or measurable period during
which an action, process, or condition exists or continues.
Definition 2 (Real-time)
Real-time is a quantitative notion of time measured using
a physical clock.
Example: After an event occurs (eg. temperature exceeds 500 degrees) the
corresponding action (cooling) must take place within 100ms.
Compare with qualitative notion of time (before, after, eventually, etc.)
Definition 3 (Real-time system)
A real-time system must deliver services in a timely manner.
Not necessarily fast, must satisfy some quantitative timing constraints
3
Real-time Embedded Systems
Definition 4 (Embedded system)
An embedded system is a computer system designed for
specific control functions within a larger system, usually
consisting of electronic as well as mechanical parts.
4
Real-time Embedded Systems
Definition 4 (Embedded system)
An embedded system is a computer system designed for
specific control functions within a larger system, usually
consisting of electronic as well as mechanical parts.
Most (not all) real-time
systems are embedded
Most (not all) embedded
systems are real-time
4
(Few) Examples of Real-time Embedded Systems
Industrial
chemical plant control
automated assembly line (e.g. robotic assembly, inspection)
5
(Few) Examples of Real-time Embedded Systems
Industrial
chemical plant control
automated assembly line (e.g. robotic assembly, inspection)
Medical
pacemaker,
medical monitoring devices
5
(Few) Examples of Real-time Embedded Systems
Industrial
chemical plant control
automated assembly line (e.g. robotic assembly, inspection)
Medical
pacemaker,
medical monitoring devices
Transportation systems
computers in cars (ABS, MPFI, cruise control, airbag ...)
aircraft (FMS, fly-by-wire ...)
5
(Few) Examples of Real-time Embedded Systems
Industrial
chemical plant control
automated assembly line (e.g. robotic assembly, inspection)
Medical
pacemaker,
medical monitoring devices
Transportation systems
computers in cars (ABS, MPFI, cruise control, airbag ...)
aircraft (FMS, fly-by-wire ...)
Military applications
controllers in weapons, missiles, ...
radar and sonar tracking
5
(Few) Examples of Real-time Embedded Systems
Industrial
chemical plant control
automated assembly line (e.g. robotic assembly, inspection)
Medical
pacemaker,
medical monitoring devices
Transportation systems
computers in cars (ABS, MPFI, cruise control, airbag ...)
aircraft (FMS, fly-by-wire ...)
Military applications
controllers in weapons, missiles, ...
radar and sonar tracking
Multimedia – video telephony, multimedia center,
videoconferencing
...
5
(Non-)Real-time (non-)embedded systems
There are real time systems that are not embedded:
trading systems
ticket reservation
multimedia (on PC)
...
6
(Non-)Real-time (non-)embedded systems
There are real time systems that are not embedded:
trading systems
ticket reservation
multimedia (on PC)
...
There are embedded systems that are (possibly) not real-time
e.g. a weather station sends data once a day without any deadline –
not really real-time system
Caveat: Aren’t all systems real-time in a sense?
6
Characteristics of Real-Time Embedded Systems
Real-time systems often are
safety critical
Serious consequences may result if services are not
delivered on timely basis
Bugs in embedded real-time systems are often difficult to fix
... need to validate their correctness
7
Characteristics of Real-Time Embedded Systems
Real-time systems often are
safety critical
Serious consequences may result if services are not
delivered on timely basis
Bugs in embedded real-time systems are often difficult to fix
... need to validate their correctness
concurrent
Real-world devices operate in parallel – better to model this
parallelism by concurrent tasks in the program
... validation may be difficult, formal methods often needed
7
Characteristics of Real-Time Embedded Systems
Real-time systems often are
safety critical
Serious consequences may result if services are not
delivered on timely basis
Bugs in embedded real-time systems are often difficult to fix
... need to validate their correctness
concurrent
Real-world devices operate in parallel – better to model this
parallelism by concurrent tasks in the program
... validation may be difficult, formal methods often needed
reactive
Interact continuously with their environment (as opposed to
information processing systems)
... “traditional” validation methods do not apply
7
Validating Time Requirements and Predictability
Given real-time requirements and an implementation on
HW and SW, how to show that the requirements are met?
8
Validating Time Requirements and Predictability
Given real-time requirements and an implementation on
HW and SW, how to show that the requirements are met?
... testing might not suffice:
Maiden flight of space shuttle, 12 April 1981: 1/67 probability that a
transient overload occurs during initialization; and it actually did!
8
Validating Time Requirements and Predictability
Given real-time requirements and an implementation on
HW and SW, how to show that the requirements are met?
... testing might not suffice:
Maiden flight of space shuttle, 12 April 1981: 1/67 probability that a
transient overload occurs during initialization; and it actually did!
We need a formal model and validation ...
8
Validating Time Requirements and Predictability
Given real-time requirements and an implementation on
HW and SW, how to show that the requirements are met?
... testing might not suffice:
Maiden flight of space shuttle, 12 April 1981: 1/67 probability that a
transient overload occurs during initialization; and it actually did!
We need a formal model and validation ...
... we need predictable behavior!
It is difficult to obtain
caches, DMA, unmaskable interrupts
memory management
scheduling anomalies
difficult to compute worst-case execution time
...
8
Types of Timing Requirements
Time sharing systems: minimize average response time
The goal of scheduling in standard op. systems such as Linux and Windows
9
Types of Timing Requirements
Time sharing systems: minimize average response time
The goal of scheduling in standard op. systems such as Linux and Windows
Often it is not enough to minimize average response time!
(A man drowned crossing a stream with an average depth of 15cm.)
9
Types of Timing Requirements
Time sharing systems: minimize average response time
The goal of scheduling in standard op. systems such as Linux and Windows
Often it is not enough to minimize average response time!
(A man drowned crossing a stream with an average depth of 15cm.)
“hard” real-time tasks must be always finished before their deadline!
e.g. airbag in a car: whenever a collision is detected, the airbag must be
deployed within 10ms
9
Types of Timing Requirements
Time sharing systems: minimize average response time
The goal of scheduling in standard op. systems such as Linux and Windows
Often it is not enough to minimize average response time!
(A man drowned crossing a stream with an average depth of 15cm.)
“hard” real-time tasks must be always finished before their deadline!
e.g. airbag in a car: whenever a collision is detected, the airbag must be
deployed within 10ms
Not all tasks in a real-time system are critical, only the quality of
service is affected by missing a deadline
9
Types of Timing Requirements
Time sharing systems: minimize average response time
The goal of scheduling in standard op. systems such as Linux and Windows
Often it is not enough to minimize average response time!
(A man drowned crossing a stream with an average depth of 15cm.)
“hard” real-time tasks must be always finished before their deadline!
e.g. airbag in a car: whenever a collision is detected, the airbag must be
deployed within 10ms
Not all tasks in a real-time system are critical, only the quality of
service is affected by missing a deadline
Most “soft” real-time tasks should finish before their deadlines.
e.g. frame rate in a videoconf. should be kept above 15fps most of the time
9
Types of Timing Requirements
Time sharing systems: minimize average response time
The goal of scheduling in standard op. systems such as Linux and Windows
Often it is not enough to minimize average response time!
(A man drowned crossing a stream with an average depth of 15cm.)
“hard” real-time tasks must be always finished before their deadline!
e.g. airbag in a car: whenever a collision is detected, the airbag must be
deployed within 10ms
Not all tasks in a real-time system are critical, only the quality of
service is affected by missing a deadline
Most “soft” real-time tasks should finish before their deadlines.
e.g. frame rate in a videoconf. should be kept above 15fps most of the time
Many real-time systems combine “hard” and “soft” real-time tasks.
i.e. we optimize performance w.r.t. “soft” real-time tasks under the constraint
that “hard” real-time tasks are finished before their deadlines
9
Examples of Real-Time Systems
Digital process control
anti-lock braking system
Higher-level command and control
helicopter flight control
Real-time databases
Stock trading systems
10
Digital Process Control
Computer controls the flow in the pipe in real-time
11
Digital Process Control
The controller (computer) controls the plant using the actuator
(valve) based on sampled data from the sensor (flow meter)
y(t) – the measured state of the plant
r(t) – the desired state of the plant
Calculate control output u(t) as a function of y(t), r(t)
e.g. uk = uk−2 + α(rk − yk ) + β(rk−1 − yk−1) + γ(rk−2 − yk−2)
where α, β, γ are suitable constants
12
Digital Process Control
Pseudo-code for the controller:
set timer to interrupt periodically with period T
foreach timer interrupt do
analogue-to-digital conversion of y(t) to get yk
compute control output uk based on rk and yk
digital-to-analogue conversion of uk to get u(t)
end
13
Digital Process Control
Pseudo-code for the controller:
set timer to interrupt periodically with period T
foreach timer interrupt do
analogue-to-digital conversion of y(t) to get yk
compute control output uk based on rk and yk
digital-to-analogue conversion of uk to get u(t)
end
Effective control of the plant depends on:
The correct reference input and control law computation
The accuracy of the sensor measurements
Resolution of the sampled data (i.e. bits per sample)
Frequency of interrupts (i.e. 1/T)
13
Digital Process Control
Pseudo-code for the controller:
set timer to interrupt periodically with period T
foreach timer interrupt do
analogue-to-digital conversion of y(t) to get yk
compute control output uk based on rk and yk
digital-to-analogue conversion of uk to get u(t)
end
Effective control of the plant depends on:
The correct reference input and control law computation
The accuracy of the sensor measurements
Resolution of the sampled data (i.e. bits per sample)
Frequency of interrupts (i.e. 1/T)
T is the sampling period
Small T better approximates the analogue behavior
Large T means less processor-time demand
... but may result in unstable control
13
Example
r(t) = 1 for t ≥ 0
14
Example
r(t) = 1 for t ≥ 0 14
Example
r(t) = 1 for t ≥ 0
14
Anti-Lock Braking System
The controller monitors the speed sensors in wheels
Right before a wheel locks up, it experiences a rapid deceleration
15
Anti-Lock Braking System
The controller monitors the speed sensors in wheels
Right before a wheel locks up, it experiences a rapid deceleration
If a rapid deceleration of a wheel is observed, the controller
alternately
reduces pressure on the corresponding brake until
acceleration is observed
then applies brake until deceleration is observed
15
Multi-Rate DPC – Helicopter Flight Control
There are also three velocity components
Two control loops: pilot’s control (30Hz) and stabilization (90Hz)
16
Multi-Rate DPC – Helicopter Flight Control
Do the following in each 1/180-second cycle:
Validate sensor data; in the presence of failures, reconfigure the system
17
Multi-Rate DPC – Helicopter Flight Control
Do the following in each 1/180-second cycle:
Validate sensor data; in the presence of failures, reconfigure the system
Do the following 30-Hz avionics tasks, each one every six cycles:
keyboard input and mode selection
data normalization and coordinate transformation
tracking reference update
17
Multi-Rate DPC – Helicopter Flight Control
Do the following in each 1/180-second cycle:
Validate sensor data; in the presence of failures, reconfigure the system
Do the following 30-Hz avionics tasks, each one every six cycles:
keyboard input and mode selection
data normalization and coordinate transformation
tracking reference update
Do the following 30-Hz avionics tasks, each one every six cycles:
control laws of the outer pitch-control loop
control laws of the outer roll-control loop
control laws of the outer yaw- and collective-control loop
17
Multi-Rate DPC – Helicopter Flight Control
Do the following in each 1/180-second cycle:
Validate sensor data; in the presence of failures, reconfigure the system
Do the following 30-Hz avionics tasks, each one every six cycles:
keyboard input and mode selection
data normalization and coordinate transformation
tracking reference update
Do the following 30-Hz avionics tasks, each one every six cycles:
control laws of the outer pitch-control loop
control laws of the outer roll-control loop
control laws of the outer yaw- and collective-control loop
Do each of the following 90-Hz computations once every two cycles,
using outputs produced by 30-Hz computations and avionics tasks:
control laws of the inner pitch-control loop
control laws of the inner roll- and collective-control loop
Compute the control laws of the inner yaw-control loop, using outputs
produced by 90-Hz control-law computations as inputs
17
Multi-Rate DPC – Helicopter Flight Control
Do the following in each 1/180-second cycle:
Validate sensor data; in the presence of failures, reconfigure the system
Do the following 30-Hz avionics tasks, each one every six cycles:
keyboard input and mode selection
data normalization and coordinate transformation
tracking reference update
Do the following 30-Hz avionics tasks, each one every six cycles:
control laws of the outer pitch-control loop
control laws of the outer roll-control loop
control laws of the outer yaw- and collective-control loop
Do each of the following 90-Hz computations once every two cycles,
using outputs produced by 30-Hz computations and avionics tasks:
control laws of the inner pitch-control loop
control laws of the inner roll- and collective-control loop
Compute the control laws of the inner yaw-control loop, using outputs
produced by 90-Hz control-law computations as inputs
Output commands
Carry out built-in-test
Wait until the beginning of the next cycle
17
Higher-Level Command and Control
Controllers organized into a hierarchy
At the lowest level we place the digital control systems that
operate on the physical environment
Higher level controllers monitor the behavior of lower levels
Time-scale and complexity of decision making increases as one
goes up the hierarchy (from control to planning)
18
Real-Time Database System
Databases that contain perishable data, i.e. relevance of
data deteriorates with time
Air traffic control, stock price quotation systems, tracking systems, etc.
19
Real-Time Database System
Databases that contain perishable data, i.e. relevance of
data deteriorates with time
Air traffic control, stock price quotation systems, tracking systems, etc.
The temporal quality of data is quantified by age of an
image object, i.e. the length of time since last update
19
Real-Time Database System
Databases that contain perishable data, i.e. relevance of
data deteriorates with time
Air traffic control, stock price quotation systems, tracking systems, etc.
The temporal quality of data is quantified by age of an
image object, i.e. the length of time since last update
temporal consistency
absolute = max. age is bounded by a fixed threshold
relative = max. difference in ages is bounded by a threshold
e.g. planning system correlating traffic density and flow of vehicles
Users of database compete for access – various models
for trading consistency with time demands exist.
19
Stock-Trading System
A system for selling/buying stock at public prices
20
Stock-Trading System
A system for selling/buying stock at public prices
Prices are volatile in their movement
20
Stock-Trading System
A system for selling/buying stock at public prices
Prices are volatile in their movement
Stop orders:
set upper limit on prices for buying – buy for the best
available price once the limit is reached
e.g. stock currently trading at $30 should be bought when the
price rises above $35
20
Stock-Trading System
A system for selling/buying stock at public prices
Prices are volatile in their movement
Stop orders:
set upper limit on prices for buying – buy for the best
available price once the limit is reached
e.g. stock currently trading at $30 should be bought when the
price rises above $35
set lower limit on prices for selling – sell for the best
available price once the limit is reached
e.g. stock currently trading at $30 should be sold when the price
sinks below $25
20
Stock-Trading System
A system for selling/buying stock at public prices
Prices are volatile in their movement
Stop orders:
set upper limit on prices for buying – buy for the best
available price once the limit is reached
e.g. stock currently trading at $30 should be bought when the
price rises above $35
set lower limit on prices for selling – sell for the best
available price once the limit is reached
e.g. stock currently trading at $30 should be sold when the price
sinks below $25
Depending on the delay, the available price may be
different from the limit
successful stop orders depend on the timely delivery of stock trade data
and the ability to trade on the changing prices in a timely manner
20
Structure of Real-Time (Embedded) Applications
21
Types of Real-Time Systems
Purely cyclic
every task executes periodically; I/O operations are polled;
demands in resources do not vary
e.g. digital controllers
22
Types of Real-Time Systems
Purely cyclic
every task executes periodically; I/O operations are polled;
demands in resources do not vary
e.g. digital controllers
Mostly cyclic
most tasks execute periodically; system also responds to
external events (fault recovery and external commands)
asynchronously
e.g. avionics
22
Types of Real-Time Systems
Purely cyclic
every task executes periodically; I/O operations are polled;
demands in resources do not vary
e.g. digital controllers
Mostly cyclic
most tasks execute periodically; system also responds to
external events (fault recovery and external commands)
asynchronously
e.g. avionics
Asynchronous and somewhat predictable
durations between consecutive executions of a task as well
as demands in resources may vary considerably. These
variations have either bounded range, or known statistics.
e.g. radar signal processing, tracking
22
Types of Real-Time Systems
The type of application affects how we schedule tasks and
prove correctness
It is easier to reason about applications that are more
cyclic, synchronous and predictable
Many real-time systems are designed in this manner
Safe, conservative, design approach, if it works
23
Real-Time Systems Failures
AT&T long distance calls
Therac-25 medical accelerator disaster
Patriot missile mistiming
24
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
sent “do not disturb” to neighbors
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
sent “do not disturb” to neighbors
after the reset, the switch began to distribute calls (quickly)
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
sent “do not disturb” to neighbors
after the reset, the switch began to distribute calls (quickly)
then another switch received one of these calls from New York
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
sent “do not disturb” to neighbors
after the reset, the switch began to distribute calls (quickly)
then another switch received one of these calls from New York
began to update its records that New York was back on line
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
sent “do not disturb” to neighbors
after the reset, the switch began to distribute calls (quickly)
then another switch received one of these calls from New York
began to update its records that New York was back on line
a second call from New York arrived less than 10 milliseconds after the
first, i.e. while the first hadn’t yet been handled;
this together with a SW bug caused maintenance reset
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
sent “do not disturb” to neighbors
after the reset, the switch began to distribute calls (quickly)
then another switch received one of these calls from New York
began to update its records that New York was back on line
a second call from New York arrived less than 10 milliseconds after the
first, i.e. while the first hadn’t yet been handled;
this together with a SW bug caused maintenance reset
the error was propagated further ....
25
AT&T Long Distance Calls
114 computer-operated electronic
switches scattered across USA
Handling up to 700,000 calls an hour
The problem:
the switch in New York City neared its load limit
entered a four-second maintenance reset
sent “do not disturb” to neighbors
after the reset, the switch began to distribute calls (quickly)
then another switch received one of these calls from New York
began to update its records that New York was back on line
a second call from New York arrived less than 10 milliseconds after the
first, i.e. while the first hadn’t yet been handled;
this together with a SW bug caused maintenance reset
the error was propagated further ....
The reason for failure: The system was unable to react to closely
timed messages 25
Therac-25 medical accelerator disaster
Therac-25 = a machine for radiotheratpy
between 1985 and 1987 (at least) six accidents involving
enormous radiation overdoses to patients
Half of these patients died due to the overdoses
26
Therac-25 – the modes
1. electron mode
electron beam (low current)
various levels of energy (5 to 25-MeV)
scanning magnets used to spread the beam to a safe
concentration
27
Therac-25 – the modes
1. electron mode
electron beam (low current)
various levels of energy (5 to 25-MeV)
scanning magnets used to spread the beam to a safe
concentration
2. photon mode
only one level of energy (25-MeV), much larger
electron-beam current
electron beam strikes a metal foil to produce X-rays
(photons)
the X-ray beam is "flattened" by a device below the foil
27
Therac-25 – the modes
1. electron mode
electron beam (low current)
various levels of energy (5 to 25-MeV)
scanning magnets used to spread the beam to a safe
concentration
2. photon mode
only one level of energy (25-MeV), much larger
electron-beam current
electron beam strikes a metal foil to produce X-rays
(photons)
the X-ray beam is "flattened" by a device below the foil
3. light mode – just light beam used to illuminate the field on
the surface of the patient’s body that will be treated
27
Therac-25 – the modes
1. electron mode
electron beam (low current)
various levels of energy (5 to 25-MeV)
scanning magnets used to spread the beam to a safe
concentration
2. photon mode
only one level of energy (25-MeV), much larger
electron-beam current
electron beam strikes a metal foil to produce X-rays
(photons)
the X-ray beam is "flattened" by a device below the foil
3. light mode – just light beam used to illuminate the field on
the surface of the patient’s body that will be treated
All devices placed on a turntable, supposed to be rotated to the
correct position before the beam is started up
27
Therac-25 – turntable
28
The Software
The software responsible for
Operator
Monitoring input and editing changes from an operator
Updating the screen to show current status of machine
Printing in response to an operator commands
29
The Software
The software responsible for
Operator
Monitoring input and editing changes from an operator
Updating the screen to show current status of machine
Printing in response to an operator commands
Machine
monitoring the machine status
placement of turntable
strength and shape of beam
operation of bending and scanning magnets
setting the machine up for the specified treatment
turning the beam on
turning the beam off (after treatment, on operator
command, or if a malfunction is detected)
29
The Software
The software responsible for
Operator
Monitoring input and editing changes from an operator
Updating the screen to show current status of machine
Printing in response to an operator commands
Machine
monitoring the machine status
placement of turntable
strength and shape of beam
operation of bending and scanning magnets
setting the machine up for the specified treatment
turning the beam on
turning the beam off (after treatment, on operator
command, or if a malfunction is detected)
Software running several safety critical tasks in parallel!
Insufficient hardware protection (as opposed to previous models)!!
29
Therac-25 – software
The Therac-25 runs on a real-time operating system
30
Therac-25 – software
The Therac-25 runs on a real-time operating system
Four major components of software: stored data, a scheduler, a
set of tasks, and interrupt services (e.g. the computer clock and
handling of computer-hardware-generated errors)
30
Therac-25 – software
The Therac-25 runs on a real-time operating system
Four major components of software: stored data, a scheduler, a
set of tasks, and interrupt services (e.g. the computer clock and
handling of computer-hardware-generated errors)
The software segregated the tasks above into
critical tasks: e.g. setup and operation of the beam
non-critical tasks: e.g. monitoring the keyboard
30
Therac-25 – software
The Therac-25 runs on a real-time operating system
Four major components of software: stored data, a scheduler, a
set of tasks, and interrupt services (e.g. the computer clock and
handling of computer-hardware-generated errors)
The software segregated the tasks above into
critical tasks: e.g. setup and operation of the beam
non-critical tasks: e.g. monitoring the keyboard
The scheduler directs all non-interrupt events and orders
simultaneous events
30
Therac-25 – software
The Therac-25 runs on a real-time operating system
Four major components of software: stored data, a scheduler, a
set of tasks, and interrupt services (e.g. the computer clock and
handling of computer-hardware-generated errors)
The software segregated the tasks above into
critical tasks: e.g. setup and operation of the beam
non-critical tasks: e.g. monitoring the keyboard
The scheduler directs all non-interrupt events and orders
simultaneous events
Every 0.1 seconds tasks are initiated and critical tasks are
executed first, with non-critical tasks taking up any remaining
time
30
Therac-25 – software
The Therac-25 runs on a real-time operating system
Four major components of software: stored data, a scheduler, a
set of tasks, and interrupt services (e.g. the computer clock and
handling of computer-hardware-generated errors)
The software segregated the tasks above into
critical tasks: e.g. setup and operation of the beam
non-critical tasks: e.g. monitoring the keyboard
The scheduler directs all non-interrupt events and orders
simultaneous events
Every 0.1 seconds tasks are initiated and critical tasks are
executed first, with non-critical tasks taking up any remaining
time
Communication between tasks based on shared variables
(without proper atomic test-and-set instructions)
30
What happened?
There were several accidents due to various bugs in software
31
What happened?
There were several accidents due to various bugs in software
One of them proceeded as follows (much simplified):
the operator entered parameters for X-rays treatment
31
What happened?
There were several accidents due to various bugs in software
One of them proceeded as follows (much simplified):
the operator entered parameters for X-rays treatment
the machine started to set up for the treatment
31
What happened?
There were several accidents due to various bugs in software
One of them proceeded as follows (much simplified):
the operator entered parameters for X-rays treatment
the machine started to set up for the treatment
the operator changed the mode from X-rays to electron (within
the interval from 1s to 8s from the end of the original editing)
31
What happened?
There were several accidents due to various bugs in software
One of them proceeded as follows (much simplified):
the operator entered parameters for X-rays treatment
the machine started to set up for the treatment
the operator changed the mode from X-rays to electron (within
the interval from 1s to 8s from the end of the original editing)
the patient received X-ray “treatment” with turntable in the
electron position (i.e. unshielded)
31
What happened?
There were several accidents due to various bugs in software
One of them proceeded as follows (much simplified):
the operator entered parameters for X-rays treatment
the machine started to set up for the treatment
the operator changed the mode from X-rays to electron (within
the interval from 1s to 8s from the end of the original editing)
the patient received X-ray “treatment” with turntable in the
electron position (i.e. unshielded)
The cause:
The turntable and treatment parameters were set by different
concurrent procedures Hand and Datent, respectively.
31
What happened?
There were several accidents due to various bugs in software
One of them proceeded as follows (much simplified):
the operator entered parameters for X-rays treatment
the machine started to set up for the treatment
the operator changed the mode from X-rays to electron (within
the interval from 1s to 8s from the end of the original editing)
the patient received X-ray “treatment” with turntable in the
electron position (i.e. unshielded)
The cause:
The turntable and treatment parameters were set by different
concurrent procedures Hand and Datent, respectively.
If the change in parameters came in the “right” time, only Hand
reacted to the change.
31
Patriot missile mistiming
vs
32
Patriot missile mistiming
Patriot – Air defense missile system
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
The problem was caused by incorrect measurement of time
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
The problem was caused by incorrect measurement of time
Simplified principle of function:
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
The problem was caused by incorrect measurement of time
Simplified principle of function:
Patriot’s radar detects an airborne object
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
The problem was caused by incorrect measurement of time
Simplified principle of function:
Patriot’s radar detects an airborne object
the object is identified as a scud missile (according to speed,
size, etc.)
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
The problem was caused by incorrect measurement of time
Simplified principle of function:
Patriot’s radar detects an airborne object
the object is identified as a scud missile (according to speed,
size, etc.)
the range gate computes an area in the air space where the
system should next look for it
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
The problem was caused by incorrect measurement of time
Simplified principle of function:
Patriot’s radar detects an airborne object
the object is identified as a scud missile (according to speed,
size, etc.)
the range gate computes an area in the air space where the
system should next look for it
finding the object in the calculated area confirms that it is a scud
33
Patriot missile mistiming
Patriot – Air defense missile system
Failed to intercept a scud missile on February 25, 1991 at
Dhahran, Saudi Arabia
(missile hit US army barracks, 28 persons killed)
The problem was caused by incorrect measurement of time
Simplified principle of function:
Patriot’s radar detects an airborne object
the object is identified as a scud missile (according to speed,
size, etc.)
the range gate computes an area in the air space where the
system should next look for it
finding the object in the calculated area confirms that it is a scud
then the scud is intercepted
33
Patriot Missile Mistiming
34
Patriot Missile Mistiming
Prediction of the new area:
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
the current time kept by incrementing whole number
counter counting tenths of seconds
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
the current time kept by incrementing whole number
counter counting tenths of seconds
computation in 24bit fixed floating point numbers
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
the current time kept by incrementing whole number
counter counting tenths of seconds
computation in 24bit fixed floating point numbers
The time converted to 24bit real number and multiplied with 1/10
represented in 24bit (i.e. the real value of 1/10 was 0.099999905)
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
the current time kept by incrementing whole number
counter counting tenths of seconds
computation in 24bit fixed floating point numbers
The time converted to 24bit real number and multiplied with 1/10
represented in 24bit (i.e. the real value of 1/10 was 0.099999905)
the system was already running for 100 hours, i.e. the counter
value was 360000, i.e. 360000 · 0.099999905 = 35999.6568
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
the current time kept by incrementing whole number
counter counting tenths of seconds
computation in 24bit fixed floating point numbers
The time converted to 24bit real number and multiplied with 1/10
represented in 24bit (i.e. the real value of 1/10 was 0.099999905)
the system was already running for 100 hours, i.e. the counter
value was 360000, i.e. 360000 · 0.099999905 = 35999.6568
the error was 0.3432 seconds, which means 687 m off MACH 5
scud missile
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
the current time kept by incrementing whole number
counter counting tenths of seconds
computation in 24bit fixed floating point numbers
The time converted to 24bit real number and multiplied with 1/10
represented in 24bit (i.e. the real value of 1/10 was 0.099999905)
the system was already running for 100 hours, i.e. the counter
value was 360000, i.e. 360000 · 0.099999905 = 35999.6568
the error was 0.3432 seconds, which means 687 m off MACH 5
scud missile
the problem was not only in wrong conversion but in the fact that
at some points correct conversion was used (after incomplete
bug fix), so the errors did not cancel out
35
Patriot Missile Mistiming
Prediction of the new area:
a function of velocity and time of the last radar detection
velocity represented as a real number
the current time kept by incrementing whole number
counter counting tenths of seconds
computation in 24bit fixed floating point numbers
The time converted to 24bit real number and multiplied with 1/10
represented in 24bit (i.e. the real value of 1/10 was 0.099999905)
the system was already running for 100 hours, i.e. the counter
value was 360000, i.e. 360000 · 0.099999905 = 35999.6568
the error was 0.3432 seconds, which means 687 m off MACH 5
scud missile
the problem was not only in wrong conversion but in the fact that
at some points correct conversion was used (after incomplete
bug fix), so the errors did not cancel out
As a result, the tracking gate looked into wrong area
35
Patriot Missile Mistiming
36
(Rough) Course Outline
Real-time scheduling
Time and priority driven
Resource control
Multi-processor (a bit)
37
(Rough) Course Outline
Real-time scheduling
Time and priority driven
Resource control
Multi-processor (a bit)
A little bit on programming real-time systems
Real-time operating systems
37
Outline – Scheduling
The Scheduling problem:
Input:
available processors, resources
set of tasks/jobs
with their requirements, deadlines, etc.
38
Outline – Scheduling
The Scheduling problem:
Input:
available processors, resources
set of tasks/jobs
with their requirements, deadlines, etc.
Question: How to assign processors and resources to
tasks/jobs so that all requirements are met?
38
Outline – Scheduling
The Scheduling problem:
Input:
available processors, resources
set of tasks/jobs
with their requirements, deadlines, etc.
Question: How to assign processors and resources to
tasks/jobs so that all requirements are met?
Example:
1 processor, one critical section shared by job 1 and job 3
job 1: release time 1, computation time 4, deadline 8
job 2: release time 1, computation time 2, deadline 5
job 3: release time 0, computation time 3, deadline 4
...
38
Outline – Scheduling
We consider a formal model of systems with parallel jobs
that possibly contend for shared resources
consider periodic as well as aperiodic jobs
Consider various algorithms that schedule jobs to meet
their timing constraints
offline and online algorithms, RM, EDF, etc.
39
Outline – Programming
Basic information about RTOS and RT programming languages
RTOS – overview
real-time in non-real-time operating systems
implementation of theoretical concepts in freeRTOS
RT in programming languages – short overview
40
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]
41
Real-Time Scheduling – Formal Model
Introduce an abstract model of real-time systems
abstracts away unessential details
sets up consistent terminology
42
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
42
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.
43
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
43
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.
43
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.
43
Life Cycle of a Job
READY RUN
WAITING
COMPL.
scheduling
preemption
wait for a busy
resource
signal free
resource
release
completed
44
Jobs – Parameters
We consider finite, or countably infinte number of jobs J1, J2, . . .
Each job has several parameters.
45
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
45
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
46
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
46
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
46
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
47
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
47
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
47
Job Parameters – Deadlines
Absolute deadline di – the instant in time by which a job must
be completed
48
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
48
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
48
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. 48
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.
49
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
49
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
49
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 5
A timing constraint is hard if the user requires formal validation
that the job meets its timing constraint.
49
Laxity Type – Soft Real-Time
A soft real-time constraint specifies that a job could
occasionally miss its deadline
Examples: stock trading, multimedia, etc.
50
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
50
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
50
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 6
A timing constraint is soft if either validation is not required, or
only a demonstration that a statistical constraint is met suffices.
50
Jobs – Preemptability
Jobs may be interrupted by higher priority jobs
51
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)
51
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
51
Jobs – Precedence Constraints
Jobs may be constrained to execute in a particular order
52
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
52
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
52
Tasks – Modeling Reactive Systems
Reactive systems – run for unlimited amount of time
53
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)
53
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.
53
Processors
A processor, P, is an active component on which jobs are scheduled
54
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.
54
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
54
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).
54
Resources
A resource, R, is a passive entity upon which jobs may depend
55
Resources
A resource, R, is a passive entity upon which jobs may depend
In general, we consider n resources R1, . . . , Rn of distinct types
55
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)
55
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)
55
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.)
56
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
57
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
57
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.
57
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
58
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
58
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
Definition 7
A scheduling algorithm is optimal if it always produces
a feasible schedule whenever such a schedule exists.
58
Real-Time Scheduling
Individual Jobs
59
Scheduling of Individual Jobs
We start with scheduling of finite sets of jobs {J1, . . . , Jm} for
execution on single processor systems.
60
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?
60
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
60
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?
61
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?
Note: Preemption does not help in synchronized case.
61
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?
Note: Preemption does not help in synchronized case.
Theorem 8
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).
61
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?
Note: Preemption does not help in synchronized case.
Theorem 8
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).
Proof.
Let σ be a schedule. Inversion is a pair (Ja, Jb) such that Ja
precedes Jb in σ but db < da.
Note that σ is EDD iff it does not contain any inversion.
61
Proof cont.
Assume k > 0 inversions in σ.
Let (Ja, Jb ) be an inversion such that Ja is scheduled right before Jb .
There is always at least one such inversion (homework).
Let ta < tb be the time instants when Ja, Jb start to be executed in σ.
Recall: Ca, Cb are completion times of Ja, Jb , and ea, eb are execution times.
Note that Ca ≤ da and that Cb ≤ db < da.
62
Proof cont.
Assume k > 0 inversions in σ.
Let (Ja, Jb ) be an inversion such that Ja is scheduled right before Jb .
There is always at least one such inversion (homework).
Let ta < tb be the time instants when Ja, Jb start to be executed in σ.
Recall: Ca, Cb are completion times of Ja, Jb , and ea, eb are execution times.
Note that Ca ≤ da and that Cb ≤ db < da.
Define a new schedule σ in which:
All jobs except Ja, Jb are scheduled as in σ,
Jb starts at ta,
Ja starts at ta + eb .
Observe that σ is still feasible:
Jb is completed at ta + eb < ta + eb + ea = tb + eb = Cb ≤ db
Ja is completed at ta + eb + ea = Cb ≤ db < da
Note that σ has k − 1 inversions. By repeating the above procedure k
times, we obtain an EDD schedule.
62
No resources, Independent, Synchronized
Is there any simple schedulability test?
{J1, . . . , Jn} where d1 ≤ · · · ≤ dn is schedulable iff
∀i ∈ {1, . . . , n} : i
k=1 ek ≤ di
63
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
64
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
Preemption makes a difference.
64
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
65
No Resources, Independent (No Synchro)
Theorem 9
If there are no resource contentions, jobs are independent and
preemption is allowed, the EDF algorithm finds a feasible
schedule (if it exists).
Proof.
We show that any feasible schedule σ can be transformed in finitely
many steps to EDF schedule which is feasible.
66
No Resources, Independent (No Synchro)
Theorem 9
If there are no resource contentions, jobs are independent and
preemption is allowed, the EDF algorithm finds a feasible
schedule (if it exists).
Proof.
We show that any feasible schedule σ can be transformed in finitely
many steps to EDF schedule which is feasible.
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.)
66
No Resources, Independent (No Synchro)
Proof cont.
We say that σ violates EDF at k if there are two jobs Ja and Jb that
satisfy:
Ja and Jb are ready for execution at k
Ja is executed in [k, k + 1)
db < da
67
No Resources, Independent (No Synchro)
Proof cont.
We say that σ violates EDF at k if there are two jobs Ja and Jb that
satisfy:
Ja and Jb are ready for execution at k
Ja is executed in [k, k + 1)
db < da
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 Jb has the minimum deadline among all jobs
ready for execution at k.
There is k < < db such that Jb is executed in [ , + 1).
67
No Resources, Independent (No Synchro)
Proof cont.
We say that σ violates EDF at k if there are two jobs Ja and Jb that
satisfy:
Ja and Jb are ready for execution at k
Ja is executed in [k, k + 1)
db < da
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 Jb has the minimum deadline among all jobs
ready for execution at k.
There is k < < db such that Jb is executed in [ , + 1).
Let us define a new schedule σ which is the same as σ except:
executes Jb in [k, k + 1)
executes Ja in [ , + 1)
Then σ is feasible and does not violate EDF at any k ≤ k.
Finitely many steps transform any feasible schedule to EDF.
67
No resources, Independent (No Synchro)
The non-preemptive case is NP-hard.
68
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.)
68
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
68
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
68
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.)
68
No Resources, Dependent (No Synchro)
Example:
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
Does EDF work?
69
No resources, Dependent (No Synchro)
Theorem 10
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.
70
No resources, Dependent (No Synchro)
Theorem 10
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.
70
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.
71
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.
Example:
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
71
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.
Example:
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
Do you need the precedence constraints? 71
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.
72
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.
72
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 11
{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.
72
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 11.
⇒: It is easy to show that in no feasible schedule on {J1, . . . , Jm} any
job Jk can be executed before r∗
k
and completed after d∗
k
(otherwise,
precedence constraints would be violated).
73
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 11.
⇒: It is easy to show that in no feasible schedule on {J1, . . . , Jm} any
job Jk can be executed before r∗
k
and completed after 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.
73
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 11.
⇒: It is easy to show that in no feasible schedule on {J1, . . . , Jm} any
job Jk can be executed before r∗
k
and completed after 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.
73
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 11.
⇒: It is easy to show that in no feasible schedule on {J1, . . . , Jm} any
job Jk can be executed before r∗
k
and completed after 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}.
73
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.
74
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]
75
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
76
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
77
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
78
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.
78
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
78
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
78
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
79
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)
79
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
80
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, ...)
80
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, ...)
80
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, ...)
80
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
81
Aperiodic and Sporadic Tasks
Many real-time systems are required to respond to
external events
82
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
82
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)
82
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 82
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
83
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
83
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
84
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
84
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.)
85
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
85
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
85
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
86
Real-Time Scheduling
Scheduling of Reactive Systems
Clock-Driven Scheduling
87
Current Assumptions
Fixed number, n, of periodic tasks T1, . . . , Tn
88
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
88
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 tasks
assume that the system maintains a single queue for jobs
of aperiodic tasks
Whenever the processor is available for aperiodic tasks, the
job at the head of this queue is executed
We treat sporadic tasks later
Abuse of notation: Periodic, aperiodic, sporadic jobs are jobs
of periodic, aperiodic, sporadic tasks, respectively.
88
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
89
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)
89
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
90
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)
91
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
91
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
91
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 )
91
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 · · ·
92
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
93
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
93
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.
93
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
94
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
94
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
94
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)
95
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
95
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.
95
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 12
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:
96
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)
97
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
97
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
97
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.
98
Scheduling Aperiodic Jobs
So far, aperiodic jobs scheduled in the background after all jobs
with hard deadlines
This may unnecessarily delay aperiodic jobs
99
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.
99
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
99
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
100
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
101
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
101
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
101
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
102
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
102
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
102
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)
102
Handling Overruns
Overruns may happen due to failures
e.g. unexpectedly large data over which the system operates, hardware
failures, etc.
103
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
103
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
104
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
104
Real-Time Scheduling
Scheduling of Reactive Systems
Priority-Driven Scheduling
105
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
106
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
106
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
107
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.
107
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 13
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
108
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
109
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.
Proof.
Consider e.g. T1 = (3, 1, 1) and T2 = (2, 1).
109
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
110
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
We focus on EDF here.
110
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 :-)
111
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.)
112
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?
112
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
112
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
113
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
113
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.
113
Utilization – Example
T1 = (2, 1) then u1 = 1
2
114
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)
114
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
114
Real-Time Scheduling
Priority-Driven Scheduling
Dynamic-Priority
115
Optimality of EDF
Theorem 14
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
116
Proof of 1.⇒2.
Assume that UT
= N
i=1
ei
pi
> 1.
117
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")
117
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.
117
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.
117
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.
117
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.
117
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.)
118
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.)
118
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.)
118
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.
By EDF, if a job preempts Ji,1, then its deadline must be in [0, pi].
During [0, pi], the processor is never idle and executes only jobs
of G.
The processor is not idle because Ji,1 is ready for computation
throughout [0, pi]. Jobs that do not belong to G are not executed as Ji,1
is not completed in [0, pi] and only jobs of G can preempt Ji,1.
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 be completed by pi.
Let us compute EG.
119
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
120
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.
120
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.
121
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).
121
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.
121
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.
121
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]).
121
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.
121
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 ).
121
Proof of 2.⇒3. – Complete (cont.)
It follows that
no job of (T T ) is executed in [t−, t],
(by definition of t−)
122
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−)
122
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 in [r−, 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 .
122
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 in [r−, 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 .
122
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 in [r−, 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].
122
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 in [r−, 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−.
122
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 in [r−, 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).
122
Proof of 2.⇒3. – Complete (cont.)
Now EG > t − t− because otherwise Ji,k would complete in [t−, t].
How to compute EG?
123
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].
123
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.)
123
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
123
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.
123
Density and EDF
What about tasks with Di < pi ?
124
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
124
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 15
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.)
124
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.
125
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
125
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
125
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
126
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)
126
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
126
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 ....
126
Real-Time Scheduling
Priority-Driven Scheduling
Fixed-Priority
127
Fixed-Priority Algorithms
Recall that we consider a set of n tasks T = {T1, . . . , Tn}
128
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.
128
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.
128
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.
128
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
129
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.)
129
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?
129
Maximum Response Time
Which job of a task Ti has the maximum response time?
130
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.
130
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.
130
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!
130
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.
130
Optimality of RM for Simply Periodic Tasks
Definition 16
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 17
The helicopter control system from the first lecture.
131
Optimality of RM for Simply Periodic Tasks
Definition 16
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 17
The helicopter control system from the first lecture.
Theorem 18
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 18 is true in general, no "in phase" assumption is needed.
131
Proof of Theorem 18
By Theorem 14, every schedulable set T satisfies UT
≤ 1.
132
Proof of Theorem 18
By Theorem 14, every schedulable set T satisfies UT
≤ 1.
We prove that if T is not schedulable according to RM, then UT
> 1.
132
Proof of Theorem 18
By Theorem 14, 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.
132
Proof of Theorem 18
By Theorem 14, 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 +
i−1
=1
pi
p
e =
i
=1
pi
p
e = pi
i
=1
u ≤ pi
n
=1
u = piUT
132
Proof of Theorem 18
By Theorem 14, 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 +
i−1
=1
pi
p
e =
i
=1
pi
p
e = pi
i
=1
u ≤ pi
n
=1
u = piUT
Now E > pi because otherwise Ji,1 meets its deadline.
132
Proof of Theorem 18
By Theorem 14, 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 +
i−1
=1
pi
p
e =
i
=1
pi
p
e = pi
i
=1
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.
132
Optimality of DM (RM) among Fixed-Priority Algs.
Theorem 19
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.
133
Optimality of DM (RM) among Fixed-Priority Algs.
Theorem 19
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.
133
Optimality of DM (RM) among Fixed-Priority Algs.
Theorem 19
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.
133
Optimality of DM (RM) among Fixed-Priority Algs.
Theorem 19
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.
133
Optimality of DM (RM) among Fixed-Priority Algs.
Theorem 19
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.
133
Optimality of DM (RM) among Fixed-Priority Algs.
Theorem 19
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.
133
Fixed-Priority Algorithms: Schedulability
We consider two schedulability tests:
Schedulable utilization URM of the RM algorithm.
Time-demand analysis based on response times.
134
Schedulable Utilization for RM
Theorem 20
Let us fix n ∈ N and consider only independent, preemptable
periodic tasks with Di = pi.
135
Schedulable Utilization for RM
Theorem 20
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.
135
Schedulable Utilization for RM
Theorem 20
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 20 holds in general, no "in phase" assumption is needed.
135
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)
136
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.
136
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)
137
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.
137
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.
137
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
.
137
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.
137
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)}.
137
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.
137
Proof – Special Case (Cont.)
Consider two cases depending on e1:
138
Proof – Special Case (Cont.)
Consider two cases depending on e1:
1. e1 < p2 − p1 :
138
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.
138
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
138
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
138
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
138
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
138
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
138
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.
138
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 :
138
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.
138
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
138
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
138
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
138
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
138
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
138
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.
138
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.)
138
Proof – Special Case (Cont.)
Substitute e1 = p2 − p1 into the expression for Up1,p2
e1
:
139
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

139
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
139
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
)
139
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
139
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
139
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.
139
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)
140
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.
140
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
140
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.
140
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).
140
Proof Idea of Theorem 20
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
141
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.
142
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.
142
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.
142
Time-Demand Analysis
Consider one task Ti at a time, starting with highest priority and
working to lowest priority.
143
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.
143
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).
143
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.
143
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.
143
Time-Demand Analysis – Example
Example: T1 = (3, 1), T2 = (5, 1.5), T3 = (7, 1.25), T4 = (9, 0.5)
This set of tasks is schedulable by RM even though
U{T1,...,T4}
= 0.85 > 0.757 = URM(4) 144
Time-Demand Analysis
The time-demand function wi(t) is a staircase function
145
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
145
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
145
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
145
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
145
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
145
Time-Demand Analysis – Comments
Time-demand analysis schedulability test is more complex than
the schedulable utilization test but more general:
146
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
146
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.
146
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.
146
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.
146
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.
146
Critical Instant – Formally
Definition 21
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.
147
Critical Instant – Formally
Definition 21
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 22
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.
147
Critical Instant – Formally
Definition 21
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 22
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!
147
Critical Instant and Schedulability Tests
We use critical instants to get upper bounds on schedulability as
follows:
148
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 22, 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 .
148
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 22, 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.
148
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 22, 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.
148
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 22, 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.
148
Dynamic vs Fixed Priority
EDF
pros:
optimal
very simple and complete test for schedulability
149
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
149
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)
149
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
149
Real-Time Scheduling
Priority-Driven Scheduling
Aperiodic Tasks
150
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
151
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
151
Scheduling Aperiodic Jobs
Consider:
A set T = {T1, . . . , Tn} of periodic tasks
An aperiodic task A
152
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
152
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
152
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
152
Background Scheduling of Aperiodic Jobs
Aperiodic jobs are scheduled and executed only at times
when there are no periodic jobs ready for execution
153
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
153
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
153
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)
153
Polled Execution of Aperiodic Jobs
We may use a polling server
154
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
154
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
154
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
154
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
154
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
154
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
154
Polled Execution of Aperiodic Jobs
Example: T1 = (3, 1), T2 = (10, 4), poller = (2.5, 0.5)
155
Polled Execution of Aperiodic Jobs
Example: T1 = (3, 1), T2 = (10, 4), poller = (2.5, 0.5)
Can we do better?
155
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.
155
Periodic Severs – Terminology
periodic server = a task that behaves much like a periodic task,
but is created for the purpose of executing aperiodic jobs
156
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)
156
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
156
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
156
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)
156
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
156
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
156
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
156
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
156
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)
156
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
157
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
157
Periodic Severs
Deferrable sever
Consumption rules:
158
Periodic Severs
Deferrable sever
Consumption rules:
The budget is consumed at the rate of one per unit time
whenever the server executes
158
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)
158
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:
158
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)
158
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)
158
Deferrable Server – RM
Here the tasks are scheduled using RM.
Is it possible to increase the budget of the server to 1.5 ?
159
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
160
Deferrable Server – Critical Instant
Lemma 23
Assume a fixed-priority scheduling algorithm. Assume that
Di ≤ pi and that the deferrable server (pS, eS) has the highest
priority among all tasks.
161
Deferrable Server – Critical Instant
Lemma 23
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:
161
Deferrable Server – Critical Instant
Lemma 23
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
161
Deferrable Server – Critical Instant
Lemma 23
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
161
Deferrable Server – Critical Instant
Lemma 23
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
161
Deferrable Server – Critical Instant
Lemma 23
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
161
Deferrable Server – Critical Instant
Assume TDS T1 T2 · · · Tn
(i.e. T1 has the highest pririty and Tn lowest)
162
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
163
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
163
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.
163
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
163
Deferrable Server – Time Demand Analysis
TDS = (3, 1.0), T1 = (3.5, 1.5), T2 = (6.5, 0.5)
164
Deferrable Server – Schedulable Utilization
No maximum schedulable utilization is known in general
165
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
165
Deferrable Server – EDF
Here the tasks are scheduled using EDF.
TDS = (3, 1), T1 = (2, 3.5, 1.5), T2 = (6.5, 0.5)
166
Deferrable Server – EDF – Schedulability
Theorem 24
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
167
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 the periodic task (pS, eS)
Therefore special version of time-demand analysis and utilization
bounds were needed.
168
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 the 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.
168
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 the 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
168
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
169
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
169
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
169
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
169
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 ) 169
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
170
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
170
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
170
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
170
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
170
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.
170
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
171
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
171
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)
171
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
171
Real-Time Scheduling
Priority-Driven Scheduling
Sporadic Tasks
172
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
173
Our situation
Based on the execution time and deadline of each newly arrived
sporadic job, decide whether to accept or reject the job
174
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
174
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 174
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
175
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
175
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
175
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
176
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
176
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)
176
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
176
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]
176
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 176
Schedulability of Sporadic Jobs with EDF
Theorem 25
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.
177
Schedulability of Sporadic Jobs with EDF
Theorem 25
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
177
Schedulability of Sporadic Jobs with EDF
Theorem 25
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
177
Schedulability of Sporadic Jobs with EDF
Theorem 25
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)
177
Schedulability of Sporadic Jobs with EDF
Theorem 25
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)
177
Schedulability of Sporadic Jobs with EDF
Theorem 25
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
177
Schedulability of Sporadic Jobs with EDF
Theorem 25
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 ....
177
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
178
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 26
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
178
Admission Control for Sporadic Jobs with EDF
Let ∆ be the total density of periodic tasks.
179
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.
179
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
179
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
179
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
179
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)
179
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
179
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)
179
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, . . . ,
179
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
179
180
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.
181
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.
181
Sporadic Jobs with EDF
One way to schedule sporadic jobs in a fixed-priority system is
to use a sporadic server to execute them
182
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
182
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
182
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
182
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
182
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
183
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
183
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
183
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]
184
Mars Pathfinder
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
The error:
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.
185
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
186
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 187
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
188
Example
At 9, J3 executes U(R) and both J1 and J2 are unblocked. J1 has higher
priority than J2 and executes
At 11, J1 executes U(R) and continues executing
At 12, J1 completes, J2 has higher priority than J3 and has the resource
R, thus executes
At 16, J2 executes U(R) and continues executing
At 17, J2 completes, J3 executes until completion at 18
188
Mars Pathfinder
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.
189
Priority Inversion
Definition 27
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
190
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)
191
Deadlock
Definition 28 (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 ....
192
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
193
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! 194
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.
195
Solutions
Contention for resources causes timing anomalies, priority
inversion and deadlock
Several protocols exist to (partially) solve the above problems:
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 .
196
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 29
Jobs J1, J2, J3 with release times 2, 5, 0, resp., and with
execution times 4, 5, 7, resp.
197
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
198
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)
199
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.)
200
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
201
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
202
Priority-Inheritance Example
At 8, J1 executes L(Shaded) and is blocked by J4. Thus J4 inherits the
priority 1 of J1 and executes
At 9, J4 executes L(Black) and is blocked by J5. Thus J5 inherits the
current priority 1 of J4 and executes
202
Priority-Inheritance Example
At 11, J5 executes U(Black), its priority returns to 5 (the priority before
locking Black). Now J4 has the highest priority (1) and executes
the Black critical section.
Later, when J4 executes U(Black), the priority of J4 remains 1 (since
Shaded blocks J1), and J4 also finishes the Shaded critical section
(at 13).
202
Priority-Inheritance Example
At 13, J4 executes U(Shaded), its priority returns to 4. J1 has now the
highest priority and executes
At 15, J1 completes, J2 is granted Black and has the highest priority and
executes
At 17, J2 completes, afterwards J3, J4, J5 complete.
202
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
203
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 30
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.
204
Lemma 31
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. 205
Priority-Inheritance – The Worst Case
J1 is blocked for the total duration of all critical sections in all lower
priority jobs.
206
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.
207
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
208
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)
209
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.
210
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
211
Priority-Ceiling Protocol
At 8, J1 executes L(Shaded), its priority is higher than Π(t) = 2, its
request is granted and J1 executes; at 9, J1 executes U(Shaded) and at
10 completes
At 11, J5 releases Black and its priority drops to 5; J2 becomes
unblocked, is allocated Black and executes
211
Priority-Ceiling Protocol
At 14, J2 and J3 complete, J4 is granted Shaded (because its priority is
higher than Π(t) = Ω) and executes
At 16, J4 executes L(Black) which is free, the priority of J4 is not higher
than Π(16) = 1 but J4 is the job holding the resource whose priority
ceiling is equal to Π(16). Thus J4 gets Black, continues to execute;
the rest is clear
211
Priority-Ceiling Protocol
Theorem 32
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.
212
These situations cannot occur with priority ceiling protocol:
213
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
214
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
215
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
216
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 30)
priority-ceiling ⇒ bi is bounded by the maximum length of
a critical section
217
Comments on Priority Inheritance Protocol (PIP)
Source: Zhang et al. Priority Inheritance Protocol Proved Correct. ITP 2012
218
Comments on Priority Inheritance Protocol (PIP)
Source: Zhang et al. Priority Inheritance Protocol Proved Correct. ITP 2012
218
Comments on Priority Inheritance Protocol (PIP)
219
Comments on Priority Inheritance Protocol (PIP)
219
Real-Time Scheduling
Multiprocessor Real-Time Systems
220
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.
221
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.
222
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
223
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.
224
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)
224
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)
224
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.
225
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.
226
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
227
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?
228
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}
228
Individual Jobs – Timing Anomalies
Priority order: J1 · · · J4
229
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?
230
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
2 processors.
230
Individual Jobs – Online Scheduling
No optimal online scheduler exists for the following jobs on two
processors:
231
Individual Jobs – Online Scheduling
No optimal online scheduler exists for the following jobs on two
processors:
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
231
Individual Jobs – Online Scheduling
No optimal online scheduler exists for the following jobs on two
processors:
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 jobs J4, J5 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.
231
Individual Jobs – Online Scheduling
No optimal online scheduler exists for the following jobs on two
processors:
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 jobs J4, J5 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.
231
Individual Jobs – Online Scheduling
No optimal online scheduler exists for the following jobs on two
processors:
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 jobs J4, J5 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.
231
Individual Jobs – Speedup Helps(?)
Theorem 33
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.
232
Individual Jobs – Speedup Helps(?)
Theorem 33
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 34
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.
232
Individual Jobs – Speedup Helps(?)
Theorem 33
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 34
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 35
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]
232
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
233
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
233
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
233
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.
233
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)
234
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. RM)
Fixed job-level priority (e.g. EDF)
(Dynamic job-level priority)
234
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. RM)
Fixed job-level priority (e.g. EDF)
(Dynamic job-level priority)
Partitioned scheduling = No migration
Global scheduling = job-level migration
234
Fundamental Limit – Fixed Job-Level Priority
Consider m processors and m + 1 tasks T = {T1, . . . , Tm+1}, each
Ti = (L, 2L − 1).
235
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.
235
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.
235
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).
235
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.
236
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
237
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 ...)
237
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.)
237
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)
238
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 = (1, 2ε) for 1 ≤ i ≤ m
Tm+1 = (1 + ε, 1)
239
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 = (1, 2ε) for 1 ≤ i ≤ m
Tm+1 = (1 + ε, 1)
T is schedulable
Stadnard EDF and RM schedules are not feasible (whiteb.)
239
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 = (1, 2ε) 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)
239
How to avoid Dhall’s effect?
Note that RM and EDF only account for task periods and
ignore the execution time!
240
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
240
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.
241
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?
242
Global Beats Partitioned
There are sets of tasks schedulable only with global scheduler:
T = {T1, T2, T3} where T1 = (2, 1), T2 = (3, 2), T3 = (3, 2),
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.
243
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 = (3, 2), T2 = (4, 3), T3 = (15, 5), T4 = (20, 5), 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.
244
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
245
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.
245
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
245
Real-Time Programming & RTOS
Concurrent and real-time programming tools
246
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
247
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
248
Processes and threads in UNIX
249
Process (Thread) States
250
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
251
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
252
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.
253
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.
254
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
255
Synchronous Message Passing
256
Asynchronous Message Passing
257
Asynch. Message Passing with Bounded Buffer
258
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.
259
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
260
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
261
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)
262
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).
263
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
264
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() 265
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)
266
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)
267
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
268
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.
269
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?
270
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
271
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
272
Real-Time Programming & RTOS
Real-Time Operating systems
273
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, ...
274
Operating Systems – What You Should Know ...
275
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?
276
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
277
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, ...
278
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
279
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
280
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)
281
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
282
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 .... 283
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
284
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. 285
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. 286
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.)
287
Real-Time Programming & RTOS
Real-Time Programming Languages
Brief Overview
288
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
289
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. 290
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
}
291
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);
}
292
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.
293
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)
294
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)
295
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 */
};
296
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 297
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
298
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
299
POSIX-compliant RTOS
Examples of POSIX-compliant implementations:
commercial:
VxWorks
QNX
OSE
Linux-related:
RTLINUX
RTAI
300
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
301
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
302
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
303
Event Latency
304
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++
305
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
306
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
307
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
308
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
309
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
310
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
311
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.
312
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())
313
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
314
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
315
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.
316