Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors

Real-time systems are essential to modern safety-critical applications, such as autonomous driving, avionics, and industrial robotics [11]. These systems are characterized by a tight interaction with the physical world, where the correctness of an operation depends not only on the logical result but also on the time at which that result is produced. Consequently, these systems demand an exceptionally high level of reliability and predictability, as a single timing failure can lead to catastrophic consequences. To enforce this high reliability, international safety standards, for instance, ISO 26262 for the automotive industry, provide a rigorous framework for development and validation. These standards often require system designers to demonstrate that the probability of timing failures, such as deadline misses, remains below a strictly defined, small threshold [10]. To provide such assurance, schedulability analysis, which mathematically proves that timing constraints are met with a required level of assurance ranging from deterministic guarantees to probabilistic bounds, is of paramount importance.

The software architecture of contemporary real-time systems, particularly in the autonomous driving domain, is growing in complexity. Applications are no longer simple, sequential programs but are composed of multiple concurrent functions with intricate data dependencies, often modeled as Directed Acyclic Graph (DAG) tasks to capture internal parallelism and precedence constraints [17]. Furthermore, to reduce size, weight, power, and cost, integrating functionalities of varying degrees of importance onto a common multiprocessor platform has become common practice. This integration leads to a Mixed-Criticality System (MCS), where safety-critical functions (e.g., collision avoidance) coexist with non-critical ones (e.g., infotainment) [18, 3]. The confluence of these characteristics of parallelism, mixed-criticality, and multiprocessor platforms presents a significant challenge. Ensuring the safety and reliability of these integrated systems requires a sophisticated and rigorous schedulability analysis specifically tailored for mixed-criticality DAG tasks on multiprocessors.

A fundamental challenge in conventional schedulability analysis lies in the reliance on the Worst-Case Execution Time (WCET) to model task behavior. WCET analysis tools aim to provide an absolute upper bound on the execution time of a task, but to provide this upper bound, these tools must account for a vast number of unlikely, pathological scenarios, such as worst-case cache behavior and pipeline hazards [19, 1]. This approach inevitably results in a highly pessimistic estimation of the required computational resources. Such pessimism in WCET-based analysis forces significant over-provisioning of hardware, leading to inefficient resource utilization and increased system cost. In response to this problem, a trend has emerged to incorporate probabilistic approaches into schedulability analysis to mitigate pessimism, for example, by using probabilistic WCETs (pWCETs) [8, 5, 2]. However, while these methods have shown promise for simpler models, such as sequential or sporadic tasks, their application to the more complex domain of mixed-criticality DAG tasks on multiprocessor systems remains largely unexplored. This gap stems from the need to account for (i) internal parallelism and precedence constraints and (ii) mixed-criticality mode changes, both of which complicate probabilistic bounding of concurrent overruns on multiprocessors.

Based on these challenges, this work investigates the following research questions.

• $\mathrm{■}$

  RQ1 (Core demand reduction): Under a system-level bound on the probability of deadline misses of HI-criticality tasks over a bounded time horizon (e.g., one hour of operation), how much can the required number of processor cores be reduced compared to deterministic WCET-based analysis?

• $\mathrm{■}$

  RQ2 (Sensitivity to failure budget): How does the permitted system-level failure probability, i.e., the probability that any HI-criticality task misses a deadline within the operational window, affect the required number of cores, and at what point does further relaxation yield diminishing returns?

• $\mathrm{■}$

  RQ3 (Scalability): Can such a probabilistic analysis be performed at practical computational cost for large task sets and large DAGs?

To answer these questions, this paper proposes a probabilistic schedulability analysis for mixed-criticality DAG tasks on multiprocessor platforms. Instead of modeling each task by a single WCET, the proposed method assigns each vertex a LO-level budget, i.e., a nominal execution-time budget expected to be met in typical runs, and a small probability of exceeding that budget (an overrun). Conventional deterministic analysis is pessimistic because such analysis effectively assumes that many vertices exceed their budgets at the same time, an event that is extremely rare in practice. In contrast, the proposed analysis exploits the rarity of multiple simultaneous overruns to reduce the required resources, while ensuring a designer-specified bound on the probability of deadline misses of HI-criticality tasks over the time horizon. The analysis adopts federated scheduling, which isolates high-utilization DAGs on dedicated cores, eliminating inter-task interference and making the per-task analysis tractable. Within each DAG, vertices are aggregated into small connected groups; because simultaneous overruns of multiple vertices in the same group are rare, each group can be assigned a tighter execution-time bound than the sum of individual WCETs. Each group is collapsed into one vertex to form a reduced DAG, enabling existing response-time bounds.

The contributions of this paper, which address RQ1–RQ3, are as follows:

• $\mathrm{■}$

  Probabilistic analysis framework (RQ1): A probabilistic schedulability analysis for mixed-criticality DAG tasks under federated scheduling that reduces required cores while maintaining a system-level failure guarantee, combining (i) probabilistic vertex grouping and (ii) existing response-time bounds on the reduced DAG.

• $\mathrm{■}$

  Optimization for resource efficiency (RQ1, RQ2): A grouping optimization formulation and a simulated-annealing-based search procedure that minimizes required cores while satisfying per-cluster failure constraints, enabling quantitative evaluation of how the system-level failure budget affects resource demand.

• $\mathrm{■}$

  Evaluation of effectiveness and scalability (RQ1, RQ2, RQ3): An evaluation comparing against deterministic baselines, characterizing strengths and limitations across task settings, and reporting computational scalability across task-set and DAG sizes.

The remainder of this paper is structured as follows. Section 2 defines the system model, including the mixed-criticality DAG task model and the probabilistic execution model. Section 3 presents the task classification scheme and design policy. Section 4 describes the probabilistic clustering scheme and multipath-based response time analysis. Section 5 details the simulated annealing optimization algorithm. Section 6 provides an experimental evaluation comparing the proposed method against existing approaches. Section 7 surveys related work in mixed-criticality scheduling and probabilistic timing analysis. Finally, Section 8 concludes the paper and outlines directions for future research.

The formal models and assumptions used throughout this paper are detailed below. The platform and the structure of the mixed-criticality parallel tasks are defined first. Subsequently, the probabilistic execution model that forms the basis of the schedulability analysis is introduced. An overview of the system model is illustrated in Figure 1. A summary of the symbols used to define the system is provided in Table 1.

The proposed probabilistic schedulability analysis framework is presented below. The key insight is that conventional mixed-criticality analysis tends to be overly pessimistic. Deterministic approaches treat the LO-mode and HI-mode separately and assume that, once the system enters HI-mode, every HI-criticality task could simultaneously require execution up to its HI-level WCET. In practice, however, the probability that any single task exceeds its LO-level budget is already very small, so requiring resources for the simultaneous worst-case execution of all HI-criticality tasks leads to significant over-provisioning. By leveraging the system-level permitted failure probability $F_S$ defined over an operational window of length $W$ (e.g., one hour), the proposed method rules out such extremely rare scenarios and reduces the required number of processor cores.

Throughout this section, implicit-deadline sporadic DAG tasks are considered, where $D_i=T_i$ for all tasks ${\tau }_i$. The proposed method follows the federated scheduling paradigm [15], which partitions tasks based on their resource requirements.

Similarly, define the LO-level utilization as $u_i^L\triangleq C_i^L/T_i$, where $C_i^L={\sum }_{v\in V_i}{c}_v^L$ is the sum of the LO-level execution times of all vertices in DAG ${\tau }_i$. For LO-criticality tasks without HI-level parameters, $u_i^L$ is used for utilization-based classification.

Intuitively, a high-utilization DAG cannot complete within its deadline on a single processor even under ideal work-conserving execution; thus, such a DAG requires multiple dedicated processors. Low-utilization tasks satisfy $u_i^H\le 1$ and can be handled using partitioned scheduling as sequential tasks.

The proposed framework consists of the following components. For high-utilization DAG tasks, vertices are grouped into small clusters. Because simultaneous overruns of multiple vertices within the same cluster are statistically rare, each cluster can be assigned a combined execution budget smaller than the sum of individual HI-level budgets, reducing the total work that must be provisioned and lowering the required number of cores. A response-time bound is then computed on the reduced DAG in which each cluster is contracted into a single vertex. For low-utilization tasks, each DAG is conservatively abstracted as a sequential sporadic task with execution time equal to its total work $C_i$, enabling reuse of MC-Partition [12] for this subset. MC-Partition receives $(C_i^L,C_i^H,T_i=D_i)$ for HI-critical tasks and $(C_i^L,T_i=D_i)$ for LO-critical tasks (HI-level parameters are not defined for LO-critical tasks). Because MC-Partition guarantees schedulability using the HI-level execution times, low-utilization tasks always meet their deadlines regardless of whether any overrun occurs; thus, these tasks do not consume the probabilistic failure budget. The system-level failure budget $F_S$ is therefore enforced only for the probabilistic analysis of high-utilization HI-criticality DAGs.

The proposed method differs from prior federated mixed-criticality analyses [16, 14] in that the proposed clustering optimization exploits the statistical rarity of concurrent overruns to improve resource efficiency, rather than relying exclusively on deterministic HI-level execution budgets. The analysis pipeline proceeds as follows: tasks are first classified into high- and low-utilization subsets using Definition 1; for each high-utilization DAG, a clustering configuration is determined and the original DAG is reduced accordingly, and the required number of dedicated cores is computed via the multipath bound on the reduced DAG; in parallel, low-utilization tasks are assigned to remaining cores using partitioned scheduling with deterministic analysis. A task set is deemed probabilistically schedulable if both the deterministic conditions (for low-utilization tasks) and the probabilistic conditions (for the clustering-based high-utilization analysis under budget $F_S$) are satisfied.

The probabilistic clustering scheme, which is the core contribution of this work, is described below. The goal is to reduce the pessimism in schedulability analysis by exploiting the statistical rarity of multiple vertices exceeding their LO-level execution budgets.

The clustering problem entails a large combinatorial search space, because a clustering configuration simultaneously affects (i) the reduced DAG structure (and its acyclicity), (ii) the multipath-based core requirement $p_i^{\ast }$, and (iii) the probabilistic constraint . In particular, merge and split transitions change the total number of clusters $K$, thereby shifting the per-cluster budget $F_S/K$ for all clusters simultaneously; this global coupling means that a local transition can alter the feasibility of many other clusters, making the search space highly non-smooth and challenging for purely local or greedy optimization. Moreover, the pipeline from a clustering assignment to the required number of cores involves multiple coupled stages, constructing the reduced DAG, computing the multipath response-time bound, and evaluating the probabilistic constraint, each of which is non-trivial. Because this pipeline has no closed-form relationship between the clustering decision variables and the objective, exact optimization methods (e.g., integer programming or dynamic programming) cannot be directly applied. This work therefore adopts simulated annealing (SA), a metaheuristic for exploring rugged discrete search spaces [13, 4]. Although SA does not guarantee a globally optimal solution, the objective function in (11) changes smoothly under local transitions (moving a vertex or merging two small clusters typically changes the core count by a small integer), which allows SA to converge to a good local optimum within a practical time budget.

Simulated annealing is a randomized local-search method. At each step, the algorithm samples a neighboring solution and accepts the candidate either when the candidate improves the objective or, otherwise, with a probability controlled by a temperature parameter. This design enables occasional acceptance of worse solutions early in the search to escape local minima, while the search becomes increasingly selective as the temperature decreases.

The optimization state is a clustering assignment for each high-utilization DAG. The initial state assigns each vertex to its own singleton cluster, which is always feasible since each $g_m^W=0$ (no two vertices can fail in a single-vertex cluster). At each iteration, the algorithm selects one high-utilization DAG and generates a candidate by applying one of the following neighborhood transitions (illustrated in Figure 2):

• $\mathrm{■}$

  Move: Move a vertex to a neighboring cluster.

• $\mathrm{■}$

  Merge: Merge two adjacent clusters.

• $\mathrm{■}$

  Split: Split a cluster into two connected subclusters.

• $\mathrm{■}$

  Merge-Split: This joint transition is useful for repartitioning adjacent clusters: a Split-only move often worsens the objective as an intermediate step, whereas Merge-Split can directly propose a new boundary between two neighboring clusters. Specifically, it merges two adjacent clusters into one, then splits the merged cluster into two connected subclusters and adopts the split that yields the best objective value. If the merged cluster contains at most $k_{\max }$ vertices (a configurable threshold), all valid connected bipartitions are enumerated exhaustively and the best one is selected. If the merged cluster exceeds $k_{\max }$ vertices, a fixed number of random connected bipartitions are sampled instead, avoiding the exponential enumeration cost.

If the resulting reduced DAG is cyclic, the candidate is rejected immediately.

The optimization minimizes a weighted combination of three terms: (1) the total number of required cores $E_{\text{cores}}={\sum }_i{p}_i^{\ast }$, (2) a tie-breaker term $E_{\text{path}}={\sum }_{i}L(G_i^{\prime })$ based on the critical-path length of the reduced DAG, and (3) a penalty term $P_{\text{viol}}$ that penalizes constraint violations; specifically, $P_{\text{viol}}={\sum }_m\max (0,g_m^W-F_S/K)$ accumulates the excess failure probability over all clusters that violate the per-cluster budget. Since low-utilization tasks are partitioned independently using MC-Partition, their core allocation is fixed and not affected by clustering; hence the optimization minimizes only the high-utilization core sum ${\sum }_i{p}_i^{\ast }$. The combined objective is

where $\epsilon$ is a small constant (e.g., ${10}^{-4}$) so that $E_{\text{path}}$ serves only as a tie-breaker. The penalty weight $\omega (t)$ increases linearly over the optimization time budget, from ${\omega }_{\text{start}}$ to ${\omega }_{\text{end}}$, to shift the search gradually from exploration to constraint satisfaction.

Let $\mathrm{\Delta }E=E_{\text{candidate}}-E_{\text{current}}$ be the objective difference. SA accepts any improving move () unconditionally, and accepts a worsening move ($\mathrm{\Delta }E>0$) with probability $\exp (-\mathrm{\Delta }E/T(t))$, where $T(t)$ is the temperature at time $t$. Intuitively, when $\mathrm{\Delta }E=1$ and $T(t)=1$, the acceptance probability becomes $\exp (-1)=1/e\approx 0.368$; as $T(t)$ decreases, the same worsening move is less likely to be accepted. Improving moves () are always accepted.

This work uses an exponential cooling schedule, in which the temperature decreases geometrically from $T_{\text{start}}$ to $T_{\text{end}}$:

where $T_{\text{start}}$ and $T_{\text{end}}$ are user-specified initial and final temperatures that control the acceptance rate of worsening moves, and $t_{\text{limit}}$ is the time budget. They are chosen relative to the scale of the objective function. Since $E_{\text{cores}}$ is the dominant term and changes in integer units, the temperature is kept much smaller than the cost of increasing the required number of cores. However, $T_{\text{start}}$ is kept positive and large enough to accept small worsening moves in the auxiliary terms, especially the tie-breaker term $\epsilon E_{\text{path}}$, so that the search can explore different clusterings with the same core count and avoid purely greedy local decisions. As the temperature decreases toward $T_{\text{end}}$, the search gradually becomes more selective, so that late-stage iterations focus on local refinement rather than broad exploration.

Intermediate solutions can violate the probabilistic constraint, but the algorithm tracks the best feasible solution encountered. Only feasible solutions (all ) are candidates for the final output. Let $K$ denote the total number of clusters over all reduced DAGs of HI-criticality tasks; $K$ is recomputed after each accepted merge or split. Since the singleton clustering is always feasible (each $g_m^W=0$), a feasible solution is guaranteed to exist; Algorithm 1 summarizes the optimization procedure.

Each SA iteration evaluates one clustering candidate. The dominant cost is the multipath bound computation for the affected DAG, which takes $O(p_{\max }({|V^{\prime }|}^2+|V^{\prime }|\log |V^{\prime }|))$ time, where $|V^{\prime }|$ is the number of clusters in the reduced DAG. Recomputing $g_m^W$ for affected clusters is proportional to the number of touched clusters and their sizes; a conservative bound is $O(K\cdot k_{\max })$, where $K$ is the number of clusters in the system and $k_{\max }$ is the maximum cluster size. With $N_{\text{iter}}$ SA iterations, the total time complexity is $O(N_{\text{iter}}\cdot p_{\max }\cdot {|V|}^2)$ in the worst case. In practice, the time budget $t_{\text{limit}}$ determines the number of iterations.

To reduce overhead, each transition affects only one DAG; the core counts of other DAGs are cached and reused. The per-job cluster failure probability $g_m^{\text{job}}$ is computed exactly using Theorem 4, then converted to $g_m^W$ via Equation 6; no approximation is used other than the union bound. No explicit limit is placed on cluster size; the constraint implicitly limits how many vertices can be merged. Cycle detection is performed via DFS on the reduced DAG; if a back edge is found (indicating a cycle), the clustering is rejected.

The proposed probabilistic schedulability analysis is evaluated through experiments using synthetic task sets.

Prior work on mixed-criticality scheduling is reviewed below, focusing on three key areas relevant to this paper: probabilistic approaches for mixed-criticality systems, federated scheduling of mixed-criticality DAG tasks, and response-time analysis for DAG tasks. A comparative summary is provided in Table 2.

One line of research has focused on incorporating permitted system failure probabilities into the scheduling of mixed-criticality systems [8]. This approach introduces a probabilistic parameter for each high-criticality task, representing the likelihood of the task exceeding its typical execution time budget. Instead of pessimistically assuming that all high-criticality tasks might overrun simultaneously, the method groups tasks into clusters. For each cluster, a shared “server” capacity is provisioned to handle overruns from only one task at a time, under the condition that the probability of multiple simultaneous overruns is below the permitted system failure threshold. This strategy significantly reduces pessimism and improves resource efficiency. However, the analysis and scheduling technique are designed for sequential, independent tasks and do not address the challenges introduced by the internal parallelism and precedence constraints of DAG tasks.

Another relevant direction of research analyzes systems with probabilistic execution times and proposes metrics inspired by safety standards [5]. This work focuses on quantifying the impact of degradation, which occurs when lower-criticality tasks are dropped, on the overall system performance. Metrics such as the probability of a deadline miss per hour and the expected time before degradation are introduced to provide a more comprehensive view of system behavior. While this research provides a valuable framework for probabilistic analysis in mixed-criticality systems, the approach does not specifically consider the scheduling of parallel tasks with complex internal dependencies, such as those modeled by DAGs.

In the domain of mixed-criticality scheduling for parallel tasks, federated scheduling has been developed as an effective paradigm. Pathan [16] proposes a federated scheduling approach for mixed-criticality parallel tasks on multiprocessors, where high-utilization tasks are assigned dedicated cores and low-utilization tasks are scheduled on shared cores. The analysis provides a work-span bound to compute the number of dedicated cores for each high-utilization DAG. This method is used as a deterministic baseline (Fed-2018) in our evaluation. Li et al. [14] extend the federated scheduling idea to a semi-federated scheme, which allows partial core sharing among high-utilization DAGs to improve resource efficiency, while maintaining schedulability guarantees under mixed criticality. Guan et al. [7] address relaxed-deadline DAG tasks within a mixed-criticality context, providing the first federated schedulability analysis that handles the case where the deadline exceeds the period. While these approaches effectively manage parallel task scheduling under mixed criticality, they all rely on deterministic WCET parameters and do not exploit the statistical rarity of simultaneous overruns.

For response-time analysis of DAG tasks, He et al. [9] propose the multipath bound, which generalizes the classical work-span bound by exploiting multiple vertex-disjoint paths to derive a tighter response-time estimate. This bound is computed by reducing the problem to a minimum-cost flow formulation. The multipath bound is not specific to mixed-criticality systems and does not incorporate probabilistic execution models, but the multipath bound serves as the response-time analysis component in the proposed method.

The research presented in this paper bridges the gap between probabilistic mixed-criticality analysis and DAG task scheduling. By integrating probabilistic vertex grouping into the federated scheduling framework and applying the multipath bound on the resulting reduced DAGs, the proposed method addresses all four dimensions in Table 2, enabling resource-efficient scheduling with quantitative safety guarantees for mixed-criticality DAG tasks on multiprocessors.

This paper presented a probabilistic schedulability analysis for mixed-criticality sporadic DAG tasks on identical multiprocessors under federated scheduling. The key idea is to reduce the pessimism of WCET-based analysis by exploiting the statistical rarity of concurrent execution-time overruns. To this end, a probabilistic clustering scheme that bounds cluster execution under a Single-HI assumption and quantifies the probability that the assumption is violated is proposed. By converting per-job cluster-failure probabilities to an operational-window level and enforcing uniform per-cluster constraints, the analysis composes to a system-level failure guarantee through a union bound. This probabilistic constraint is then combined with a multipath-based response-time bound on the reduced DAG to compute the dedicated cores required for high-utilization tasks, and a simulated-annealing-based procedure is introduced to search for efficient clusterings under a fixed time budget.

Experimental results on synthetic DAG task sets indicate that the proposed method reduces the total required cores compared to deterministic baselines, and that probabilistic clustering yields additional gains beyond those obtained from switching from a work-span bound to a multipath bound alone, especially for DAGs with high parallelism. The sensitivity analysis further shows that, in our experiments, relaxing the system-level failure budget $F_S$ generally reduces the required number of cores; however, the marginal benefit diminishes as $F_S$ increases, suggesting a diminishing-returns regime where further relaxation yields only limited additional resource savings. The optimization time-budget study confirms that even a one-second search already outperforms the deterministic baselines, while extending the budget to ten seconds yields further reductions, particularly for task sets with moderate-to-high core demands. These results support the premise that incorporating probabilistic execution information into mixed-criticality federated analysis can improve resource efficiency while preserving a system-level failure budget.

Multiple directions remain for future work. First, the current formulation assumes independence of vertex exceedance events and uses a uniform failure-budget allocation across clusters; incorporating correlation models and exploring risk-proportional allocations could further improve tightness. Second, extending the analysis to constrained-deadline or arbitrary-deadline DAG models is an important next step. Finally, broader sensitivity studies over probabilistic parameters and more extensive scalability characterization will strengthen practical applicability.