Partial-Order Reduction in Reachability-based Response-Time Analyses

Abstract

The temporal correctness of safety-critical systems is typically guaranteed via a response-time analysis, whose goal is to determine the worst-case response time (WCRT) of a set of input jobs when they are scheduled by a given scheduling policy on a computing resource.
However, response-time analysis is a hard problem to solve, with most variations of the problem being NP-hard. Recently, Nasri et al. have introduced an exact reachability-based response-time analysis that is based on exploring the space of possible decisions that a scheduler can take for a set of jobs/tasks. Their solution is at least three orders of magnitude faster than other exact response-time analyses and scales well.

Despite its current success in scalability, the schedule-abstraction-based analysis still faces one big fundamental limitation: in the reachability graph that it builds, each edge can only include one single scheduling decision. As a result, as soon as there are large uncertainties in the release time or execution time of the jobs in the input job set, the number of states generated by the schedule-abstraction graph grows exponentially because the analysis will try to explore all (valid) combinations of ordering between jobs.

We improve the scalability of the schedule-abstraction-based analysis by introducing partial-order reduction (POR) rules that allow combining multiple scheduling decisions on one edge and hence avoiding combinatorial exploration of all possible orderings between jobs in cases where there are large uncertainties. Our solution is an exact schedulability analysis and provides a safe response-time analysis that reduces the size of the graph while only introducing a small overestimation on the WCRT of the jobs.

Our key idea is to identify subsets of jobs for which the combinatorial exploration of all orderings is irrelevant to the schedulability of the job set. Exploring these combinations is irrelevant when all scenarios lead to a system state without encountering a deadline miss in any of those scenarios. Dispatching such jobs can be considered in a single step (that combines all those scheduling decisions), which further defers the state-space explosion.

We show that our solution is able to reduce the runtime of the analysis by five orders of magnitude on average, and the number of explored states by 98% on average in comparison to the original schedule-abstraction-based analysis of Nasri et al. for randomly generated periodic task sets. This achievement comes with a negligible cost of an average 0.1% increase in the WCRT of the jobs. This shows that POR allows us to analyze even more task sets than the original and has the potential to scale even further.