Leveraging Parallelism in Global Scheduling to Improve State Space Exploration in the SAG Framework

Response-time analysis (RTA) is crucial for ensuring the timeliness of real-time systems. As system complexity increases, there’s a growing need for RTA techniques that can automate the process of finding worst-case response times. The schedule-abstraction graph (SAG), a recent reachability-based RTA, addresses this by systematically exploring the decision space of global job-level fixed-priority (JLFP) scheduling policies for a given task set. SAG significantly outperforms existing RTAs for global scheduling on multicore, e.g., it can identify 12 times more schedulable task sets for global EDF in comparison to sufficient RTAs and operates 400 times faster than some other reachability-based tests.
Despite these achievements, the state-space explored by the SAG can become very large in case the release jitter or the number of cores is large. This is because at present the SAG approach explores one scheduling decision at a time, leaving the parallelism inherent to global scheduling unexploited during state-space exploration. Recognizing that multiple jobs can be dispatched concurrently without interference, we introduce the first state-space-reduction technique for SAG that identifies and analyzes sets of independent jobs in tandem. We apply this technique to both preemptive and non-preemptive SAG frameworks. Our empirical evaluations show that our solution efficiently reduces the number of explored states while maintaining or even enhancing the accuracy of the SAG analysis, enabling it to scale to larger systems. For instance, our method achieves a 6 times reduction in runtime while improving schedulability by 16% for preemptive task sets scheduled using global EDF (e.g., for systems with 2 to 12 cores and 60% utilization).