nach oben

Real-Time Systems

Erschienen in:

18.01.2017

An efficient schedulability analysis for optimizing systems with adaptive mixed-criticality scheduling

verfasst von: Yecheng Zhao, Haibo Zeng

Erschienen in: Real-Time Systems | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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).

Vorheriger Artikel Fixed priority scheduling with pre-emption thresholds and cache-related pre-emption delays: integrated analysis and evaluation

Nächster Artikel Schedulability analysis of Ethernet Audio Video Bridging networks with scheduled traffic support

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

We realize there is another analysis for AMC documented in Huang et al. (2014). We leave it out for now as it may be optimistic (Burns and Davis 2015).

Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8:284–292CrossRef

Baruah S (2014) Implementing mixed-criticality synchronous reactive programs upon uniprocessor platforms. Real-Time Syst 50(3):317–341CrossRefMATH

Baruah S, Burns A (2011) Implementing mixed criticality systems in Ada. In: Romanovsky A, Vardanega T (eds) Reliable software technologies-Ada-Europe 2011. Springer, Berlin, pp 174–188CrossRef

Baruah S, Burns A, Davis R (2011) Response-time analysis for mixed criticality systems. In: 32nd IEEE real-time systems symposium

Baruah SK (2003) Dynamic- and static-priority scheduling of recurring real-time tasks. Real-Time Syst 24(1):93–128CrossRefMATH

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

Bazaka K, Jacob MV (2012) Implantable devices: issues and challenges. Electronics 2(1):1–34CrossRef

Bini E, Buttazzo GC (2004) Schedulability analysis of periodic fixed priority systems. IEEE Trans Comput 53(11):1462–1473CrossRef

Burns A, Davis R (2014) Adaptive mixed criticality scheduling with deferred preemption. In: IEEE Real-time systems symposium

Burns A, Davis R (2015) Mixed criticality systems: a review. Technical report, Department of Computer Science, University of York

Chakraborty S (2012) Keynote talk: challenges in automotive cyber-physical systems design. In: 25th International conference on VLSI design (VLSID). IEEE, pp 9–10

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

Davis R, Zabos A, Burns A (2008) Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans Comput 57(9):1261–1276MathSciNetCrossRef

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

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

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

Di Natale M, Guo L, Zeng H, Sangiovanni-Vincentelli A (2010) Synthesis of multi-task implementations of simulink models with minimum delays. IEEE Trans Ind Inform 6(4):637–651CrossRef

Dick RP, Rhodes DL, Wolf W (1998) TGFF: task graphs for free. In: 6th international workshop on Hardware/software codesign

Fleming T, Burns A (2013) Extending mixed criticality scheduling. In: Workshop on mixed criticality systems (WMC)

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

Huang H-M, Gill C, Lu C (2014) Implementation and evaluation of mixed-criticality scheduling approaches for sporadic tasks. ACM Trans Embed Comput Syst 13(4s):126CrossRef

International Business Machines Corporation (2016) CPLEX optimizer. http://www.ibm.com/software/commerce/optimization/cplex-optimizer/. Accessed Feb 2016

International Electrotechnical Commission (2016) IEC 62304:2006 medical device software—software life cycle processes. https://webstore.iec.ch/publication/6792. Accessed Feb 2016

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

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

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)

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

MathWorks. The MathWorks simulink and stateflow user’s manuals. http://www.mathworks.com

Oral M, Kettani O (1992) A linearization procedure for quadratic and cubic mixed-integer problems. Oper Res 40(S1):109–116MathSciNetCrossRefMATH

Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: 28th IEEE real-time systems symposium

Wikipedia. Floor and ceiling functions. https://en.wikipedia.org/wiki/Floor_and_ceiling_functions. Accessed Feb 2016

Zeng H, Di Natale M (2013) An efficient formulation of the real-time feasibility region for design optimization. IEEE Trans Comput 62(4):644–661MathSciNetCrossRef

Zhao Q, Gu Z, Yao M, Zeng H (2016) HLC-PCP: a resource synchronization protocol for mixed criticality systems. J Syst Archit 66(C):84–99CrossRef

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)

Zhao Q, Gu Z, Zeng H (2014) HLC-PCP: a resource synchronization protocol for certifiable mixed criticality scheduling. IEEE Embed Syst Lett 6(1):8–11CrossRef

Zhao Q, Gu Z, Zeng H (to appear) Design optimization for AUTOSAR models with preemption thresholds and mixed-criticality scheduling. J Syst Archit

Titel: An efficient schedulability analysis for optimizing systems with adaptive mixed-criticality scheduling
verfasst von: Yecheng Zhao
Haibo Zeng
Publikationsdatum: 18.01.2017
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 4/2017
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-017-9267-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2017

Fixed priority scheduling with pre-emption thresholds and cache-related pre-emption delays: integrated analysis and evaluation

Erratum to: Optimal minimal routing and priority assignment for priority-preemptive real-time NoCs

Schedulability analysis of Ethernet Audio Video Bridging networks with scheduled traffic support

Isolation scheduling on multicores: model and scheduling approaches

Optimal minimal routing and priority assignment for priority-preemptive real-time NoCs

Premium Partner