Editing Real-time computing (section)

== {{anchor|Hard|Firm|Require|Soft}}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.<ref>{{cite journal | last1 = Shin | first1 = Kang G. |author-link=Kang G. Shin | last2 = Ramanathan | first2 = Parameswaran | title = Real-time computing: a new discipline of computer science and engineering | journal = Proceedings of the IEEE | volume = 82 | issue = 1 | pages = 6–24 | date = Jan 1994 | issn = 0018-9219 | doi = 10.1109/5.259423| url = http://kabru.eecs.umich.edu/papers/publications/1994/ramanathan-shin-ieee-proceedings.pdf | citeseerx = 10.1.1.252.3947 }}</ref> Real-time systems, as well as their deadlines, are classified by the consequence of missing a deadline:<ref>Kopetz, Hermann; ''Real-Time Systems: Design Principles for Distributed Embedded Applications'', Kluwer Academic Publishers, 1997</ref>
* ''Hard''{{snd}} missing a deadline is a total system failure.
* ''Firm''{{snd}} 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''{{snd}} 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 depend 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). Some examples of hard real-time systems:
* A [[automobile|car]] [[internal combustion engine|engine]] control system is a hard real-time system because a delayed signal may cause engine failure or damage.
* Medical systems such as heart [[artificial pacemaker|pacemaker]]s. Even though a pacemaker's task is simple, because of the potential risk to human life, medical systems like these are typically required to undergo thorough testing and certification, which in turn requires hard real-time computing in order to offer provable guarantees that a failure is unlikely or impossible.
* Industrial process controllers, such as a machine on an [[assembly line]]. If the machine is delayed, the item on the assembly line could pass beyond the reach of the machine (leaving the product untouched), or the machine or the product could be damaged by activating the robot at the wrong time. If the failure is detected, both cases would lead to the assembly line stopping, which slows production. If the failure is not detected, a product with a defect could make it through production, or could cause damage in later steps of production.
* 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.
* [[Softmodem]]s replace a hardware modem with software running on a computer's [[Central processing unit|CPU]]. The software must run every few milliseconds to generate the next audio data to be output. If that data is late, the receiving modem will lose synchronization, causing a long interruption as synchronization is reestablished or causing the connection to be lost entirely.
* Many types of [[Printer (computing)|printers]] have hard real-time requirements, such as [[inkjet]]s (the ink must be deposited at the correct time as the printhead crosses the page), [[laser printer]]s (the laser must be activated at the right time as the beam scans across the rotating drum), and dot matrix and various types of [[line printer]]s (the impact mechanism must be activated at the right time as the print mechanism comes into alignment with the desired output). A failure in any of these would cause either missing output or misaligned output.

In the context of [[Computer multitasking|multitasking]] systems the [[scheduling policy]] is normally priority driven ([[Preemptive multitasking|pre-emptive]] schedulers). In some situations, these can guarantee hard real-time performance (for instance if the set of tasks and their priorities is known in advance). There are other hard real-time schedulers such as [[Rate-monotonic scheduling|rate-monotonic]] which is not common in general-purpose systems, as it requires additional information in order to schedule a task: namely a bound or worst-case estimate for how long the task must execute. Specific algorithms for scheduling such hard real-time tasks exist, like [[Earliest deadline first scheduling|earliest deadline first]], which, ignoring the overhead of [[context switch]]ing, is sufficient for system loads of less than 100%.<ref>Liu, Chang L.; and Layland, James W.; "Scheduling Algorithms for Multiprogramming in a Hard Real-time Environment", ''Journal of the ACM'', 20(1):46-61, January 1973, http://citeseer.ist.psu.edu/liu73scheduling.html</ref> 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.

'''Firm real-time systems''' are more nebulously defined, and some classifications do not include them, distinguishing only hard and soft real-time systems. Some examples of firm real-time systems:
* The assembly line machine described earlier as ''hard'' real-time could instead be considered ''firm'' real-time. A missed deadline still causes an error which needs to be dealt with: there might be machinery to mark a part as bad or eject it from the assembly line, or the assembly line could be stopped so an operator can correct the problem. However, as long as these errors are infrequent, they may be tolerated.

'''Soft real-time systems''' are typically used to solve issues of concurrent access and the need to keep a number of connected systems up-to-date through changing situations. Some examples of soft real-time systems:
* Software that maintains and updates the flight plans for commercial [[airline]]rs. The flight plans must be kept reasonably current, but they can operate with the latency of a few seconds.
* Live audio-video systems are also usually soft real-time. A frame of audio which is played late may cause a brief audio glitch (and may cause all subsequent audio to be delayed correspondingly, causing a perception that the audio is being played slower than normal), but this may be better than the alternatives of continuing to play silence, static, a previous audio frame, or estimated data. A frame of video that is delayed typically causes even less disruption for viewers. The system can continue to operate and also recover in the future using workload prediction and reconfiguration methodologies.<ref>{{cite journal | title = Real-time reconfiguration for guaranteeing QoS provisioning levels in Grid environments | journal = Future Generation Computer Systems | volume = 25 | issue = 7 | pages = 779–784 | date = July 2009 | doi = 10.1016/j.future.2008.11.001| last1 = Menychtas | first1 = Andreas | last2 = Kyriazis | first2 = Dimosthenis | last3 = Tserpes | first3 = Konstantinos }}</ref>
* Similarly, video games are often soft real-time, particularly as they try to meet a target [[frame rate]]. As the next image cannot be computed in advance, since it depends on inputs from the player, only a short time is available to perform all the computing needed to generate a frame of video before that frame must be displayed. If the deadline is missed, the game can continue at a lower frame rate; depending on the game, this may only affect its graphics (while the gameplay continues at normal speed), or the gameplay itself may be slowed down (which was common on older [[Third generation of video game consoles|third-]] and [[Fourth generation of video game consoles|fourth-generation consoles]]).

=== Real-time in digital signal processing ===
In a real-time [[digital signal processing]] (DSP) 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.<ref name="Kuo-Lee-Tian">Kuo, Sen M.; Lee, Bob H.; and Tian, Wenshun; "Real-Time Digital Signal Processing: Implementations and Applications", Wiley, 2006, {{ISBN|0-470-01495-4}}, [http://media.wiley.com/product_data/excerpt/54/04700149/0470014954.pdf Section 1.3.4: ''Real-Time Constraints''].</ref> It means that the processing delay must be bounded even if the processing continues for an unlimited time. The [[arithmetic mean|mean]] processing time per sample, including [[Overhead (computing)|overhead]], 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 as blocks or are processed individually and whether there are long, short, or non-existent [[data buffer|input and output buffers]].

Consider an [[Audio signal processing|audio DSP]] example; if a process requires 2.01 seconds to [[Audio analysis|analyze]], [[Sound synthesis|synthesize]], or process 2.00 seconds of sound, it is not real-time. However, if it takes 1.99 seconds, it is or can be made into a real-time DSP process.

A common life analogy is standing in a line or [[Queue area|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 output as rapidly, on average, as they are being inputted then that process ''is'' real-time. The grocer might go out of business or must at least lose business if they cannot make their checkout process real-time; thus, it is fundamentally important that this process is real-time.

A signal processing algorithm that cannot keep up with the flow of input data with output falling further and further behind the input, is not real-time. If the delay of the output (relative to the input) is bounded regarding a process which operates over an unlimited time, then that signal processing algorithm is real-time, even if the throughput delay may be very long.

==== Live vs. real-time ====

Real-time signal processing is necessary, but not sufficient in and of itself, for live signal processing such as what is required in [[live event support]]. Live audio digital signal processing requires both real-time operation and a sufficient limit to throughput delay so as to be tolerable to performers using [[stage monitor]]s or [[in-ear monitor]]s and not noticeable as [[lip sync error]] by the audience also directly watching the performers. Tolerable limits to latency for live, real-time processing is a subject of investigation and debate, but is estimated to be between 6 and 20 milliseconds.<ref>{{cite journal|last1=Kudrle|first1=Sara|last2=Proulx|first2=Michel|last3=Carrieres|first3=Pascal|last4=Lopez|first4=Marco|title=Fingerprinting for Solving A/V Synchronization Issues within Broadcast Environments|journal=SMPTE Motion Imaging Journal|date=July 2011|volume=120|issue=5|pages=36–46|doi=10.5594/j18059XY|quote=Appropriate A/V sync limits have been established and the range that is considered acceptable for film is +/- 22 ms. The range for video, according to the ATSC, is up to 15 ms lead time and about 45 ms lag time|display-authors=etal}}</ref>

Real-time bidirectional [[G.114|telecommunications delays]] of less than 300 ms ("round trip" or twice the unidirectional delay) are considered "acceptable" to avoid undesired "talk-over" in conversation.