Abstract
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.
We introduce a novel iterative approach to efficiently cope with this combinatorial explosion, called combinatorial abstraction refinement. In combination with other techniques it significantly reduces exponential growth of run-time for most inputs. We apply the method to static task priorities and demonstrate that a prototype implementation outperforms the state-of-the art pseudo-polynomial analysis for dynamic priority feasibility. It further shows better scaling behavior for randomly generated problem instances. We extend the approach to non-preemptive schedulers as well as static job-type priorities where jobs of different types in the same task may be assigned different static priorities. Finally, we provide a general, abstract formulation of the algorithm, since we believe that this method can be applicable to a variety of combinatorial problems in the theory of real-time systems with certain abstraction structures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Another important condition for this is that all jobs released by the same task do have the same priority. We extend the method to SJP in Sect. 6, i.e., where different vertices could be assigned different static priorities.
The point-wise maximum on request functions and the dominance relation from Definition 6 are a join-semilattice \((\succcurlyeq , \sqcup )\) on the request functions for each task. These semilattices are the core structure of our abstraction refinement technique.
A bound \(L\) for the size of the maximal busy window can be easily computed by finding smallest interval size \(t\) for which \(\sum _{T\in \tau } \textit{mrf }^{(T)}(t) \leqslant t\).
References
Audsley NC (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. YCS-164, University of York, England
Baruah SK (1998) A general model for recurring real-time tasks. In: Proceedings of the Real-Time Systems Symposium RTSS, pp 114–122 1998
Baruah SK (2010) The non-cyclic recurring real-time task model. In: Proceedings of the real-time systems symposium RTSS, pp 173–182 2010
Baruah S, Chen D, Gorinsky S, Mok A (1999) Generalized multiframe tasks. Real-Time Syst 17(1):5–22
Clarke E, Grumberg O, Jha S, Lu Y, Veith H (2000) Counterexample-guided abstraction refinement. In: Emerson E, Sistla A (eds) Computer aided verification. Lecture Notes in Computer Science, vol 1855. Springer, Berlin, pp 154–169
Cousot P, Cousot R (1977) Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on principles of programming languages. ACM, New York, pp 238–252
Davis R, Burns A (2011) Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real-Time Syst. 47(1):1–40
Davis RI, Burns A, Bril RJ, Lukkien JJ (2007) Controller area network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Syst. 35(3):239–272
Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: Proceeding of IFIP congress, vol 74. Stockholm, pp 807–813, 1974
Fersman E, Krcal P, Pettersson P, Yi W (2007) Task automata: schedulability, decidability and undecidability. Inf. Comput. 205(8):1149–1172
George L, Rivierre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Research Report RR-2966, INRIA, Projet REFLECS
Gulavani BS, Chakraborty S, Nori AV, Rajamani SK (2008) Automatically refining abstract interpretations. In: Proceedings of the 14th international conference on tools and algorithms for the construction and analysis of systems (TACAS)
Han C-CJ (1998) A better polynomial-time schedulability test for real-time multiframe tasks. In: Proceedings of the RTSS. IEEE Computer Society, Washington, p 104
Harbour M, Klein M, Lehoczky J (1991) Fixed priority scheduling of periodic tasks with varying execution priority. In: Proceedings of the IEEE real-time systems symposium, RTSS. IEEE, pp 116–128
Joseph M, Pandya PK (1986) Finding response times in a real-time system. Comput J 29:390–395
Lehoczky J (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings of the 11th real-time systems symposium. IEEE, pp 201–209
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61
Lu W-C, Lin K-J, Wei H-W, Shih W-K (2007) New schedulability conditions for real-time multiframe tasks. In: Proceedings of the euromicro conference on real-time systems, ECRTS. IEEE, pp 39–50
Mok AK, Chen D (1997) A multiframe model for real-time tasks. IEEE Trans Softw Eng 23(10):635–645
Stigge M (2014) Real-Time workload models: expressiveness vs. analysis efficiency. PhD thesis, Uppsala University, Uppsala
Stigge M, Ekberg P, Guan N, Yi W (2011) On the tractability of digraph-based task models. In: Proceedings of the euromicro conference on real-time systems, ECRTS. IEEE, pp 162–171
Stigge M, Ekberg P, Guan N, Yi W (2011) The digraph real-time task model. In: Proceedings of the real-time and embedded technology and applications symposium. IEEE, pp 71–80
Stigge M, Yi W (2012) Hardness results for static priority real-time scheduling. In: Proceedings of the euromicro conference on real-time systems, ECRTS. IEEE, pp 189–198
Stigge M, Yi W (2013) Combinatorial abstraction refinement for feasibility analysis. In: Proceedings of the real-time systems symposium, RTSS. IEEE, pp 340–349
Takada H, Sakamura K (1997) Schedulability of generalized multiframe task sets under static priority assignment. In: Proceedings of the real-time computing systems and applications, RTCSA. IEEE, pp 80–86
Thiele L, Chakraborty S, Naedele M (2000) Real-time calculus for scheduling hard real-time systems. In: Proceedings of the International Symposium on Circuits and Systems, ISCAS 2000, vol 4. Geneva, 2000
Tindell K, Burns A (1994) Guaranteeing message latencies on control area network (CAN). In: Proceedings of the 1st international CAN conference on control area network (CAN) 1994
Wei Kuo T, Pin Chang L, Hua Liu Y, Jay Lin K (2003) Efficient online schedulability tests for real-time systems. IEEE Trans Softw Eng 29:734–751
Yao G, Buttazzo G, Bertogna M (2010) Feasibility analysis under fixed priority scheduling with fixed preemption points. In: Proceedings of the IEEE 16th international conference on embedded and real-time computing systems and applications (RTCSA), 2010. IEEE, pp 71–80
Zuhily A, Burns A (2009) Exact scheduling analysis of non-accumulatively monotonic multiframe tasks. Real-Time Syst J 43:119–146
Acknowledgments
The authors would like to thank the anonymous reviewers of the RTSS 2013 conference and the Real-Time Systems journal for their constructive comments on the conference version (Stigge and Yi 2013) and earlier manuscripts of this article, respectively.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Stigge, M., Yi, W. Combinatorial abstraction refinement for feasibility analysis of static priorities. Real-Time Syst 51, 639–674 (2015). https://doi.org/10.1007/s11241-015-9220-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11241-015-9220-5