DROPS

Document

DOI: 10.4230/LIPIcs.ECRTS.2026.3

Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors

Authors: Hiroto Takahashi, Atsushi Yano, and Takuya Azumi

Published in: LIPIcs, Volume 375, 38th European Conference on Real-Time Systems (ECRTS 2026)

Abstract

Mixed-criticality DAG task systems on multiprocessors require schedulability analysis to guarantee that safety-critical tasks meet their deadlines. Conventional approaches rely on worst-case execution times (WCETs), which account for extremely rare pathological scenarios and consequently lead to significant over-provisioning of processor cores. This paper proposes a probabilistic schedulability analysis that exploits the statistical rarity of multiple vertices within a DAG exceeding their expected execution budgets. By grouping vertices within each DAG into small clusters and bounding the probability that more than one vertex in a cluster overruns, the method assigns each cluster a tighter execution budget than the sum of individual WCETs, thereby reducing the number of cores required. The clustering configuration is optimized via simulated annealing to minimize total core usage while maintaining a designer-specified bound on the system-level probability of deadline misses. Experiments on synthetic task sets demonstrate that the proposed method reduces the required number of cores by up to 36% compared to a deterministic baseline, with larger gains for DAGs exhibiting higher internal parallelism.

Cite as

Hiroto Takahashi, Atsushi Yano, and Takuya Azumi. Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors. In 38th European Conference on Real-Time Systems (ECRTS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 375, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.ECRTS.2026.3,
  author =	{Takahashi, Hiroto and Yano, Atsushi and Azumi, Takuya},
  title =	{{Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors}},
  booktitle =	{38th European Conference on Real-Time Systems (ECRTS 2026)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-429-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{375},
  editor =	{Kritikakou, Angeliki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2026.3},
  URN =		{urn:nbn:de:0030-drops-265871},
  doi =		{10.4230/LIPIcs.ECRTS.2026.3},
  annote =	{Keywords: Mixed-Criticality Systems, DAG Tasks, Probabilistic Analysis, Federated Scheduling, Real-Time Systems}
}

Document

Artifact

DOI: 10.4230/DARTS.12.2.11

Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors (Artifact)

Authors: Hiroto Takahashi, Atsushi Yano, and Takuya Azumi

Published in: DARTS, Volume 12, Issue 2, Special Issue of the 38th European Conference on Real-Time Systems (ECRTS 2026)

Abstract

This artifact accompanies the ECRTS 2026 paper "Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors". The package provides the implementation of the proposed probabilistic schedulability analysis and baseline analyses, together with the DAG-generation wrapper, experiment drivers, plotting scripts, and input data needed to reproduce the main evaluation results of the paper. The primary reproduction workflow covers the paper-scale experiments for Figures 3-5, while additional check and smoke modes provide faster functional validation. The artifact was evaluated in the ECRTS 2026 Artifact Evaluation process and received all four artifact-evaluation seals: Artifact Available, Artifact Evaluated - Functional, Artifact Evaluated - Reusable, and Artifact Evaluated - Results Reproduced.

Cite as

Hiroto Takahashi, Atsushi Yano, and Takuya Azumi. Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors (Artifact). In Special Issue of the 38th European Conference on Real-Time Systems (ECRTS 2026). Dagstuhl Artifacts Series (DARTS), Volume 12, Issue 2, pp. 11:1-11:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{takahashi_et_al:DARTS.12.2.11,
  author =	{Takahashi, Hiroto and Yano, Atsushi and Azumi, Takuya},
  title =	{{Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors (Artifact)}},
  pages =	{11:1--11:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2026},
  volume =	{12},
  number =	{2},
  editor =	{Takahashi, Hiroto and Yano, Atsushi and Azumi, Takuya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.12.2.11},
  URN =		{urn:nbn:de:0030-drops-266280},
  doi =		{10.4230/DARTS.12.2.11},
  annote =	{Keywords: Mixed-Criticality Systems, DAG Tasks, Probabilistic Analysis, Federated Scheduling, Real-Time Systems, Artifact Evaluation}
}

Search Results

Documents authored by Yano, Atsushi

Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors

Abstract

Cite as

Probabilistic Schedulability Analysis for Mixed-Criticality DAG Tasks on Multiprocessors (Artifact)

Abstract

Cite as

Thanks for your feedback!

Could not send message