Transcript Introduction to Real Time Systems

Introduction
to
Real Time Systems
Akos Ledeczi
EECE 354, Fall 2010
Vanderbilt University
Disclaimer
• Some of the slides are adapted from various
presentations found on the internet:
– Johnnie W. Baker
– Ian Sommerville
– Alan Burns and Andy Wellings
– others
Embedded vs. Real Time Systems
• Embedded system: is a computer system that performs a
limited set of specific functions. It often interacts with its
environment.
• RTS: Correctness of the system depends not only on the
logical results, but also on the time in which the results are
produced.
Real Time
Systems
Embedded
Systems
Examples?
Examples
• Real Time Embedded:
–
–
–
–
–
–
Nuclear reactor control
Flight control
Basically any safety critical system
GPS
MP3 player
Mobile phone
• Real Time, but not Embedded:
– Stock trading system
– Skype
– Pandora
• Embedded, but not Real Time:
–
–
–
–
Home temperature control
Sprinkler system
Washing machine, refrigerator, etc.
Blood pressure meter
Characteristics of RTS
•
•
•
•
•
•
Event-driven, reactive.
High cost of failure.
Concurrency/multiprogramming.
Stand-alone/continuous operation.
Reliability/fault-tolerance requirements.
Predictable behavior.
Definitions
•
Hard real-time — systems where it is absolutely imperative that responses occur
within the required deadline. E.g. Flight control systems.
•
Soft real-time — systems where deadlines are important but which will still
function correctly if deadlines are occasionally missed. E.g. Data acquisition
system.
•
Real real-time — systems which are hard real-time and which the response times
are very short. E.g. Missile guidance system.
•
Firm real-time — systems which are soft real-time but in which there is no benefit
from late delivery of service.
A single system may have all hard, soft and real real-time subsystems.
In reality many systems will have a cost function associated with missing each deadline
Control systems
Example: A simple one-sensor, one-actuator control system.
reference
input r(t)
A/D
A/D
rk
yk
control-law
computation
uk
D/A
y(t)
sensor
Outside effects
u(t)
plant
actuator
The system
being controlled
Control systems cont’d.
Pseudo-code for this system:
set timer to interrupt periodically with period T;
at each timer interrupt do
do analog-to-digital conversion to get y;
compute control output u;
output u and do digital-to-analog conversion;
end do
T is called the sampling period. T is a key design choice. Typical
range for T: seconds to milliseconds.
Taxonomy of Real-Time Systems
9
Taxonomy of Real-Time Systems
10
Taxonomy of Real-Time Systems
11
Taxonomy: Static
• Task arrival times can be predicted
• Static (compile-time) analysis possible
• Allows good resource usage (low idle time for
processors).
12
Taxonomy: Dynamic
• Arrival times unpredictable
• Static (compile-time) analysis possible only for
simple cases.
• Processor utilization decreases dramatically.
• In many real systems, this is very difficult to
handle.
• Must avoid over-simplifying assumptions
– e.g., assuming that all tasks are independent,
when this is unlikely.
13
Taxonomy: Soft Real-Time
• Allows more slack in the implementation
• Timings may be suboptimal without being
incorrect.
• Problem formulation can be much more
complicated than hard real-time
• Two common and an uncommon way of handling
non-trivial soft real-time system requirements
– Set somewhat loose hard timing constraints
– Informal design and testing
– Formulate as an optimization problem
14
Taxonomy: Hard Real-Time
• Creates difficult problems.
– Some timing constraints are inflexible
• Simplifies problem formulation.
15
Taxonomy: Periodic
• Each task (or group of tasks) executes
repeatedly with a particular period.
• Allows some static analysis techniques to be
used.
• Matches characteristics of many real problems
• It is possible to have tasks with deadlines
smaller, equal to, or greater than their period.
– The later are difficult to handle (i.e., multiple
concurrent task instances occur).
16
Periodic
• Single rate:
– One period in the system
– Simple but inflexible
– Used in implementing a lot of wireless sensor
networks.
• Multi rate:
– Multiple periods
– Should be harmonics to simplify system design
17
Taxonomy: Aperiodic
• Are also called sporadic, asynchronous, or
reactive.
• Creates a dynamic situation
• Bounded arrival time interval are easier to
handle
• Unbounded arrival time intervals are
impossible to handle with resourceconstrained systems.
18
Example: Adaptive Cruise Control
• Demo video
• Control system
• Hard Real Time
• Multi-rate periodic
• Camera
• GPS
• Low-speed mode for
rush hour traffic
United States Patent 7096109
Data Acquisition and Signal-Processing
Systems
• Examples:
–
–
–
–
Video capture.
Digital filtering.
Video and voice compression/decompression.
Radar signal processing.
• Response times range from a few milliseconds to a few
seconds.
• Typically simpler than control systems
Other Real-Time Applications
• Real-time databases.
• Examples: stock market, airline reservations, etc.
• Transactions must complete by deadlines.
• Main dilemma: Transaction scheduling algorithms and real-time
scheduling algorithms often have conflicting goals.
• Data is subject temporal consistency requirements.
• 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).
Are All Systems Real-Time Systems?
• Question: Is a payroll processing system a real-time 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.
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.
Example: Interactive/Multimedia
Applications
Requirements
(performance, scale)
Interactive
Video
The interesting
real-time
applications
are here
sufficient
but scarce
resources
insufficient
resources
High-quality
Audio
Network
File Access
abundant
resources
Remote
Login
1980
1990
2000
Hardware resources in year X
OS or not?
User Programs
User Program
Operating
Including Operating
Hardware
Hardware
System
Typical OS Configuration
System Components
Typical Embedded Configuration
Foreground/Background Systems
• Task-level, interrupt level
• Critical operations must
be performed at the
interrupt level (not good)
• Response time/timing
depends on the entire
loop
• Code change affects
timing
• Simple, low-cost systems
RTS Programming
•
•
•
Because of the need to respond to timing demands made by different stimuli/responses,
the system architecture must allow for fast switching between stimulus handlers.
Because of different priorities, unknown ordering and different timing requirements of
different stimuli, a simple sequential loop is not usually adequate.
Real-time systems are therefore usually designed as cooperating processes with a real-time
kernel controlling these processes.
Concurrent programming
Real Time Java?
• Java supports lightweight concurrency (threads and
synchronized methods) and can be used for some soft
real-time systems.
• Java is not suitable for hard RT programming but real-time
versions of Java are now available that address problems
such as
– Not possible to specify thread execution time;
– Uncontrollable garbage collection;
– Not possible to access system hardware;
– Etc.
– Real-Time Specification for Java
– Sun Java Real-Time System
Requires a Real Time OS underneath (e.g., no Windows support)
Classification of Scheduling Algorithms
All scheduling algorithms
static scheduling
(or offline, or clock driven)
dynamic scheduling
(or online, or priority driven)
static-priority
scheduling
dynamic-priority
scheduling
Scheduling strategies
• Non pre-emptive scheduling
– Once a process has been scheduled for execution, it runs to
completion or until it is blocked for some reason (e.g. waiting for I/O).
• Pre-emptive scheduling
– The execution of an executing processes may be stopped if a higher
priority process requires service.
• Scheduling algorithms
–
–
–
–
Round-robin;
Rate monotonic;
Shortest deadline first;
Etc.
Real-time operating systems
• Real-time operating systems are specialised operating systems
which manage the processes in the RTS.
• Responsible for process management and
resource (processor and memory) allocation.
• Do not normally include facilities such as file management.
14
Operating system components
• Real-time clock
– Provides information for process scheduling.
• Interrupt handler
– Manages aperiodic requests for service.
• Scheduler
– Chooses the next process to be run.
• Resource manager
– Allocates memory and processor resources.
• Dispatcher
– Starts process execution.
Interrupt servicing
• Control is transferred automatically to a
pre-determined memory location.
• This location contains an instruction to jump to
an interrupt service routine.
• Further interrupts are disabled, the interrupt
serviced and control returned to the interrupted
process.
• Interrupt service routines MUST be short,
simple and fast.
What’s Important in Real-Time
Metrics for real-time systems differ from that for time-sharing systems.
Time-Sharing
Systems
Real-Time
Systems
Capacity
High throughput
Schedulability
Responsiveness
Fast average response
Ensured worst-case
response
Overload
Fairness
Stability
– schedulability is the ability of tasks to meet all hard deadlines
– latency is the worst-case system response time to events
– stability in overload means the system meets critical deadlines even if all
deadlines cannot be met