Combinatorial abstraction refinement for feasibility analysis of static priorities

摘要

Combinatorial explosion is a challenge for many analysis problems in the theory of hard real-time systems. One of these problems is static priority schedulability of workload models which are more expressive than the traditional periodic task model. Different classes of directed graphs have been proposed in recent years to model structures like frames, branching and loops. In contrast to dynamic priority schedulers with pseudo-polynomial time analysis methods, static priority schedulability has been shown to be intractable since it is strongly coNP-hard already for the relatively simple class of cyclic digraphs. The core of this problem is the necessity to combine different behaviors of the participating tasks.