Introduction

COE186 | Real-Time Systems

Development

Slides from
Real Time Operating Systems and Middleware
Prof. Luca Abeni Introduction to the Course
Overview of the Course - 1
• Real-Time Systems: what are they?
• Real-Time Computing, Temporal Constraints
• Definitions and task model
• Real-Time scheduling
• Notes about real-time programming, RT-POSIX,
pthreads, . . .
• Real-Time Scheduling
• Fixed Priority scheduling, RM, DM
• EDF and dynamic priorities
• Resource Sharing (Priority Inversion, etc...)

Introduction to the Course

Overview of the Course - 2
• Operating System structure
• Notes about traditional kernel structures
• Sources of kernel latencies
• Some approaches to real-time kernels:
• dual kernel approach
• interrupt pipes
• microkernels
• monolithic kernels and RT
• Real-Time Kernels and OSs
• Developing Real-Time applications

Introduction to the Course

Real-Time Operating Systems

• Real-Time operating system (RTOS): OS providing

support to Real-Time applications
• Real-Time application: the correctness depends not
only on the output values, but also on the time when
such values are produced
• Operating System:
• Set of computer programs
• Interface between applications and hardware
• Control the execution of application programs
• Manage the hardware and software resources

Introduction to the Course

Different Visions of an OS
• An OS manages resources to provide services...
• ...hence, it can be seen as:
• A Service Provider for user programs
• Exports a programming interface...
• A Resource Manager
• Implements schedulers...

Introduction to the Course

Operating System as a Resource Manager

• Process and Memory Management

• File Management
• VFS
• File System
• Networking, Device Drivers, Graphical Interface
Resources must be managed so that
real-time applications are served properly

Introduction to the Course

Operating System Services
• Services (Kernel Space):
• Process Synchronisation, Inter-Process
Communication (IPC)
• Process / Thread Scheduling
• I/O
• Virtual Memory
Specialised API?

Introduction to the Course

Resource Management Algorithms
• Resource Manager (device drivers, ...)
• Interrupt Handling
• Device Management
• ...
OS Structure?

Introduction to the Course

Real-Time Systems: What???
• Real-Time application: the time when a result is
produced matters
• a correct result produced too late is equivalent to
a wrong result, or to no result
• characterised by temporal constraints that have
to be respected
• Example: mobile vehicle with a software module that
1. Detects obstacles
2. Computes a new trajectory to avoid them
3. Computes the commands for engine, brakes, . . .
4. Sends the commands

Introduction to the Course

Real-Time Systems: What???
• If the commands are correctly computed, but are not
sent in time...
• ...The vehicle crashes into the obstacle before
receiving the commands!
• Examples of temporal constraints:
• must react to external events in a predictable
time
• must repeat a given activity at a precise rate
• must end an activity before a specified time
• Temporal constraints are modelled using the concept
of deadline

Introduction to the Course

Real-Time & Determinism
• A Real-Time system is not just a “fast system” . . .
• speed is always relative to a specific environment!
• Running faster is good, but does not guarantee a
correct behaviour
• It must be possible to prove that temporal
constraints are always respected
• Running “fast enough”
• . . . ⇒ worst-case analysis

Introduction to the Course

Throughtput vs Real-Time
• Real-Time systems and general-purpose systems
have different goals
• General-purpose systems are optimised for the
“most common” or “average” case → fast sytems
• Real-Time systems only care about the worst
case
• In general, fast systems tend to minimise the
average response time of a task set . . .
• . . . While a real-time system must guarantee the
timing behaviour of RT tasks!

Introduction to the Course

Processes, Threads, and Tasks

• Algorithm → logical procedure used to solve a

problem
• Program → formal description of an algorithm, using
a programming language
• Process → instance of a program (program in
execution)
• Thread → flow of execution
• Task → process or thread

Introduction to the Course

 Real-Time Tasks
• A task can be seen as a sequence of actions . . .
• . . . and a deadline must be associated to each one
of them!
• Some kind of formal model is needed to identify
these “actions” and associate deadlines to them

Introduction to the Course

Mathematical Model of a Task - 1
• Real-Time task τi: stream of jobs (or instances) Ji,k
• Each job Ji,k = (ri,k, ci,k, di,k):
• Arrives at time ri,k (activation time)
• Executes for a time ci,k
• Finishes at time f i,k
• Should finish within an absolute deadline di,k

ci,k
ri,k fi,k di,k

Introduction to the Course

Mathematical Model of a Task - 2

• Job: abstraction used to associate deadlines

(temporal constraints) to activities
• ri,k: time when job Ji,k is activated (by an external
event, a timer, an explicit activation, etc...)
• ci,k: computation time needed by job Ji,k to
complete
• di,k: absolute time instant by which job Ji,k must
complete
• job Ji,k respects its deadline if f i,k ≤ di,k
• Response time of job Ji,k: ρi,k = f i,k − ri,k

Introduction to the Course

 Periodic Tasks
Periodic task τi = (C i , D i , Ti): stream of jobs Ji,k, with

ri,k+1 = ri,k + Ti
di,k = ri,k + D i
C i = max{ci,k}
k

• Ti is the task period, D i is the task relative deadline,

C i is the task worst-case execution time (WCET)
• R i : worst-case response time →
R i = maxk{ρi,k} = maxk{fi,k − ri,k}
• for the task to be correctly scheduled, it must be
Ri ≤ Di

Introduction to the Course

Example: Periodic Task Model
• A periodic task has a regular structure (cycle):
• activate periodically (period Ti)
• execute a computation
• suspend waiting for the next period

void *PeriodicTask(void *arg)

{
<initialization>;
<start periodic timer, period = T>;
while (cond) {
<read sensors>;
<update outputs>;
<update state variables>;
<wait next activation>;
}
}

Introduction to the Course

Graphical Representation
Tasks are graphically represented by using a scheduling
diagram. For example, the following picture shows a
schedule of a periodic task τ1 = (3, 6, 8) (with
WCET 1 = 3, D 1 = 6, T1 = 8)

τ1

0 2 4 6 8 10 12 14 16 18 20 22 24

Notice that, while job J1,1 and J1,3 execute for 3 units of
time (WCET), job J1,2 executes for only 2 units of time.

Introduction to the Course

 Aperiodic Tasks
• Aperiodic tasks are not characterised by periodic
arrivals:
• A minimum interarrival time between activations
does not exist
• Sometimes, aperiodic tasks do not have a
particular structure
• Aperiodic tasks can model:
• Tasks responding to events that occur rarely.
Example: a mode change.
• Tasks responding to events with irregular
structure (bursts of packets from the network, ...)

Introduction to the Course

Aperiodic Tasks - Example
The following example shows a possible arrival pattern
for an aperiodic task τ1

τ1

0 2 4 6 8 10 12 14 16 18 20 22 24

Notice that arrivals might be bursty, and there is not a

minimum time between them.

Introduction to the Course

Sporadic tasks
• Sporadic tasks: aperiodic tasks with a minimum
interarrival time between jobs
• In this sense, they are similar to periodic tasks, but...
• Periodic task ⇒ activated by a periodic timer
• Sporadic task ⇒ activated by an external event
(for example, the arrival of a packet from the
network)
void *SporadicTask(void *)
{
<initialization>;
while (cond) {
<computation>;
<wait event>;
}
}
Introduction to the Course
Mathematical model of a sporadic task
Similar to a periodic task: a sporadic task
τi = (C i , D i , Ti) is a stream of jobs Ji,k, with

ri,k+1 ≥ ri,k + Ti
di,k = ri,k + D i
Ci = max{ci,k}
k

• Ti is the task minimum interarrival time (MIT);

• D i is the task relative deadline;
• C i is the task worst-case execution time (WCET).
• The task is correctly scheduled if R i ≤ D i .

Introduction to the Course

Graphical representation
The following example, shows a possible schedule of a
sporadic task τ1 = (2, 5, 9).

τ1

0 2 4 6 8 10 12 14 16 18 20 22 24 26

Notice that
r1,2 = 12 > r1,1 + T1 = 9
r1,3 = 21 = r1,2 + T1 = 21

Introduction to the Course

Task Criticality - 1
• A deadline is said to be hard if a deadline miss
causes a critical failure in the system
• A task is said to be a hard real-time task if all its
deadlines are hard
• All the deadlines must be guaranteed
(∀j, ρi,j ≤ D i ⇒ R i ≤ D i ) before starting the task
• Examples:
• The controller of a mobile robot, must detect
obstacles and react within a time dependent on
the robot speed, otherwise the robot will crash
into the obstacles.

Introduction to the Course

Task Criticality - 2
• A deadline is said to be soft if a deadline miss
causes a degradation in the Quality of Service, but is
not a catastrophic event
• A task is said to be a soft real-time task if it has soft
deadlines
• Some deadlines can be missed without
compromising the correctness of the system...
• ... But the number of missed deadlines must be
kept under control, because the “quality” of the
results depend on the number of missed
deadlines

Introduction to the Course

Soft Real-Time Requirements - 1

• Characterising a soft real-time task can be difficult...

• What’s the tradeoff between “non compromising
the system correctness” and not considering
missed deadlines?
• Some way to express the QoS experienced by a
(soft) real-time task is needed
• Examples of QoS definitions:
• no more than X consecutive deadlines can be
missed
• no more than X deadlines in an interval of time T
can be missed

Introduction to the Course

Soft Real-Time Requirements - 2
• Other examples of soft real-time constraints:
• the deadline miss probability must be less than a
specified value
• P {f i,j > di,j } ≤ Rmax
• the deadline miss ratio can be used instead
number of missed deadlines
≤ Rmax
total number of deadlines
• the maximum tardiness must be less than a
specified value
Ri
• D i
< L
• ...
Introduction to the Course
Example of Soft Real-Time
• Audio / Video player:
• fps: 25 ⇒ frame period: 40ms
• if a frame is played a little bit too late, the user
might even be unable to notice any degradation
in the QoS...
• ...but skipped frames can be disturbing
• missing a lot of frames by 5ms can be better
than missing only few frames by 40ms!
• In some robotic systems, some actuations can be
delayed with little consequences on the control
quality
• In any case, soft real-time does not mean no
guarantee on deadlines...
Introduction to the Course
Job Execution Times
• Tasks can have variable execution times between
different jobs
• Execution times might depend on different factors:
• Input data
• Hw issues (cache effects, pipeline stalls, ...)
• The internal state of the task
• ...

τ1

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34

Introduction to the Course

Variable Execution Times: Video Player
Distribution of the job execution times for a video player
(frame decoding times for an MPEG video)
0.1

0.09

0.08

0.07
probability density

0.06

0.05

0.04

0.03

0.02

0.01

0
0 2000 4000 6000 8000 10000

decoding time (microseconds)

Introduction to the Course