Transcript real-time system - Computer Science

Real-Time Systems
Introduction
Frank Drews
[email protected]
Frank Drews
Real-Time Systems
Real-time Systems
• A real-time system is a system whose
specification includes both logical and temporal
correctness requirements.
• Logical Correctness: Produces correct outputs.
– Can by checked, for example, by Hoare logic.
• Temporal Correctness: Produces outputs at
the right time.
– In this course, we spend much time on techniques
and technologies for achieving and checking temporal
correctness.
Frank Drews
Real-Time Systems
Embedded Systems
• [www.webopedia.com]:
An embedded system is “a specialized
computer system that is part of a larger system
or machine. Typically, an embedded system is
housed on a single microprocessor board with
the programs stored in ROM. Virtually all
appliances that have digital interfaces (e.g.,
watches, microwaves, VCRs, cars) utilize
embedded systems […]”
• Many embedded systems are real-time systems
Frank Drews
Real-Time Systems
Typical Characteristics of RealTime Systems
•
•
•
•
•
•
Event-driven, reactive.
High cost of failure.
Concurrency/multiprogramming.
Stand-alone/continuous operation.
Reliability/fault-tolerance requirements.
Predictable behavior.
Frank Drews
Real-Time Systems
Misconceptions about Real-Time Systems
(Stankovic ‘88)
• There is no science in real-time-system design.
– We shall see…
• Advances in supercomputing hardware will take
care of real-time requirements.
– The old “buy a faster processor” argument…
• Real-time computing is equivalent to fast
computing.
– Only to ad agencies. To us, it means PREDICTABLE
computing.
Frank Drews
Real-Time Systems
Misconceptions (Continued)
• Real-time programming is assembly coding,
– We would like to automate (as much as possible) real-time
system design, instead of relying on clever hand-crafted code.
• “Real time” is performance engineering.
– In real-time computing, timeliness is almost always more
important than raw performance …
• “Real-time problems” have all been solved in other areas
of CS or operations research.
– OR people typically use stochastic queuing models or one-shot
scheduling models to reason about systems.
– In other CS areas, people are usually interested in optimizing
average-case performance.
Frank Drews
Real-Time Systems
Misconceptions (Continued)
• It is not meaningful to talk about
guaranteeing real-time performance when
things can fail.
– Though things may fail, we certainly don’t
want the operating system to be the weakest
link!
• Real-time systems function only in a static
environment.
– Note true. We consider systems in which the
environment may change dynamically.
Frank Drews
Real-Time Systems
Are All Systems Real-Time
Systems?
• Question: Is a payroll processing system a
realtime system?
– It has a time constraint: Print the pay checks every
two weeks.
• Perhaps it is a real-time system in a definitional
sense, but it doesn’t pay us to view it as such.
• We are interested in systems for which it is not a
priori obvious how to meet timing constraints
Frank Drews
Real-Time Systems
The “Window of Scarcity”
Resources may be categorized as:
• Abundant: Virtually any system design
methodology can be used to realize the timing
requirements of the application.
• Insufficient: The application is ahead of the
technology curve; no design methodology can
be used to realize the timing requirements of the
application.
• Sufficient but scarce: It is possible to realize
the timing requirements of the application, but
careful resource allocation is required.
Frank Drews
Real-Time Systems
Example: Interactive/Multimedia
Applications
Frank Drews
Real-Time Systems
Example: Real-Time Applications
Many real-time systems are control systems
Example 1: A simple one-sensor, oneactuator control system
Frank Drews
Real-Time Systems
Simple Control System (Continued)
Pseudo-code for this system:
T is called sampling period. T is a key design choice.
Typical range for T: seconds to milliseconds.
Frank Drews
Real-Time Systems
Time
Frank Drews
Real-Time Systems
Multi-rate Control Systems
More complicated control systems have multiple sensors
and actuators and must support control loops of different
rates.
Example 2: Helicopter flight controller.
Note: Having only harmonic rates simplifies the system
Frank Drews
Real-Time Systems
Hierarchical Control Systems
Frank Drews
Real-Time Systems
Air Traffic Control
[Reddaway et al. WMPP’05]
Frank Drews
Real-Time Systems
Signal-Processing System
• Signal-processing systems transform
data from one form to another.
• Examples:
– Digital filtering.
– Video and voice compression/decompression.
– Radar signal processing.
• Response times range from a few
milliseconds to a few seconds.
Frank Drews
Real-Time Systems
Example: Radar System
Frank Drews
Real-Time Systems
Internet/Multimedia Applications
•
Web farms hosting multiple web
domains
static
dynamic streaming
content content video/audio
– Each web domain receives a certain
share of the overall resources (CPU,
network, file system)
– Each web domain consists of an
application pool (static content,
dynamic content, streaming
video/audio, etc.)
•
Server
Challenges
– Sharing the resource among domains
(i.e. application pools) may be hard in
general purpose Operating Systems
– Guarantee of a uniform, steady, jitterfree execution of time critical
multimedia applications while not
starving other applications
– Support of multiprocessor server
systems
Frank Drews
Real-Time Systems
Domain 1
Domain 3
Domain 2
Other Real-Time Applications
• Real-time databases.
– Transactions must complete by deadlines.
– Main dilemma: Transaction scheduling algorithms and real-time
scheduling algorithms often have conflicting goals.
– Data may be subject to absolute and relative temporal
consistency requirements.
– Overall goal: reliable responses
• Multimedia.
• Want to process audio and video frames at steady rates.
– TV video rate is 30 frames/sec. HDTV is 60 frames/sec.
– Telephone audio is 16 Kbits/sec. CD audio is 128 Kbits/sec.
• Other requirements: Lip synchronization, low jitter, low
end-to-end response times (if interactive).
Frank Drews
Real-Time Systems
Hard vs. Soft Real Time
• Task: A sequential piece of code.
• Job: Instance of a task
• Jobs require resources to execute.
– Example resources: CPU, network, disk, critical section.
– We will simply call all hardware resources “processors”.
• Release time of a job: The time instant the job
becomes ready to execute.
• Deadline of a job: The time instant by which the job
must complete execution.
• Relative deadline of a job: “Deadline - Release time”.
• Response time of a job: “Completion time - Release
time”.
Frank Drews
Real-Time Systems
Example
Job is released at time 3.
It’s absolute deadline is at time 10.
It’s relative deadline is 7.
It’s response time is 6.
Frank Drews
Real-Time Systems
Hard Real-Time Systems
• A hard deadline must be met.
– If any hard deadline is ever missed, then the system
is incorrect.
– Requires a means for validating that deadlines are
met.
• Hard real-time system: A real-time system in
• which all deadlines are hard.
– We consider hard and soft real-time systems in this
course.
• Examples: Nuclear power plant control, flight
control.
Frank Drews
Real-Time Systems
Soft Real-Time Systems
• A soft deadline may occasionally be
missed.
– Question: How to define “occasionally”?
• Soft real-time system: A real-time system
in which some deadlines are soft.
• Examples: multimedia applications.
Frank Drews
Real-Time Systems
Performance
• Two particular factors are important
– How fast does a system respond
– When it fails, what happens?
Frank Drews
Real-Time Systems
The Speed of Response
• All required responses are time-critical
– The designer should predict the delivered
performance of the systems with the required
performance
– Unfortunately, it may not be possible to give
100% guarantees
Frank Drews
Real-Time Systems
Periodic vs. Aperiodic Tasks
• Periodic Tasks
– Tasks run at regular, pre-defined intervals
– Example: closed loop digital controller having
fixed, pre-set sampling rates
Execute
control task
Execute
control task
Idle time
Idle time
time
Sampling interval
t0
Frank Drews
t1
Synchronous real-time clock signals
Real-Time Systems
t2
Periodic vs. Aperiodic Tasks
• Aperiodic Tasks
– Occur when the computer must respond to (generally) external events which
occur at random (asynchronous or aperiodic); have either soft or no deadlines
•
Sporadic Tasks
– Similar to aperiodic tasks; however, the event must be serviced within a specific
maximum time period; hard deadline
Execute
event task
Idle
time
Execute
event task
Execute
event task
Idle time
time
e0
Frank Drews
e1
Asynchronous events
Real-Time Systems
e2
Mixing Periodic and Aperiodic
Tasks
• We get into trouble in situations which
involve a mix of periodic and
aperiodic(sporadic) events, which are
usual in real-time designs
• Much thought and skill are needed to deal
with the response requirements of periodic
and aperiodic tasks
Frank Drews
Real-Time Systems
Real-Time Operating Systems
(RTOSs)
• RTOS: specialized operating system for RTS
• Main responsibilities:
– Process management
– Resource allocation (processor, memory, network)
• They may not include regular OS facilities such as file
management, virtual memory, user/kernel level
separation, etc.
• Manage at least two priority levels:
– Interrupt level, for processes that need fast response
– Clock level, for periodic processes
• Typical components: real-time clock, interrupt handler,
scheduler, resource manager, dispatcher
Frank Drews
Real-Time Systems