Real-time computing
Encyclopedia
In computer science
, real-time computing (RTC), or reactive computing, is the study of hardware
and software
systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints. Often real-time response times are understood to be in the order of milliseconds and sometimes microseconds. In contrast, a non-real-time system is one that cannot guarantee a response time in any situation, even if a fast response is the usual result.
The use of this word should not be confused with the two other legitimate uses of real-time, which in the domain of simulations, means real-clock synchronous, and in the domain of data transfer, media processing and enterprise systems, the term is intended to mean without perceivable delay.
The needs of real-time software requires the use of one or more synchronous programming language
s, real-time operating system
s, and real-time networks which provide the essential frameworks on which to build a real-time software application.
A real-time system may be one where its application can be considered (within context) to be mission critical
. The anti-lock brakes on a car are a simple example of a real-time computing system — the real-time constraint in this system is the time in which the brakes must be released to prevent the wheel from locking. Real-time computations can be said to have failed if they are not completed before their deadline, where their deadline is relative to an event. A real-time deadline must be met, regardless of system load
.
, where a real-world process is simulated at a rate that matched that of the real process (now called Real-time Simulation
to avoid ambiguity). Analog computers, most often, were capable of simulating at a much faster pace than real-time, a situation that could be just as dangerous as a slow simulation if it were not also recognized and accounted for.
Thus, the goal of a hard real-time system is to ensure that all deadlines are met, but for soft real-time systems the goal becomes meeting a certain subset of deadlines in order to optimize some application specific criteria. The particular criteria optimized depends on the application, but some typical examples include maximizing the number of deadlines met, minimizing the lateness of tasks and maximizing the number of high priority tasks meeting their deadlines.
Hard real-time systems are used when it is imperative that an event be reacted to within a strict deadline. Such strong guarantees are required of systems for which not reacting in a certain interval of time would cause great loss in some manner, especially damaging the surroundings physically or threatening human lives (although the strict definition is simply that missing the deadline constitutes failure of the system). For example, a car
engine
control system is a hard real-time system because a delayed signal may cause engine failure or damage. Other examples of hard real-time embedded systems include medical systems such as heart pacemaker
s and industrial process controllers. Hard real-time systems are typically found interacting at a low level with physical hardware, in embedded system
s. Early video game systems such as the Atari 2600
and Cinematronics
vector graphics had hard real-time requirements because of the nature of the graphics and timing hardware.
In the context of multitasking
systems the scheduling policy is normally priority driven (pre-emptive schedulers). Other scheduling algorithms include Earliest Deadline First
, which, ignoring the overhead of context switch
ing, is sufficient for system loads of less than 100%. New overlay scheduling systems, such as an Adaptive Partition Scheduler
assist in managing large systems with a mixture of hard real-time and non real-time applications.
Soft real-time systems are typically used where there is some issue of concurrent access and the need to keep a number of connected systems up to date with changing situations; for example software that maintains and updates the flight plans for commercial airline
rs. The flight plans must be kept reasonably current but can operate to a latency of seconds. Live audio-video systems are also usually soft real-time; violation of constraints results in degraded quality, but the system can continue to operate.
process, the analyzed (input) and generated (output) samples can be processed (or generated) continuously in the time it takes to input and output the same set of samples independent of the processing delay. It means that the processing delay must be bounded even if the processing continues for an unlimited time. That means that the average processing time per sample is no greater than the sampling period, which is the reciprocal of the sampling rate
. This is the criterion whether the samples are grouped together in large segments and processed in blocks or are processed individually and whether there are long, short, or non-existent input and output buffers.
Consider an audio DSP
example: if a process requires 2.01 seconds to analyze
, synthesize, or process 2.00 seconds of sound, it is not real-time. If it takes 1.99 seconds, it is or can be made into, a real-time DSP process.
A common life analog is standing in a line or queue
waiting for the checkout in a grocery store. If the line asymptotically grows longer and longer without bound, the checkout process is not real-time. If the length of the line is bounded, customers are being "processed" and outputted as rapidly, on average, as they are being inputted and that process is real-time. The grocer might go out of business or must at least lose business if he/she cannot make his/her checkout process real-time (so it's fundamentally important that this process be real-time).
A signal processing algorithm that cannot keep up with the flow of input data with output getting farther and farther behind the input is not real-time. But if the delay is bounded during a process that operates over an unlimited time, then that signal processing algorithm is real-time, even if the throughput delay may be very long.
, but this is not always the case. For example, a massive supercomputer
executing a scientific simulation may offer impressive performance, yet it is not executing a real-time computation. Conversely, once the hardware and software for an anti-lock braking system has been designed to meet its required deadlines, no further performance gains are obligatory. Furthermore, if a network server is highly loaded with network traffic
, its response time may be slower but will (in most cases) still succeed before it times out (hits its deadline). Hence, such a network server would not be considered a real-time system: temporal failures (delays, time-outs, etc.) are typically small and compartmentalized (limited in effect) but are not catastrophic failures. In a real-time system, such as the FTSE 100 Index
, a slow-down beyond limits would often be considered catastrophic in its application context. Therefore, the most important requirement of a real-time system is predictability and not performance.
Some kinds of software, such as many chess-playing programs
, can fall into either category. For instance, a chess program designed to play in a tournament with a clock will need to decide on a move before a certain deadline or lose the game, and is therefore a real-time computation, but a chess program that is allowed to run indefinitely before moving is not. In both of these cases, however, high performance is desirable: the more work a tournament chess program can do in the allotted time, the better its moves will be, and the faster an unconstrained chess program runs, the sooner it will be able to move. This example also illustrates the essential difference between real-time computations and other computations: if the tournament chess program does not make a decision about its next move in its allotted time it loses the game—i.e., it fails as a real-time computation—while in the other scenario, meeting the deadline is assumed not to be necessary.
, an old but very successful method which represents the concurrent
structure of the system. Other examples are HOOD
, Real-Time UML, AADL the Ravenscar profile
, Real-Time Java
, WIMS Engine Server (a true-realtime web
implementation).
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, real-time computing (RTC), or reactive computing, is the study of hardware
Computer hardware
Personal computer hardware are component devices which are typically installed into or peripheral to a computer case to create a personal computer upon which system software is installed including a firmware interface such as a BIOS and an operating system which supports application software that...
and software
Computer software
Computer software, or just software, is a collection of computer programs and related data that provide the instructions for telling a computer what to do and how to do it....
systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints. Often real-time response times are understood to be in the order of milliseconds and sometimes microseconds. In contrast, a non-real-time system is one that cannot guarantee a response time in any situation, even if a fast response is the usual result.
The use of this word should not be confused with the two other legitimate uses of real-time, which in the domain of simulations, means real-clock synchronous, and in the domain of data transfer, media processing and enterprise systems, the term is intended to mean without perceivable delay.
The needs of real-time software requires the use of one or more synchronous programming language
Synchronous programming language
A synchronous programming language is a computer programming language optimized for programming reactive systems, systems that are often interrupted and must respond quickly. Many such systems are also called realtime systems, and are found often in embedded uses. The term 'reactive' is chosen to...
s, real-time operating system
Real-time operating system
A real-time operating system is an operating system intended to serve real-time application requests.A key characteristic of a RTOS is the level of its consistency concerning the amount of time it takes to accept and complete an application's task; the variability is jitter...
s, and real-time networks which provide the essential frameworks on which to build a real-time software application.
A real-time system may be one where its application can be considered (within context) to be mission critical
Mission Critical
Mission critical refers to any factor of a system whose failure will result in the failure of business operations. That is, it is critical to the organization's 'mission'....
. The anti-lock brakes on a car are a simple example of a real-time computing system — the real-time constraint in this system is the time in which the brakes must be released to prevent the wheel from locking. Real-time computations can be said to have failed if they are not completed before their deadline, where their deadline is relative to an event. A real-time deadline must be met, regardless of system load
Load (computing)
In UNIX computing, the system load is a measure of the amount of work that a computer system performs. The load average represents the average system load over a period of time...
.
History
The term real-time derives from its use in early simulationSimulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....
, where a real-world process is simulated at a rate that matched that of the real process (now called Real-time Simulation
Real-time Simulation
Real-time Simulation refers to a computer model of a physical system that can execute at the same rate as actual "wall clock" time. In other words, the computer model runs at the same rate as the actual physical system...
to avoid ambiguity). Analog computers, most often, were capable of simulating at a much faster pace than real-time, a situation that could be just as dangerous as a slow simulation if it were not also recognized and accounted for.
Criteria for real-time computing
A system is said to be real-time if the total correctness of an operation depends not only upon its logical correctness, but also upon the time in which it is performed. Real-time systems, as well as their deadlines, are classified by the consequence of missing a deadline.- Hard
- Missing a deadline is a total system failure.
- Firm
- Infrequent deadline misses are tolerable, but may degrade the system's quality of service. The usefulness of a result is zero after its deadline.
- Soft
- The usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.
Thus, the goal of a hard real-time system is to ensure that all deadlines are met, but for soft real-time systems the goal becomes meeting a certain subset of deadlines in order to optimize some application specific criteria. The particular criteria optimized depends on the application, but some typical examples include maximizing the number of deadlines met, minimizing the lateness of tasks and maximizing the number of high priority tasks meeting their deadlines.
Hard real-time systems are used when it is imperative that an event be reacted to within a strict deadline. Such strong guarantees are required of systems for which not reacting in a certain interval of time would cause great loss in some manner, especially damaging the surroundings physically or threatening human lives (although the strict definition is simply that missing the deadline constitutes failure of the system). For example, a car
Automobile
An automobile, autocar, motor car or car is a wheeled motor vehicle used for transporting passengers, which also carries its own engine or motor...
engine
Engine
An engine or motor is a machine designed to convert energy into useful mechanical motion. Heat engines, including internal combustion engines and external combustion engines burn a fuel to create heat which is then used to create motion...
control system is a hard real-time system because a delayed signal may cause engine failure or damage. Other examples of hard real-time embedded systems include medical systems such as heart pacemaker
Artificial pacemaker
A pacemaker is a medical device that uses electrical impulses, delivered by electrodes contacting the heart muscles, to regulate the beating of the heart...
s and industrial process controllers. Hard real-time systems are typically found interacting at a low level with physical hardware, in embedded system
Embedded system
An embedded system is a computer system designed for specific control functions within a larger system. often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal...
s. Early video game systems such as the Atari 2600
Atari 2600
The Atari 2600 is a video game console released in October 1977 by Atari, Inc. It is credited with popularizing the use of microprocessor-based hardware and cartridges containing game code, instead of having non-microprocessor dedicated hardware with all games built in...
and Cinematronics
Cinematronics
Cinematronics Incorporated was a pioneering arcade game developer that had its heyday in the era of vector display games. While other companies released games based on raster displays, early in their history, Cinematronics and Atari released vector-display games, which offered a distinctive look...
vector graphics had hard real-time requirements because of the nature of the graphics and timing hardware.
In the context of multitasking
Computer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...
systems the scheduling policy is normally priority driven (pre-emptive schedulers). Other scheduling algorithms include Earliest Deadline First
Earliest deadline first scheduling
Earliest deadline first or least time to go is a dynamic scheduling algorithm used in real-time operating systems. It places processes in a priority queue. Whenever a scheduling event occurs the queue will be searched for the process closest to its deadline...
, which, ignoring the overhead of context switch
Context switch
A context switch is the computing process of storing and restoring the state of a CPU so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system...
ing, is sufficient for system loads of less than 100%. New overlay scheduling systems, such as an Adaptive Partition Scheduler
Adaptive Partition Scheduler
Adaptive partition schedulers are a relatively new type of partition scheduler, pioneered with the most recent version of the QNX operating system. Adaptive partitioning, or AP, allows the real-time system designer to request that a percentage of processing resources be reserved for a particular...
assist in managing large systems with a mixture of hard real-time and non real-time applications.
Soft real-time systems are typically used where there is some issue of concurrent access and the need to keep a number of connected systems up to date with changing situations; for example software that maintains and updates the flight plans for commercial airline
Airline
An airline provides air transport services for traveling passengers and freight. Airlines lease or own their aircraft with which to supply these services and may form partnerships or alliances with other airlines for mutual benefit...
rs. The flight plans must be kept reasonably current but can operate to a latency of seconds. Live audio-video systems are also usually soft real-time; violation of constraints results in degraded quality, but the system can continue to operate.
Real-time in Digital Signal Processing
In a real-time DSPDigital signal processing
Digital signal processing is concerned with the representation of discrete time signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing...
process, the analyzed (input) and generated (output) samples can be processed (or generated) continuously in the time it takes to input and output the same set of samples independent of the processing delay. It means that the processing delay must be bounded even if the processing continues for an unlimited time. That means that the average processing time per sample is no greater than the sampling period, which is the reciprocal of the sampling rate
Sampling rate
The sampling rate, sample rate, or sampling frequency defines the number of samples per unit of time taken from a continuous signal to make a discrete signal. For time-domain signals, the unit for sampling rate is hertz , sometimes noted as Sa/s...
. This is the criterion whether the samples are grouped together in large segments and processed in blocks or are processed individually and whether there are long, short, or non-existent input and output buffers.
Consider an audio DSP
Audio signal processing
Audio signal processing, sometimes referred to as audio processing, is the intentional alteration of auditory signals, or sound. As audio signals may be electronically represented in either digital or analog format, signal processing may occur in either domain...
example: if a process requires 2.01 seconds to analyze
Audio analysis
Audio analysis refers to the extraction of information and meaning from audio signals for analysis, classification, storage, retrieval, synthesis, etc....
, synthesize, or process 2.00 seconds of sound, it is not real-time. If it takes 1.99 seconds, it is or can be made into, a real-time DSP process.
A common life analog is standing in a line or queue
Queue area
Queue areas are places in which people queue for goods or services. Examples include checking out groceries or other goods that have been collected in a self service shop, in a shop without self service, at an ATM, at a ticket desk, a city bus, or in a taxi stand.Queueing is a phenomenon in a...
waiting for the checkout in a grocery store. If the line asymptotically grows longer and longer without bound, the checkout process is not real-time. If the length of the line is bounded, customers are being "processed" and outputted as rapidly, on average, as they are being inputted and that process is real-time. The grocer might go out of business or must at least lose business if he/she cannot make his/her checkout process real-time (so it's fundamentally important that this process be real-time).
A signal processing algorithm that cannot keep up with the flow of input data with output getting farther and farther behind the input is not real-time. But if the delay is bounded during a process that operates over an unlimited time, then that signal processing algorithm is real-time, even if the throughput delay may be very long.
Real-time and high-performance
Real-time computing is sometimes misunderstood to be high-performance computingHigh-performance computing
High-performance computing uses supercomputers and computer clusters to solve advanced computation problems. Today, computer systems approaching the teraflops-region are counted as HPC-computers.-Overview:...
, but this is not always the case. For example, a massive supercomputer
Supercomputer
A supercomputer is a computer at the frontline of current processing capacity, particularly speed of calculation.Supercomputers are used for highly calculation-intensive tasks such as problems including quantum physics, weather forecasting, climate research, molecular modeling A supercomputer is a...
executing a scientific simulation may offer impressive performance, yet it is not executing a real-time computation. Conversely, once the hardware and software for an anti-lock braking system has been designed to meet its required deadlines, no further performance gains are obligatory. Furthermore, if a network server is highly loaded with network traffic
Network traffic
Network traffic is data in a network. In computer networks, the data is encapsulated in packets.*Network traffic control*Network traffic measurement*Network traffic simulation...
, its response time may be slower but will (in most cases) still succeed before it times out (hits its deadline). Hence, such a network server would not be considered a real-time system: temporal failures (delays, time-outs, etc.) are typically small and compartmentalized (limited in effect) but are not catastrophic failures. In a real-time system, such as the FTSE 100 Index
FTSE 100 Index
The FTSE 100 Index, also called FTSE 100, FTSE, or, informally, the footsie , is a share index of the 100 most highly capitalised UK companies listed on the London Stock Exchange....
, a slow-down beyond limits would often be considered catastrophic in its application context. Therefore, the most important requirement of a real-time system is predictability and not performance.
Some kinds of software, such as many chess-playing programs
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
, can fall into either category. For instance, a chess program designed to play in a tournament with a clock will need to decide on a move before a certain deadline or lose the game, and is therefore a real-time computation, but a chess program that is allowed to run indefinitely before moving is not. In both of these cases, however, high performance is desirable: the more work a tournament chess program can do in the allotted time, the better its moves will be, and the faster an unconstrained chess program runs, the sooner it will be able to move. This example also illustrates the essential difference between real-time computations and other computations: if the tournament chess program does not make a decision about its next move in its allotted time it loses the game—i.e., it fails as a real-time computation—while in the other scenario, meeting the deadline is assumed not to be necessary.
Design methods
Several methods exist to aid the design of real-time systems, an example of which is MASCOTModular Approach to Software Construction Operation and Test
The Modular Approach to Software Construction Operation and Test is a software engineering methodology developed under the auspices of the United Kingdom Ministry of Defence starting in the early 1970s at the Royal Radar Establishment and continuing its evolution over the next twenty years...
, an old but very successful method which represents the concurrent
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
structure of the system. Other examples are HOOD
HOOD method
HOOD is a detailed software design method. It is based on hierarchical decomposition of a software problem...
, Real-Time UML, AADL the Ravenscar profile
Ravenscar profile
The Ravenscar profile is a subset of the Ada tasking features designed for safety-critical hard real-time computing. It was defined by a separate technical report in Ada 95; it is now part of the Ada 2005 Standard.- Restrictions of the profile:...
, Real-Time Java
Real time Java
Real time Java is a catch-all term for a combination of technologies that allows programmers to write programs that meet the demands of Real time systems in the Java programming language....
, WIMS Engine Server (a true-realtime web
Real-time web
The real-time web is a set of technologies and practices that enable users to receive information as soon as it is published by its authors, rather than requiring that they or their software check a source periodically for updates....
implementation).
See also
- Synchronous programming languageSynchronous programming languageA synchronous programming language is a computer programming language optimized for programming reactive systems, systems that are often interrupted and must respond quickly. Many such systems are also called realtime systems, and are found often in embedded uses. The term 'reactive' is chosen to...
- Ptolemy Project
- DSOSDSOSDSOS was a real-time operating system developed by Texas Instruments' Geophysical Services division in the mid-1970s.- Background :...
- Worst-case execution time
Technical committees
Scientific conferences
- ECRTS - Euromicro Conference on Real-time Systems
- IEEE Real-time Systems Symposium
- IEEE Real-time Technology and Applications Symposium
- International Symposium on Object-oriented Real-time distributed Computing
- IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
- Real-Time & Embedded Computing Conference
Journals
Research groups
- CISTER Research Unit, ISEP, Polytechnic Institute of Porto (IPP), Portugal
- Real-Time Systems Research Group,INRIA,LORIA NANCY, France
- Real-Time & Embedded Computing Laboratory (USMAN SHARIF BCS-SP03-37)
- Mälardalen Real-Time research Centre
- Real-Time Computing Laboratory
- Real-Time Systems Laboratory
- RTSE Laboratory
- Institute for Systems Engineering - Real Time systems Group
- Real-Time Systems Laboratory at Scuola Superiore Sant'Anna, Pisa, Italy
- Technical University of Kaiserslautern - Institute for Electrical Engineering and Information Technology - Real-Time Systems Group
- Vienna University of Technology - Institute for Computer Engineering - Real-Time Systems Group
- Real-Time Systems Research Group at the University of York, UK
- Chalmers University of Technology - Dependable Real-Time Systems research group
- ARTES: a national Swedish strategic research initiative in Real-Time Systems supported by the Swedish Foundation for Strategic Research (SSF), SE
- Real-Time Systems at the University of North Carolina at Chapel Hill
- Real-time Systems Laboratory at Virginia Polytechnic and State University, Blacksburg
- mc2labs.com - ICT Research&Development, Mogliano Veneto IT - Realtime Internet programming infrastructures