nach oben

Real-Time Systems

Erschienen in:

01.01.2014

Mixed-criticality scheduling on multiprocessors

verfasst von: Sanjoy Baruah, Bipasa Chattopadhyay, Haohan Li, Insik Shin

Erschienen in: Real-Time Systems | Ausgabe 1/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The scheduling of mixed-criticality implicit-deadline sporadic task systems on identical multiprocessor platforms is considered. Two approaches, one for global and another for partitioned scheduling, are described. Theoretical analyses and simulation experiments are used to compare the global and partitioned scheduling approaches.

Vorheriger Artikel Task assignment algorithms for two-type heterogeneous multiprocessors

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

We assume that the run-time system provides support for ensuring that jobs do not execute for more than a specified amount; see, e.g., Baruah et al. (2011b) for a discussion of this issue.

By applying some results from Baruah et al. (2012), this result can easily be improved to show that the speedup bound is actually no more than ((4/3)+ϵ).

Although this is not a multiprocessor example, it serves to illustrate the steps taken by the algorithm in a relatively simple manner.

Observe that these conditions are exactly the ones that we have generalized in order to come up with the conditions P1–P2 (Eqs. (2) and (3)) in Sect. 5.2.

Baker T (2005) Comparison of empirical success rates of global vs. partitioned fixed-priority and EDF scheduling for hard real time. Tech Rep TR-050601, Department of Computer Science, Florida State University

Baker T (2006) A comparison of global and partitioned EDF schedulability tests for multiprocessors. In: Proceeding of the international conference on real-time and network systems, Poitiers, France

Baker T, Baruah S (2009) Sustainable multiprocessor scheduling of sporadic task systems. In: Proceedings of the EuroMicro conference on real-time systems. IEEE Computer Society Press, Dublin

Baruah S (2004) Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors. IEEE Trans Comput 53(6)

Baruah S, Burns A (2006) Sustainable scheduling analysis. In: Proceedings of the IEEE real-time systems symposium. IEEE Computer Society Press, Rio de Janeiro, pp 159–168

Baruah S, Fohler G (2011) Certification-cognizant time-triggered scheduling of mixed-criticality systems. In: Proceedings of the IEEE real-time systems symposium (RTSS). IEEE Computer Society Press, Vienna

Baruah S, Bonifaci V, D’Angelo G, Marchetti-Spaccamela A, van der Ster S, Stougie L (2011a) Mixed-criticality scheduling of sporadic task systems. In: Proceedings of the 19th annual European symposium on algorithms. Springer, Saarbrucken, pp 555–566

Baruah S, Burns A, Davis R (2011b) Response-time analysis for mixed criticality systems. In: Proceedings of the IEEE real-time systems symposium (RTSS). IEEE Computer Society Press, Vienna

Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, van der Ster S, Stougie L (2012) The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In: Proceedings of the 2012 24th euromicro conference on real-time systems ECRTS’12. IEEE Computer Society, Pisa

Bertogna M (2008) Real-time scheduling analysis for multiprocessor platforms. PhD thesis, Scuola Superiore Santa Anna, Pisa, Italy

Bertogna M (2009) Evaluation of existing schedulability tests for global EDF. In: ICPPW’09: proceedings of the 2009 international conference on parallel processing workshops. IEEE Computer Society, Washington, pp 11–18. doi:10.1109/ICPPW.2009.12 CrossRef

Chekuri C, Khanna S (1999) On multi-dimensional packing problems. In: Proceedings of the tenth annual ACM-SIAM symposium on discrete algorithms, pp 185–194

Chekuri C, Khanna S (2004) On multidimensional packing problems. SIAM J Comput 33(4):837–851. doi:10.1137/S0097539799356265 MathSciNetCrossRefMATH

de Niz D, Lakshmanan K, Rajkumar RR (2009) On the scheduling of mixed-criticality real-time task sets. In: Proceedings of the real-time systems symposium. IEEE Computer Society Press, Washington, pp 291–300

Dertouzos M (1974) Control robotics: the procedural control of physical processors. In: Proceedings of the IFIP Congress, pp 807–813

Dorin F, Richard P, Richard M, Goossens J (2010) Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities. Real-Time Systems

Ekberg P, Yi W (2012) Bounding and shaping the demand of mixed-criticality sporadic tasks. In: Proceedings of the 2012 24th euromicro conference on real-time systems ECRTS’12. IEEE Computer Society, Pisa

Guan N, Ekberg P, Stigge M, Yi W (2011) Effective and efficient scheduling for certifiable mixed criticality sporadic task systems. In: Proceedings of the IEEE real-time systems symposium (RTSS). IEEE Computer Society Press, Vienna

Guan N, Ekberg P, Stigge M, Yi W (2013) Improving the scheduling of certifiable mixed-criticality sporadic task systems. Tech Rep 2013-008, Department of Information Technology, Uppsala University

Herman J, Kenna C, Mollison M, Anderson J, Johnson D (2012) RTOs support for multicore mixed-criticality systems. In: Proceedings of the 2012 IEEE real-time and embedded technology and applications symposium RTAS’12. IEEE Computer Society, Beijing

Huang HM, Gill C, Lu C (2012) Implementation and evaluation of mixed-criticality scheduling algorithms for periodic tasks. In: Proceedings of the 2012 IEEE real-time and embedded technology and applications symposium RTAS’12. IEEE Computer Society, Beijing

Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. J ACM 37(4):617–643 MathSciNetCrossRef

Lakshmanan K, de Niz D, Rajkumar RR, Moreno G (2010) Resource allocation in distributed mixed-criticality cyber-physical systems. In: Proceedings of the 30th international conference of distributed computing systems. IEEE Computer Society Press, New York

Lakshmanan K, de Niz D, Rajkumar RR (2011) Mixed-criticality task synchronization in zero-slack scheduling. In: Proceedings of the real-time and embedded technology and applications symposium. IEEE Computer Society Press, Chicago

Li H, Baruah S (2012) Global mixed-criticality scheduling on multiprocessors. In: Proceedings of the 2012 24th euromicro conference on real-time systems ECRTS’12. IEEE Computer Society, Pisa

Liu C, Layland J (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 20(1):46–61 MathSciNetCrossRefMATH

Mollison M, Erickson J, Anderson J, Baruah S, Scoredos J (2010) Mixed-criticality real-time scheduling for multicore systems. In: Proceedings of the IEEE international conference on embedded systems and software. IEEE Computer Society Press, Bradford

Park T, Kim S (2011) Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems. In: Proceedings of the 11th international conference on embedded software, EMSOFT-2011, pp 253–262

Pathan R (2012) Schedulability analysis of mixed-criticality systems on multiprocessors. In: Proceedings of the 2012 24th euromicro conference on real-time systems ECRTS’12. IEEE Computer Society, Pisa

Santy F, George L, Thierry P, Goossens J (2012) Relaxing mixed-criticality scheduling strictness for task sets scheduled with FP. In: Proceedings of the 2012 24th euromicro conference on real-time systems ECRTS’12. IEEE Computer Society, Pisa

Tamas-Selicean D, Pop P (2011) Design optimization of mixed-criticality real-time applications on cost-constrained partitioned architectures. In: Proceedings of the IEEE real-time systems symposium (RTSS). IEEE Computer Society Press, Vienna

Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proceedings of the real-time systems symposium. IEEE Computer Society Press, Tucson, pp 239–243

Yun H, Yao G, Pellizzoni R, Caccamo M, Sha L (2012) Memory access control in multiprocessor for real-time systems with mixed criticality. In: Proceedings of the 2012 24th euromicro conference on real-time systems ECRTS’12. IEEE Computer Society, Pisa

Titel: Mixed-criticality scheduling on multiprocessors
verfasst von: Sanjoy Baruah
Bipasa Chattopadhyay
Haohan Li
Insik Shin
Publikationsdatum: 01.01.2014
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 1/2014
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-013-9184-2

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 1/2014

Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling

Task assignment algorithms for two-type heterogeneous multiprocessors

Special issue on multiprocessor and mixed-criticality scheduling

Bounding and shaping the demand of generalized mixed-criticality sporadic task systems