<p>We present the first (to our knowledge) Deep-Learning based framework for real-time schedulability-analysis that guarantees to never incorrectly mis-classify an unschedulable system as being schedulable, and is hence suitable for use in safety-critical scenarios. We relate applicability of this framework to well-understood concepts in computational complexity theory: membership in the complexity class NP. We apply the framework upon the widely-studied schedulability analysis problems of determining whether a given constrained-deadline sporadic task system is schedulable on a preemptive uniprocessor under both Deadline-Monotonic and EDF scheduling. As a proof-of-concept, we implement our framework for Deadline-Monotonic scheduling, and demonstrate that it has a predictive accuracy exceeding <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11241_2025_9450_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$70\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>70</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> for systems of as many as 20 tasks <i>without making any unsafe predictions</i>. Furthermore, the implementation has very small (<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11241_2025_9450_Article_IEq2.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">$<1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo><</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> ms on two widely-used embedded platforms; <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11241_2025_9450_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">$<4~\upmu$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo><</mo> <mn>4</mn> <mspace width="3.33333pt" /> <mi mathvariant="normal">μ</mi> </mrow> </math></EquationSource> </InlineEquation>s on an embedded FPGA) and highly predictable running times.</p>

Learning-assisted schedulability analysis: opportunities and limitations

期刊论文
出版模式：

开放获取
发表日期：

2025年7月2日

查看全文

Sanjoy Baruah,
Pontus Ekberg,
Marion Sudvarg

摘要

We present the first (to our knowledge) Deep-Learning based framework for real-time schedulability-analysis that guarantees to never incorrectly mis-classify an unschedulable system as being schedulable, and is hence suitable for use in safety-critical scenarios. We relate applicability of this framework to well-understood concepts in computational complexity theory: membership in the complexity class NP. We apply the framework upon the widely-studied schedulability analysis problems of determining whether a given constrained-deadline sporadic task system is schedulable on a preemptive uniprocessor under both Deadline-Monotonic and EDF scheduling. As a proof-of-concept, we implement our framework for Deadline-Monotonic scheduling, and demonstrate that it has a predictive accuracy exceeding $70\%$ $70 %$ for systems of as many as 20 tasks without making any unsafe predictions. Furthermore, the implementation has very small ( $<1$ $< 1$ ms on two widely-used embedded platforms; $<4~\upmu$ $< 4 μ$ s on an embedded FPGA) and highly predictable running times.