zbMATH — the first resource for mathematics

An efficient schedulability analysis for optimizing systems with adaptive mixed-criticality scheduling. (English) Zbl 1409.68064
Summary: In the design optimization of real-time systems, the schedulability analysis is used to define the feasibility region within which tasks meet their deadlines, so that optimization algorithms can find the best solution within the region. However, the current analysis techniques for systems with adaptive mixed-criticality (AMC) scheduling are based on response time calculation, which are too complex for optimization purposes. In this paper, we provide a simpler schedulability test based on request bound functions, which allows an efficient definition of the feasibility region for AMC. We prove that the new analysis is safe with bounded pessimism. Experimental results show that our analysis provides much better scalability for optimization procedures, with only small loss of performance (less than 7% in weighted schedulability, and no more than 4% in optimization objectives).
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
CPLEX; Simulink; TGFF
Full Text: DOI
[1] Audsley, N; Burns, A; Richardson, M; Tindell, K; Wellings, AJ, Applying new scheduling theory to static priority pre-emptive scheduling, Softw Eng J, 8, 284-292, (1993)
[2] Baruah, S, Implementing mixed-criticality synchronous reactive programs upon uniprocessor platforms, Real-Time Syst, 50, 317-341, (2014) · Zbl 1291.68064
[3] Baruah, S; Burns, A; Romanovsky, A (ed.); Vardanega, T (ed.), Implementing mixed criticality systems in ada, 174-188, (2011), Berlin
[4] Baruah S, Burns A, Davis R (2011) Response-time analysis for mixed criticality systems. In: 32nd IEEE real-time systems symposium
[5] Baruah, SK, Dynamic- and static-priority scheduling of recurring real-time tasks, Real-Time Syst, 24, 93-128, (2003) · Zbl 1033.68012
[6] Bastoni A, Brandenburg B, Anderson J (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: 6th workshop on operating systems platforms for embedded real-time applications, pp 33-44 · Zbl 0771.90072
[7] Bazaka, K; Jacob, MV, Implantable devices: issues and challenges, Electronics, 2, 1-34, (2012)
[8] Bini, E; Buttazzo, GC, Schedulability analysis of periodic fixed priority systems, IEEE Trans Comput, 53, 1462-1473, (2004)
[9] Burns A, Davis R (2014) Adaptive mixed criticality scheduling with deferred preemption. In: IEEE Real-time systems symposium
[10] Burns A, Davis R (2015) Mixed criticality systems: a review. Technical report, Department of Computer Science, University of York
[11] Chakraborty S (2012) Keynote talk: challenges in automotive cyber-physical systems design. In: 25th International conference on VLSI design (VLSID). IEEE, pp 9-10
[12] Cho Y, Kim Y, Joo Y, Lee K, and Chang N (2008) Simultaneous optimization of battery-aware voltage regulator scheduling with dynamic voltage and frequency scaling. In: ACM/IEEE international symposium on low power electronics and design, pp 309-314
[13] Davis, R; Zabos, A; Burns, A, Efficient exact schedulability tests for fixed priority real-time systems, IEEE Trans Comput, 57, 1261-1276, (2008) · Zbl 1390.68122
[14] Davis RI, Burns A (2009) Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In: Proceedings of the 2009 30th IEEE real-time systems symposium, RTSS ’09, pp 398-409
[15] De Niz D, Lakshmanan K, Rajkumar R (2009) On the scheduling of mixed-criticality real-time task sets. In: 30th IEEE real-time systems symposium, pp 291-300
[16] Deng P, Zhu Q, Cremona F, Di Natale M, and Zeng H (2015) A model-based synthesis flow for automotive cps. In: ACM/IEEE international conference on cyber-physical systems · Zbl 1033.68012
[17] Natale, M; Guo, L; Zeng, H; Sangiovanni-Vincentelli, A, Synthesis of multi-task implementations of simulink models with minimum delays, IEEE Trans Ind Inform, 6, 637-651, (2010)
[18] Dick RP, Rhodes DL, Wolf W (1998) TGFF: task graphs for free. In: 6th international workshop on Hardware/software codesign
[19] Fleming T, Burns A (2013) Extending mixed criticality scheduling. In: Workshop on mixed criticality systems (WMC) · Zbl 1033.68012
[20] Goodenough JB, Sha L (1988) The priority ceiling protocol: a method for minimizing the blocking of high priority ada tasks. Ada Lett VIII(7):20-31
[21] Huang, H-M; Gill, C; Lu, C, Implementation and evaluation of mixed-criticality scheduling approaches for sporadic tasks, ACM Trans Embed Comput Syst, 13, 126, (2014)
[22] International Business Machines Corporation (2016) CPLEX optimizer. http://www.ibm.com/software/commerce/optimization/cplex-optimizer/. Accessed Feb 2016 · Zbl 1291.68064
[23] International Electrotechnical Commission (2016) IEC 62304:2006 medical device software—software life cycle processes. https://webstore.iec.ch/publication/6792. Accessed Feb 2016
[24] International Standardization Organization (2016) ISO 26262-1:2011(en) Road vehicles—functional safety—part 1: vocabulary. https://www.iso.org/obp/ui/#iso:std:iso:26262:-1:ed-1:v1:en. Accessed Feb 2016 · Zbl 0771.90072
[25] Kelly O, Aydin H, Zhao B (2011) On partitioned scheduling of fixed-priority mixed-criticality task sets. In: IEEE 10th international conference on trust, security and privacy in computing and communications (TrustCom), pp 1051-1059
[26] Kramer S, Ziegenbein D, Hamann A (2015) Real world automotive benchmarks for free. In: International workshop on analysis tools and methodologies for embedded and real-time systems (WATERS)
[27] Lehoczky J, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: exact characterization and average case behavior. In: 10th IEEE real-time systems symposium
[28] MathWorks. The MathWorks simulink and stateflow user’s manuals. http://www.mathworks.com
[29] Oral, M; Kettani, O, A linearization procedure for quadratic and cubic mixed-integer problems, Oper Res, 40, 109-116, (1992) · Zbl 0771.90072
[30] Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: 28th IEEE real-time systems symposium
[31] Wikipedia. Floor and ceiling functions. https://en.wikipedia.org/wiki/Floor_and_ceiling_functions. Accessed Feb 2016
[32] Zeng, H; Natale, M, An efficient formulation of the real-time feasibility region for design optimization, IEEE Trans Comput, 62, 644-661, (2013) · Zbl 1365.90175
[33] Zhao, Q; Gu, Z; Yao, M; Zeng, H, HLC-PCP: a resource synchronization protocol for mixed criticality systems, J Syst Archit, 66, 84-99, (2016)
[34] Zhao Q, Gu Z, Zeng H (2013) PT-AMC: Integrating Preemption Thresholds into Mixed-Criticality Scheduling. In: Proceedings of the design, automation & test in Europe conference & exhibition (DATE ’13)
[35] Zhao, Q; Gu, Z; Zeng, H, HLC-PCP: a resource synchronization protocol for certifiable mixed criticality scheduling, IEEE Embed Syst Lett, 6, 8-11, (2014)
[36] Zhao Q, Gu Z, Zeng H (to appear) Design optimization for AUTOSAR models with preemption thresholds and mixed-criticality scheduling. J Syst Archit
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.