Online Adaptive Fault Tolerant based Feedback Control Scheduling Algorithm for Multiprocessor Embedded Systems

This paper proposes a novel online adaptive fault-tolerant feedback control scheduling algorithm designed to optimize resource allocation and ensure deadline adherence for safety-critical tasks in multiprocessor embedded systems amidst dynamic load fluctuations and unpredictable environments.

The Gist

Imagine you are the conductor of a busy orchestra, but instead of violins and drums, your musicians are computer processors, and the music they are playing is a series of urgent tasks. Some of these tasks are "Safety Critical" (like the brakes in a self-driving car), and others are less critical (like playing a background song).

The paper you shared is about a new, smarter way for this conductor to manage the orchestra, especially when things go wrong or when the music gets unexpectedly loud or quiet.

Here is the breakdown of their idea using everyday analogies:

1. The Problem: The "Guessing Game" of Old Scheduling

In the past, computer schedulers worked like a rigid conductor who had a fixed sheet of music. They knew exactly how long every note (task) would take before the concert started. They assumed the musicians would never make mistakes or play slower than expected.

• The Reality: In the real world, computers are unpredictable. Sometimes a task takes longer than planned (like a musician stumbling), or a hardware glitch happens (like a string breaking).
• The Consequence: If the conductor sticks to the rigid plan, the orchestra gets overwhelmed (the CPU gets overloaded), and the most important notes (Safety Critical tasks) get missed.

2. The Solution: The "Feedback Loop" (FCSA)

The authors propose a system called Feedback Control Scheduling (FCSA).

• The Analogy: Imagine a thermostat in your house. It doesn't just guess how hot it should be; it constantly measures the current temperature and adjusts the heater up or down to keep it perfect.
• How it works here: The computer system constantly checks its own "temperature" (how busy the processors are). If it sees the processors are getting too hot (overloaded), it slows down the less important tasks. If they are too cool (underutilized), it speeds things up. This happens automatically and continuously.

3. The Twist: Adding "Fault Tolerance"

The paper adds a special layer: Fault Tolerance. This is like having a backup plan for when a musician actually breaks a string.

• The Challenge: If a processor crashes or a task fails, the system can't just stop. The "Safety Critical" tasks (the brakes) must still work.
• The Strategy: The system uses smart tricks like:
  • Active Replication: Having two musicians play the same part at the same time. If one fails, the other keeps the music going.
  • Re-execution: If a note is played wrong, the musician immediately tries again.
  • Checkpoints: Like pausing a video game to save your progress. If you crash, you don't start from the beginning; you reload from the last save point.

4. The "Brain": Online Adaptive Controller

The most advanced part of this paper is the Online Adaptive Controller.

• The Analogy: Imagine a driver who not only steers the car but also learns how the car handles while driving. If the road gets icy (the system changes), the driver instantly learns, "Oh, I need to brake earlier," and adjusts their driving style immediately.
• The Tech: The authors use a mathematical "brain" (combining a Linear Quadratic controller and a Recursive Least Square estimator) that learns the computer's behavior in real-time. It doesn't need to know the exact speed of every task beforehand; it figures it out as it goes and adjusts the "steering" to keep the system stable.

5. The Experiments: Testing the System

The authors tested their "smart conductor" in three scenarios:

1. The Slow Start: They started with tasks that were much faster than expected. The system gradually sped up the task rates until the processors were perfectly busy (at 81% capacity).
2. The Overload: They started with tasks that were seven times slower than expected (a huge surprise!). The system immediately slowed down the task rates to prevent a crash, eventually stabilizing the load.
3. The Rollercoaster: They suddenly changed the workload in the middle of the test (like a sudden traffic jam). The system adjusted almost instantly, keeping the processors at the perfect speed with very little wobbling.

The Bottom Line

This paper presents a new method for managing complex computer systems that:

1. Self-Corrects: It constantly monitors its own workload and adjusts automatically.
2. Survives Crashes: It has built-in safety nets to ensure critical tasks finish on time, even if parts of the system fail.
3. Learns on the Fly: It doesn't need perfect predictions; it adapts to changes as they happen.

The authors conclude that this approach makes the system much more stable and efficient, ensuring that the "brakes" of the computer system work perfectly even when the "engine" is sputtering or the road conditions change unexpectedly. They note that while the math works well in their tests, putting this into real-world hardware is still a challenge for the future.

Technical Summary

Technical Summary: Online Adaptive Fault Tolerant Based Feedback Control Scheduling Algorithm for Multiprocessor Embedded Systems

Problem Statement
The paper addresses the challenges inherent in the control-scheduling co-design of multiprocessor embedded systems operating in open and unpredictable environments. Traditional scheduling algorithms, such as Rate Monotonic (RM) and Early Deadline First (EDF), rely on open-loop assumptions where task mapping and Worst Case Execution Time (WCET) are predefined. However, in real-world scenarios, execution times for both Safety Critical (SC) and non-SC tasks vary due to environmental uncertainty, leading to potential deadline misses and resource under- or over-utilization. Furthermore, existing Feedback Control Scheduling Algorithms (FCSA) often fail to provide optimal solutions under dynamic load fluctuations, and current Fault Tolerance (FT) designs frequently separate concerns, assuming fixed mappings that do not account for system faults. The authors identify a gap in the literature regarding a unified approach that integrates online adaptation, fault tolerance, and feedback control for multiprocessor systems to ensure Quality of Service (QoS) and deadline adherence.

Methodology
The proposed methodology introduces an Online Adaptive Fault Tolerant Feedback Control Scheduling Algorithm designed for a distributed shared hardware platform. The system architecture consists of multiprocessor nodes where each node contains two cores: one dedicated to SC tasks and the other to non-SC tasks. The scheduling algorithm operates on top of a Real-Time Operating System (RTOS) using fixed-priority pre-emption.

The core of the methodology involves a closed-loop control system with the following components:

1. System Model: The multiprocessor system is modeled as a non-linear, multiple-input-multiple-output (MIMO) system. The control inputs are the task periods (sampling rates), and the output variable is the measured CPU utilization.
2. Controller Design: The authors employ an Online Adaptive Controller comprising two main elements:
   • Recursive Least Squares (RLS) Model Estimator: This component uses an exponential forgetting factor to identify time-varying parameters of the system model online. It updates the model coefficients to adapt to changing runtime conditions and execution time deviations.
   • Linear Quadratic (LQ) Optimal Controller: This controller minimizes a quadratic cost function to track a reference command (desired CPU utilization) while penalizing large changes in control inputs. The cost function balances tracking accuracy against the magnitude of control adjustments.
3. Fault Tolerance Integration: The design incorporates fault tolerance mechanisms (such as active replication, re-execution, or checkpointing concepts mentioned in the background) to ensure that SC tasks meet deadlines even in the presence of transient or permanent faults. The controller aims to maintain CPU utilization within a schedulable bound despite these faults.

Key Contributions

• Novel Integration: The paper presents a methodology that integrates online adaptation, fault tolerance, and feedback control scheduling specifically for multiprocessor embedded systems, claiming this is the first work to address these three elements together in this context.
• Adaptive Mechanism: Unlike static or non-adaptive FCSA designs, the proposed algorithm utilizes an RLS-based estimator to dynamically update the system model, allowing it to handle dynamic load fluctuations and execution time variations without prior knowledge of actual task execution times.
• Robust Control Strategy: The use of an LQ controller allows for the optimization of CPU performance and resource utilization by keeping the system at a desired utilization set point, thereby avoiding overloading and minimizing deadline miss ratios.

Experimental Results
The authors validated the methodology through three experiments focusing on CPU utilization control:

1. Under-utilization Scenario: Starting with actual execution times at 30% of estimated values (under-utilized), the controller successfully increased task rates, converging the CPU utilization of both processors to the desired set point of 0.8123.
2. Over-utilization Scenario: With actual execution times set to seven times the estimated values (severe over-utilization), the controller decreased task rates. Despite initial oscillations caused by model estimation inaccuracies, the system quickly converged to the 0.8123 set point.
3. Robustness to Dynamic Loads: The system was subjected to dynamic workload changes at specific intervals (300th, 400th, and 800th sample steps). The online adaptive controller maintained the utilization at the set point with minimal oscillation, demonstrating robustness against sudden load fluctuations.

The results indicate that the system remains stable even when actual execution times are significantly higher than estimates (up to a factor of 7), provided the tasks meet their deadlines. However, the authors note that if execution times exceed this threshold, the system becomes unstable, leading to oscillations and deadline misses.

Significance and Claims
The paper claims that the proposed methodology offers a superior approach for control-scheduling co-design in multiprocessor embedded systems by providing QoS in terms of CPU performance and resource utilization. The significance lies in the ability to maintain system stability and meet deadlines for Safety Critical tasks in the presence of faults and dynamic load changes, which traditional open-loop or non-adaptive feedback methods struggle to achieve.

The authors conclude that while the system demonstrates improved stability and resource usage, the practical implementation of such feedback scheduling-based control systems remains an "almost completely open issue." They suggest that future work could focus on developing more advanced CPU utilization models and hybrid online controllers to further enhance overall system performance. The paper does not claim to solve all real-time scheduling problems but positions its adaptive, fault-tolerant approach as a significant step forward in handling the uncertainties of modern embedded environments.