Restart-based fault-tolerance: System design and schedulability analysis

Fardin Abdi, Renato Mancuso, Rohan Tabish, Marco Caccamo

TL;DR

This paper proposes a novel fault-tolerance mechanism for safety-critical embedded systems that relies on rapid, full-system restarts to recover from software and OS faults. By combining the Simplex Architecture with rigorous schedulability analysis, the authors prove that critical control tasks can safely re-execute and meet their deadlines even if the system reboots mid-operation. They evaluate four scheduling disciplines, showing that limited preemption models offer the best balance between restart overhead and task schedulability.

What Problem Does This Paper Address?

Modern safety-critical cyber-physical systems (CPS)—such as medical devices, avionics, and autonomous vehicles—increasingly rely on complex hardware and software stacks. This includes real-time operating systems (RTOS), multi-core processors, and unverified third-party libraries. Formally verifying this entire stack to guarantee safety is prohibitively expensive, if not impossible.

Consequently, bugs in the OS or complex application layers can cause silent failures or crashes that jeopardize the physical system. Traditional fault tolerance often requires expensive redundant hardware or assumes the underlying OS won't fail. The authors tackle the challenge of guaranteeing physical safety in the presence of unpredictable software faults using only a single processing unit, leveraging the fact that many modern embedded platforms can reboot extremely quickly.

Methods

The authors propose a Restart-Based Recovery (RBR) approach. They structure the software using the Simplex Architecture, dividing control into a formally verified Safety Controller (SC), an unverified Complex Controller (CC), and a verified Decision Module (DM).

To handle faults, they introduce a hardware watchdog timer that monitors the execution of critical tasks. If a task doesn't finish within its "ideal worst-case response time," the watchdog assumes a fault has occurred and triggers a full system restart from a read-only memory image.

To ensure the physical plant remains safe, critical tasks must finish before their deadlines even if a restart occurs. The authors derive exact mathematical response-time equations (RBR-Feasibility) for four fixed-priority scheduling paradigms:

  1. Fully Preemptive: High restart overhead because a restart forces all preempted tasks to re-execute.
  2. Fully Non-Preemptive: Low restart overhead (only the currently running task re-executes) but high blocking times for high-priority tasks.
  3. Non-Preemptive Ending Intervals: Tasks become non-preemptive near completion, reducing wasted execution time if a restart happens late in a task's lifecycle.
  4. Preemption Thresholds: Tasks are assigned a higher priority threshold once they start executing, limiting which tasks can preempt them and shrinking the "preemption chain."

Datasets

The evaluation relies on synthetically generated periodic task sets to test the mathematical schedulability bounds. For each data point in their experiments, 500 task sets were generated with varying CPU utilizations and periods (e.g., diverse periods ranging from 10 to 1000 time units, and uniform periods ranging from 900 to 1000 time units). The authors also mention a proof-of-concept implementation on an i.MX7D platform controlling a 3-DOF helicopter, though the physical flight logs are not the primary focus of the paper's evaluation.

Key Insights and Ideas

  • Restarts as a First-Class Recovery Mechanism: Instead of complex, granular software recovery blocks, a fast, full-system reboot from a read-only image is a highly effective way to clear transient and system-level faults—provided the real-time schedule can absorb the delay.
  • The Preemption Chain Penalty: In fully preemptive systems, a restart at the worst possible time (the end of a long chain of preemptions) forces all partially executed tasks in the chain to start over. This cascading penalty severely limits the system's ability to guarantee deadlines.
  • The Power of Limited Preemption: By tweaking the scheduler to use preemption thresholds or non-preemptive ending intervals, the system drastically reduces the maximum preemption chain length. This provides a "Goldilocks" zone: enough preemption to meet tight deadlines, but enough restriction to keep restart overhead manageable.

Key Results

  • Baseline Feasibility: Under fully preemptive scheduling, almost all task sets with a CPU utilization under 50% remain schedulable (RBR-feasible) even with the overhead of a full system restart.
  • Impact of Task Diversity: When task periods are highly diverse, fully preemptive scheduling outperforms fully non-preemptive scheduling. This is because non-preemptive scheduling suffers from severe blocking (low-priority tasks with long execution times block high-priority tasks with short deadlines).
  • Limited Preemption Wins: Both "preemption thresholds" and "non-preemptive ending intervals" significantly outperformed the fully preemptive and non-preemptive baselines. They maintained high schedulability even as system utilization approached 70-80%.
  • Granularity Matters: For systems with a very small number of tasks (2-10), non-preemptive ending intervals performed slightly better than preemption thresholds due to the finer granularity of tuning time intervals versus discrete priority levels.

Limitations and Future Work

  • Single Fault Assumption: The mathematical analysis assumes only one fault (and thus one restart) occurs per hyper-period of the critical tasks. It does not model fault bursts or cascading hardware failures.
  • Hardware Dependencies: The architecture requires specific hardware support: a reliable external monotonic clock and a transactional Non-Volatile Memory (NVM) block to preserve task completion timestamps across reboots.
  • Uniprocessor Focus: The schedulability analysis is strictly designed for uniprocessor systems. Extending this to multi-core platforms—where inter-core interference and shared resources complicate worst-case execution times and fault isolation—is a necessary and highly challenging future direction.

Summary updated

Abstract

Embedded systems in safety-critical environments are continuously required to deliver more performance and functionality, while expected to provide verified safety guarantees. Nonetheless, platform-wide software verification (required for safety) is often expensive. Therefore, design methods that enable utilization of components such as real-time operating systems (RTOS), without requiring their correctness to guarantee safety, is necessary. In this paper, we propose a design approach to deploy safe-by-design embedded systems. To attain this goal, we rely on a small core of verified software to handle faults in applications and RTOS and recover from them while ensuring that timing constraints of safety-critical tasks are always satisfied. Faults are detected by monitoring the application timing and fault-recovery is achieved via full platform restart and software reload, enabled by the short restart time of embedded systems. Schedulability analysis is used to ensure that the timing constraints of critical plant control tasks are always satisfied in spite of faults and consequent restarts. We derive schedulability results for four restart-tolerant task models. We use a simulator to evaluate and compare the performance of the considered scheduling models.
BibTeX
@inproceedings{abdi2017restart,
  author = {Fardin Abdi and Renato Mancuso and Rohan Tabish and Marco Caccamo},
  title = {{Restart-based fault-tolerance: System design and schedulability analysis}},
  booktitle = {RTCSA},
  year = {2017},
  url = {https://openreview.net/forum?id=d6mjklpwQp},
}

Loading related content...

Figure