×

Response time analysis of digraph real-time tasks scheduled with static priority: generalization, approximation, and improvement. (English) Zbl 1425.68047

Summary: Graph-based task models have been studied to better model and analyze the schedulability of real-time systems. Among them, the digraph task model, with its powerful expressiveness to describe the behavior of a large class of real-time tasks, receives a wide range of interests recently. However, the exact schedulability analysis of digraph tasks on a uni-processor with preemptive static-priority scheduling has been shown to be coNP-hard. Approximate analyses based on the request and interference bound functions (rbf and ibf) have been proposed to improve the analysis efficiency. In this work, we summarize the existing results on these analysis techniques, and seek to further improve their generality, complexity, and accuracy. Specifically, we develop analysis techniques for tasks with arbitrary deadlines. We prove the periodicity of interference bound function such that it can be expressed as a finite aperiodic part and an infinite periodic part, which makes the asymptotic complexity of its calculation independent from the length of the time interval. Moreover, we develop a linear upper bound on ibf that is tighter than that of rbf, to derive a better response time bound.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

Simulink; SCADE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] André C (1995) Synccharts: a visual representation of reactive behaviors. Technical Report RR 96-56, I3S Laboratory, University of Nice-Sophia Antipolis, Nice
[2] Baruah S, Chen D, Gorinsky S, Mok A (1999) Generalized multiframe tasks. Real-Time Syst 17(1):5-22
[3] Baruah SK (1998) Feasibility analysis of recurring branching tasks. In: Proceedings of the 10th Euromicro workshop on real-time systems, pp. 138-145 · Zbl 0998.15020
[4] Baruah SK (2003) Dynamic-and static-priority scheduling of recurring real-time tasks. Real-Time Syst 24(1):93-128 · Zbl 1033.68012
[5] Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30(1-2):129-154 · Zbl 1083.68008
[6] Bini E, Nguyen THC, Richard P, Baruah SK (2009) A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans Comput 58(2):279 · Zbl 1368.68109
[7] Esterel Technologies (1984) The trusted design chain company: SCADE suite. http://www.esterel-technologies.com/products/scade-system/ · Zbl 1033.68012
[8] Garey MR, Johnson DS (1990) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York · Zbl 0411.68039
[9] Gavalec M (2000) Linear matrix period in max-plus algebra. Linear Algebra Appl 307(1):167-182 · Zbl 0998.15020
[10] Guan N, Gu C, Stigge M, Deng Q, Yi W (2014) Approximate response time analysis of real-time task graphs. In: IEEE real-time systems symposium (RTSS), pp. 304-313 · Zbl 1343.68037
[11] Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. JACM 47(4):617-643 · Zbl 1094.68529
[12] Lehoczky JP (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. RTSS 90:201-209
[13] Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. JACM 20(1):46-61 · Zbl 0265.68013
[14] Mathworks (1994) The Mathworks Simulink and StateFlow user’s manuals. http://www.mathworks.com · Zbl 1033.68012
[15] Mohaqeqi M, Abdullah J, Guan N, Yi W (2016) Schedulability analysis of synchronous digraph real-time tasks. In: 28th Euromicro conference on real-time systems (ECRTS)
[16] Mok AK (1983) Fundamental design problems of distributed systems for the hard-real-time environment. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge · Zbl 1094.68529
[17] Mok AK, Chen D (1997) A multiframe model for real-time tasks. IEEE Trans. Softw. Eng. 23(10):635-645
[18] Norstrom C, Wall A, Yi W (1999) Timed automata as task models for event-driven systems. In: Sixth international conference on real-time computing systems and applications, pp 182-189
[19] Stigge M (2014) Real-time workload models: expressiveness vs. analysis efficiency. Ph.D. thesis, Uppsala University, Uppsala
[20] Stigge M, Ekberg P, Guan N, Yi W (2011) The digraph real-time task model. In: 17th IEEE real-time and embedded technology and applications symposium (RTAS), pp 71-80
[21] Stigge M, Ekberg P, Guan N, Yi W (2011) On the tractability of digraph-based task models. In: 23rd Euromicro conference on real-time systems (ECRTS), pp 162-171
[22] Stigge M, Yi W (2012) Hardness results for static priority real-time scheduling. In: 24th Euromicro conference on real-time systems (ECRTS), pp 189-198 · Zbl 1338.68042
[23] Stigge M, Yi W (2013) Combinatorial abstraction refinement for feasibility analysis. In: 34th IEEE real-time systems symposium (RTSS), pp 340-349 · Zbl 1343.68037
[24] Stigge M, Yi W (2015) Combinatorial abstraction refinement for feasibility analysis of static priorities. Real-Time Syst 51:1-36 · Zbl 1343.68037
[25] Stigge M, Yi W (2015) Graph-based models for real-time workload: a survey. Real-Time Syst 51(5):602-636 · Zbl 1337.68050
[26] Young NE, Tarjant RE, Orlin JB (1991) Faster parametric shortest path and minimum-balance algorithms. Networks 21(2):205-221 · Zbl 0719.90087
[27] Zeng H, Di Natale, M (2012) Schedulability analysis of periodic tasks implementing synchronous finite state machines. In: 24th Euromicro conference on real-time systems (ECRTS). IEEE, pp 353-362 · Zbl 1337.68050
[28] Zeng H, Di Natale, M (2013) Using max-plus algebra to improve the analysis of non-cyclic task models. In: 25th Euromicro conference on real-time systems (ECRTS), pp 205-214 · Zbl 1094.68529
[29] Zeng H, Di Natale M (2015) Computing periodic request functions to speed-up the analysis of non-cyclic task models. Real-Time Syst 51(4):360-394 · Zbl 1338.68042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.