Real-Time Scheduling
Hard vs Soft Real-Time
Read aloud is unavailable in this browser.
When Timing Is Everything
In conventional computing, we measure success primarily by correctness—did the program produce the right answer? But for an entire class of systems, correctness is necessary but insufficient. These systems must also satisfy timing constraints: producing the right answer, but on time.
Consider an airbag deployment system in a vehicle. It must detect a collision, calculate the deployment angle, and trigger the airbag—all within approximately 15-30 milliseconds from impact. A correct decision arriving at 50 milliseconds is not merely suboptimal; it is catastrophically useless. The occupant has already impacted the steering wheel.
This is the domain of real-time systems: computing environments where temporal correctness is as critical as logical correctness. Understanding the distinction between hard and soft real-time requirements is fundamental to designing, implementing, and scheduling these systems correctly.
By the end of this page, you will be able to: (1) Precisely define and differentiate hard and soft real-time systems; (2) Analyze the consequences of deadline misses in each category; (3) Identify real-world examples across the hard-soft spectrum; (4) Understand the implications for scheduler design and system architecture; (5) Recognize firm real-time as an intermediate category.
Defining Real-Time Systems
A real-time system is a computing system in which the correctness of the system behavior depends not only on the logical results of computations, but also on the physical time at which the results are produced. This definition, attributed to John Stankovic's seminal work in real-time computing, captures the essence of temporal correctness.
Crucial distinction from general-purpose systems:
In a general-purpose operating system (like desktop Linux or Windows), faster is always better, but there's no absolute requirement for when a task must complete. If your word processor takes 200ms instead of 100ms to respond to a keystroke, the user experience degrades, but the system remains functionally correct.
In a real-time system, the deadline is a first-class constraint. Tasks are characterized not just by their computational requirements, but by:
- Arrival time (aᵢ): When the task becomes ready for execution
- Execution time (Cᵢ): Worst-case CPU time required to complete
- Deadline (dᵢ): The absolute time by which the task must complete
- Period (Tᵢ): For periodic tasks, the interval between successive arrivals
A common misconception is that real-time means 'very fast.' This is incorrect. A real-time system could have deadlines of hours or days. What matters is that the deadlines are predictable and guaranteed. A 10-hour response is real-time if the deadline is 12 hours. A 100-microsecond response is not real-time if the deadline was 50 microseconds.
The temporal correctness requirement:
Let τᵢ denote task i, with arrival time aᵢ, execution time Cᵢ, and deadline dᵢ. Let fᵢ denote the actual finishing time of task i. The temporal correctness requirement is:
$$f_i \leq d_i \quad \text{for all tasks } \tau_i$$
When this condition is violated—when fᵢ > dᵢ—we have a deadline miss. The consequences of this miss determine whether the system is classified as hard or soft real-time.
Hard Real-Time Systems
A hard real-time system is one in which missing a deadline constitutes a system failure. The value of the result produced after the deadline is not merely diminished—it is zero or negative. The computation becomes useless or actively harmful.
Formal definition:
The utility function U(t) for a hard real-time task takes the form:
U(t) = {
V if t ≤ deadline
−∞ if t > deadline
}
Where V is the value of the completed task. After the deadline, the utility crashes to negative infinity, representing catastrophic failure.
Characteristics of hard real-time systems:
- •Deadline misses are catastrophic — A single missed deadline can result in loss of life, destruction of equipment, mission failure, or environmental disaster. There is no acceptable rate of deadline misses.
- •Worst-case execution time (WCET) analysis is mandatory — The system must guarantee that tasks always complete before their deadlines, even under worst-case conditions. Average-case analysis is insufficient.
- •Deterministic behavior is required — The system must be fully predictable. Non-deterministic elements (unbounded loops, dynamic memory allocation, garbage collection) are typically prohibited or heavily constrained.
- •Certification and formal verification — Hard real-time systems often require formal proofs of correctness and timing guarantees, especially in safety-critical industries (aerospace, medical devices, nuclear).
- •Resource over-provisioning — To guarantee worst-case performance, hard real-time systems are typically designed with significant safety margins, often utilizing only 40-70% of theoretical CPU capacity.
Canonical examples of hard real-time systems:
1. Flight Control Systems (Fly-by-Wire)
Modern aircraft rely on computer systems to translate pilot inputs into control surface movements. The Boeing 777 and Airbus A380 use quadruple-redundant flight control computers with hard real-time constraints. If the system fails to compute and apply the correct control inputs within milliseconds, the aircraft's stability is compromised. The DO-178C standard governs software development for airborne systems, requiring exhaustive testing and formal verification.
2. Antilock Braking Systems (ABS)
ABS controllers must process wheel speed sensor data and modulate brake pressure at frequencies of 10-20 Hz (cycles every 50-100ms). If the controller misses a deadline, the wheels can lock, leading to loss of steering control. Modern ABS systems achieve deadline compliance rates of 100%—any less is a design failure.
3. Cardiac Pacemakers
Implanted pacemakers must deliver electrical stimulation to the heart at precisely timed intervals. A missed deadline in sensing or pacing could trigger arrhythmias or fail to prevent cardiac arrest. These devices undergo FDA Class III certification, the most stringent regulatory category.
4. Nuclear Reactor Control Systems
SCADA (Supervisory Control and Data Acquisition) systems in nuclear plants monitor thousands of sensors and control coolant flow, control rod positions, and emergency shutdown sequences. A delayed response to a coolant temperature spike could initiate a meltdown scenario.
The Therac-25 radiation therapy machine killed three patients in the 1980s due to race conditions and timing errors in its software. A hard real-time constraint—ensuring the radiation beam configuration matched the selected dose—was not properly enforced. This case study remains a cautionary tale in real-time systems engineering.
Soft Real-Time Systems
A soft real-time system is one in which deadline misses are undesirable but tolerable. The value of a late result degrades gracefully rather than becoming worthless. The system continues to function, albeit with reduced quality or performance.
Formal definition:
The utility function U(t) for a soft real-time task takes the form:
U(t) = {
V if t ≤ deadline
V × decay(t - deadline) if t > deadline
}
Where decay() is a monotonically decreasing function (linear, exponential, or step-wise) representing the diminishing value of late results.
Characteristics of soft real-time systems:
- •Deadline misses degrade quality, not correctness — Late results still have value, though diminished. The system doesn't fail catastrophically; it delivers reduced service quality.
- •Statistical guarantees are acceptable — Rather than 100% deadline compliance, soft real-time systems target high percentages (e.g., 95% or 99% of deadlines met). Average-case performance matters.
- •Quality of Service (QoS) metrics apply — Latency percentiles (p50, p95, p99), jitter (variance in response times), and throughput under load define the performance contract.
- •Adaptive behaviors are common — Soft real-time systems can adjust frame rates, reduce audio quality, or skip computations when overloaded—trading fidelity for timeliness.
- •Standard OS primitives may suffice — Unlike hard real-time, soft real-time constraints can often be met using standard operating systems with appropriate tuning (real-time scheduling classes, priority adjustments).
Canonical examples of soft real-time systems:
1. Video Streaming and Playback
Netflix or YouTube must decode and render video frames at 24-60 frames per second. If a frame misses its deadline, the system can skip the frame, repeat the previous frame, or interpolate. Viewers perceive a stutter or quality drop, but playback continues. Target: 99%+ frames on time.
2. Video Conferencing (Zoom, Teams)
Audio and video streams have latency budgets of 150-400ms for acceptable conversation quality. Occasional frame drops or audio glitches are tolerable; sustained degradation makes conversation difficult but doesn't break the system. Adaptive bitrate and frame rate adjustments handle overload.
3. Online Gaming
Multiplayer games target 16-33ms frame times (60-30 FPS) for input responsiveness. Server tick rates of 64-128 Hz provide game state updates. Late updates cause 'rubber-banding' or lag, frustrating players but not disabling the game. Competitive players are extremely sensitive to latency spikes.
4. GPS Navigation
Consumer GPS devices update position every 1 second. Occasional late or missed updates result in momentary position uncertainty or delayed turn announcements. The driver may miss a turn but won't crash due to a late GPS fix.
| System | Deadline Miss Consequence | Mitigation Strategy |
|---|---|---|
| Video Playback | Frame stutter, artifacts | Frame skipping, buffer management |
| Audio Streaming | Clicks, pops, gaps | Buffer depth, adaptive bitrate |
| Online Gaming | Lag, rubber-banding | Interpolation, prediction |
| Web Servers | Slow page loads, timeouts | Request timeouts, load shedding |
| Sensor Networks | Stale data, missed readings | Interpolation, redundancy |
Firm Real-Time: The Middle Ground
Between hard and soft real-time lies a less commonly discussed but important category: firm real-time. In firm real-time systems, missing a deadline renders the result worthless (like hard real-time), but the overall system doesn't fail catastrophically (like soft real-time).
Formal definition:
The utility function U(t) for a firm real-time task takes the form:
U(t) = {
V if t ≤ deadline
0 if t > deadline
}
The late result has zero value, but not negative value. The system can continue operating, potentially with degraded output quality.
In hard real-time, a missed deadline is a system failure (the airbag doesn't deploy, the plane crashes). In firm real-time, a missed deadline is a task failure (this video frame is worthless, but the video keeps playing). The distinction lies in whether the overall system continues functioning.
Examples of firm real-time systems:
1. Financial Trading Systems
High-frequency trading algorithms must respond to market data within microseconds. A trading decision delayed past the market opportunity window is worthless—the price has moved, the opportunity is gone. However, missing one trade doesn't crash the trading system; it proceeds to the next opportunity.
2. Automated Manufacturing
A robotic assembly line must complete operations within the conveyor belt cycle time. If a robot misses its window, that specific part passes by unprocessed. The part is rejected (zero value for that task), but the line continues operating.
3. Sensor Data in Scientific Experiments
A particle physics detector must capture and timestamp events during a collision. Data arriving after the analysis window cannot be correlated and is discarded. The experiment continues, but that data point is lost.
Implications for scheduling:
Firm real-time systems often employ skip scheduling or overload management strategies. Since late tasks have zero value, it's better to drop a task entirely (saving the resources) than to complete it late. This informs algorithms like earliest-deadline-first with rejection.
Comparative Analysis
To solidify understanding, let's directly compare hard, firm, and soft real-time across multiple dimensions:
| Attribute | Hard Real-Time | Firm Real-Time | Soft Real-Time |
|---|---|---|---|
| Deadline miss consequence | System failure | Task worthless | Task degraded |
| Utility after deadline | Negative (harmful) | Zero (useless) | Positive (diminished) |
| Acceptable miss rate | 0% | Low % | Moderate % |
| Analysis approach | Worst-case (WCET) | Worst-case + rejection | Average-case + percentiles |
| Example domain | Aerospace, medical | Trading, manufacturing | Multimedia, gaming |
| Failure mode | Catastrophic | Localized loss | Graceful degradation |
| OS requirements | RTOS mandatory | RTOS or tuned GPOS | Standard GPOS often sufficient |
| Certification | Formal verification | Often required | Rarely required |
The spectrum view:
Rather than discrete categories, real-time requirements exist on a spectrum. Some systems have components in multiple categories:
- Aircraft flight control: Primary flight surfaces are hard real-time; cabin entertainment is soft real-time.
- Autonomous vehicles: Collision avoidance is hard real-time; route planning is soft real-time.
- Medical monitoring: Alarm detection is hard real-time; trend display is soft real-time.
Understanding this spectrum helps architects isolate safety-critical components and allocate resources appropriately.
Treating a hard real-time requirement as soft can be fatal—literally. Treating a soft requirement as hard wastes resources and increases system cost. Proper classification during requirements analysis is essential. Err on the side of caution for safety-critical functions.
Implications for Scheduler Design
The hard/soft distinction profoundly impacts how scheduling algorithms are designed, analyzed, and implemented.
- •Deterministic guarantees — The scheduler must prove that all deadlines will be met under worst-case conditions.
- •Admission control — Before accepting a new task, verify that adding it won't cause any existing task to miss its deadline.
- •WCET-based analysis — All timing calculations use worst-case execution times, not averages.
- •Bounded preemption — Context switch overhead must be known and bounded.
- •No unbounded priority inversion — Priority inheritance or priority ceiling protocols are mandatory.
- •Probabilistic guarantees — Target p99 latency or percentage of deadlines met, not absolute guarantees.
- •Best-effort with priorities — Prefer meeting deadlines but gracefully degrade under overload.
- •Average-case optimization — Optimize for common-case performance; worst-case is secondary.
- •Fairness considerations — Balance responsiveness across multiple applications and users.
- •Adaptive behavior — Dynamically adjust based on load, possibly missing some deadlines to meet others.
Operating system implications:
Real-Time Operating Systems (RTOS) like VxWorks, QNX, FreeRTOS, and RTEMS are designed specifically for hard real-time requirements. They provide:
- Deterministic scheduling with bounded latencies
- Fine-grained priority control (often 256+ priority levels)
- Priority inheritance protocols built into mutexes
- Minimal interrupt latency (guaranteed worst-case)
- Minimal OS kernel footprint
General-Purpose Operating Systems (GPOS) like Linux and Windows are designed for soft real-time at best. However, modifications exist:
- Linux PREEMPT_RT patch: Adds full kernel preemption, converting Linux from soft to near-hard real-time
- Windows Multimedia Class Scheduler Service (MMCSS): Provides priority boost for multimedia applications
- Linux SCHED_DEADLINE: Earliest deadline first scheduling class for periodic tasks
The choice of OS is an architectural decision driven by real-time requirements.
Practical Classification Guidelines
When designing or analyzing a real-time system, use these questions to classify timing requirements:
Decision Framework for Real-Time Classification
- •What happens if the deadline is missed once? — Loss of life/equipment → Hard. Lost revenue/opportunity → Firm. User annoyance → Soft.
- •What happens if the deadline is missed repeatedly? — Even soft systems become firm/hard if miss rates exceed thresholds.
- •Is the system safety-critical? — Any safety function (collision avoidance, medical monitoring, industrial safety) defaults to hard real-time.
- •What is the economic impact of misses? — High-frequency trading losing millions per microsecond delay justifies hard real-time investment.
- •What regulatory standards apply? — DO-178C (aviation), IEC 62304 (medical), ISO 26262 (automotive) imply hard real-time requirements.
- •Can the system degrade gracefully? — If frame dropping, quality reduction, or retry are acceptable, soft real-time may apply.
Many systems implement defense in depth: a hard real-time safety monitor watches over a soft real-time main controller. If the main controller misses deadlines, the safety monitor triggers a safe fallback. This allows the flexibility of soft real-time for normal operation with the guarantees of hard real-time for emergencies.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.