Learning-Assisted Schedulability Analysis: Opportunities and Limitations

We present the first (to our knowledge) Deep-Learning based framework for realtime schedulability-analysis that guarantees to never incorrectly mis-classify an unschedulable system as being schedulable, and is hence suitable for use in safetycritical 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% for systems of as many as 20 tasks without making any unsafe predictions. Furthermore, the implementation has very small (<1 ms on two widely-used embedded platforms; <4 μs on an embedded FPGA) and highly predictable running times.