TL;DR
This paper introduces a novel approach to scheduling mixed-criticality real-time systems by incorporating probabilistic information about task execution times. This allows for more realistic system certification and improved resource utilization by avoiding overly pessimistic assumptions, leading to a higher acceptance ratio of schedulable task sets compared to existing methods.
What Problem Does This Paper Address?
Safety-critical real-time systems, like those in avionics or automotive, must meet stringent failure probability requirements. Traditional methods for analyzing these systems often rely on pessimistic Worst-Case Execution Time (WCET) estimates, which can lead to over-provisioning of resources and inefficient scheduling. This pessimism arises because precisely determining the absolute WCET for complex software is extremely difficult. Mixed-criticality systems attempt to address this by assigning different importance levels (criticalities) to tasks, allowing lower-criticality tasks to be dropped if higher-criticality tasks exceed their nominal execution times. However, even in mixed-criticality systems, the gap between nominal execution times and actual WCETs can be significant, and existing models often don't fully leverage the probabilistic information available from timing analysis tools. This paper aims to bridge this gap by integrating probabilistic WCET information into the scheduling process, enabling more flexible and efficient scheduling while still meeting safety certification requirements.
Methods
The core contribution of this paper is a new model for mixed-criticality tasks that includes an additional parameter: the probability of a task exceeding its lower-bound WCET (LO-WCET) within a given time interval (e.g., one hour). This probabilistic information is derived from timing analysis tools.
Key methodological aspects include:
- Probabilistic WCET (pWCET) Model: Extending the traditional dual-criticality task model (LO-WCET and HI-WCET) to include a failure probability ($f_i$) for each high-criticality task, representing the likelihood of exceeding its LO-WCET.
- Probabilistic Schedulability: Defining "strongly probabilistic schedulable" (all deadlines met with probability $1-F_s$) and "weakly probabilistic schedulable" (HI-criticality deadlines met with probability $1-F_s$, and no deadlines missed if all jobs meet their LO-WCETs), where $F_s$ is the system-wide permitted failure probability.
- LFF-Clustering Algorithm: A greedy algorithm for uniprocessor scheduling that clusters high-criticality tasks based on their additional utilization costs and failure probabilities. This clustering aims to minimize the total additional utilization cost required to accommodate potential overruns.
- HI-Criticality Server: A mechanism to manage the potential overruns of high-criticality tasks. This server is scheduled alongside other tasks and provides a dedicated "bandwidth" for high-criticality jobs when needed.
- Multiprocessor Scheduling: Extending the uniprocessor approach to multiprocessor platforms using a partitioned scheduling strategy. This involves clustering tasks, allocating clusters to processors, and then applying schedulability tests on each processor.
- Covariance Matrix for Failure Dependencies: Introducing a covariance matrix to model dependencies between tasks' failure probabilities. This allows for more accurate analysis when the failure of one task influences the likelihood of another task failing. A graph-coloring-based approach is used to isolate dependent tasks onto different processors.
Datasets
Not discussed in the paper. The paper focuses on a theoretical model and simulation-based evaluation using randomly generated task sets.
Key Insights and Ideas
- Probabilistic Information is Key: The paper demonstrates that leveraging probabilistic information about WCETs, rather than just worst-case bounds, significantly improves schedulability and resource utilization. This is because it allows for a more nuanced understanding of system behavior under less extreme conditions.
- Avoiding Over-Pessimism: By allowing for a small, acceptable probability of failure ($F_s$), the system can avoid the extreme pessimism of traditional WCET analysis, leading to more efficient scheduling.
- Clustering for Efficiency: The LFF-Clustering algorithm effectively groups high-criticality tasks to manage their potential overruns, reducing the overall resource overhead required.
- Failure Dependencies Matter: Ignoring failure dependencies between tasks can lead to an inaccurate assessment of schedulability. The covariance matrix approach provides a more realistic way to model and handle these dependencies.
- Server-Based Overrun Management: The HI-criticality server provides a flexible mechanism to handle task overruns without necessarily dropping lower-criticality tasks, enhancing system robustness.
Key Results
- Improved Schedulability: For uniprocessor systems, the proposed PMC algorithm achieved a significantly higher acceptance ratio (70.1%) compared to EDF-VD (48.9%) on randomly generated task sets. Even for task sets with high HI-criticality utilization (0.9-1), PMC still outperformed EDF-VD.
- Robustness to $f_i$ Distributions: The algorithm's performance was shown to be robust to different distributions of failure probabilities ($f_i$), indicating its general applicability.
- Multiprocessor Performance: Experiments on multiprocessor platforms showed that the pMCMP algorithm, using various partitioning heuristics (FFD, BFD, WFD), achieved good acceptance ratios, especially when average utilization was lower. The performance generally decreased with increasing utilization and increased with the number of processors.
- Impact of Covariance Density: For multiprocessor systems with failure dependencies, the acceptance ratio decreased as the density of the covariance matrix (representing the number of dependencies) increased, highlighting the challenge of scheduling highly interdependent tasks.
Limitations and Future Work
- Server Period: The current model uses a server with a period of 1 tick. The authors suggest that adaptive servers with dynamic periods or budgets could potentially reduce preemptions.
- Multiple Criticality Levels: The current work focuses on dual-criticality systems. Extending the probabilistic framework to handle multiple criticality levels per task would be a valuable future direction.
- Probabilistic Correctness for Multiple Thresholds: Defining and handling probabilistic correctness for multiple probability thresholds per task is an open research question.
- Real-World Validation: While simulations show promising results, real-world validation on actual hardware platforms would be beneficial.
- Optimality of Heuristics: The paper uses heuristic algorithms (LFF-Clustering, graph coloring) due to the NP-hard nature of the underlying problems. Investigating more optimal or refined heuristics could further improve performance.
Summary updated