More Web Proxy on the site http://driver.im/

article

Mixed-criticality scheduling on multiprocessors

Authors:

Bipasa Chattopadhyay,

Insik ShinAuthors Info & Claims

Real-Time Systems, Volume 50, Issue 1

Pages 142 - 177

https://doi.org/10.1007/s11241-013-9184-2

Published: 01 January 2014 Publication History

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.

References

[1]

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.

[2]

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.

[3]

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.

[4]

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

[5]

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.

[6]

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.

[7]

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.

[8]

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.

[9]

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.

[10]

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

[11]

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.

[12]

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.

[13]

Chekuri C, Khanna S (2004) On multidimensional packing problems. SIAM J Comput 33(4):837-851.

Digital Library

[14]

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.

[15]

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

[16]

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

[17]

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.

[18]

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.

[19]

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.

[20]

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.

[21]

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.

[22]

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

Digital Library

[23]

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.

[24]

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.

[25]

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.

[26]

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

Digital Library

[27]

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.

[28]

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.

[29]

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.

[30]

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.

[31]

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.

[32]

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.

[33]

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.

Cited By

Pereira DGhose AGhosh SDey S(2023)Inferencing on Edge Devices: A Time- and Space-aware Co-scheduling ApproachACM Transactions on Design Automation of Electronic Systems10.1145/357619728:3(1-33)Online publication date: 19-Mar-2023
https://dl.acm.org/doi/10.1145/3576197
Tiansen LShujuan HFeng XWenjuan ZXingxing H(2023)A Mixed-Criticality Task Scheduling Method Based on Comprehensive Impact FactorComputers and Electrical Engineering10.1016/j.compeleceng.2022.108544105:COnline publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.compeleceng.2022.108544
She TGuo ZYang K(2022)Scheduling Constrained-Deadline Tasks in Precise Mixed-Criticality Systems on a Varying-Speed ProcessorProceedings of the 30th International Conference on Real-Time Networks and Systems10.1145/3534879.3534897(94-102)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3534879.3534897
Show More Cited By

Mixed-criticality scheduling on multiprocessors

Recommendations

Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred Preemption
Special Issue on Embedded Platforms for Crypto and Regular Papers

This article introduces schedulability analysis for Global Fixed Priority Scheduling with Deferred Preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of Global Fixed Priority Preemptive Scheduling (gFPPS) and Global Fixed ...
Multi-rate fluid scheduling of mixed-criticality systems on multiprocessors

In this paper we consider the problem of mixed-criticality (MC) scheduling of implicit-deadline sporadic task systems on a homogenous multiprocessor platform. Focusing on dual-criticality systems, algorithms based on the fluid scheduling model have been ...
The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Real-Time Systems

Real-Time Systems Volume 50, Issue 1

January 2014

177 pages

ISSN:0922-6443

Issue’s Table of Contents

Copyright © Copyright © 2014 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pereira DGhose AGhosh SDey S(2023)Inferencing on Edge Devices: A Time- and Space-aware Co-scheduling ApproachACM Transactions on Design Automation of Electronic Systems10.1145/357619728:3(1-33)Online publication date: 19-Mar-2023
https://dl.acm.org/doi/10.1145/3576197
Tiansen LShujuan HFeng XWenjuan ZXingxing H(2023)A Mixed-Criticality Task Scheduling Method Based on Comprehensive Impact FactorComputers and Electrical Engineering10.1016/j.compeleceng.2022.108544105:COnline publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.compeleceng.2022.108544
She TGuo ZYang K(2022)Scheduling Constrained-Deadline Tasks in Precise Mixed-Criticality Systems on a Varying-Speed ProcessorProceedings of the 30th International Conference on Real-Time Networks and Systems10.1145/3534879.3534897(94-102)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3534879.3534897
Zhao QQu MGu ZZeng H(2022)Minimizing Stack Memory for Partitioned Mixed-criticality Scheduling on Multiprocessor PlatformsACM Transactions on Embedded Computing Systems10.1145/350670321:2(1-30)Online publication date: 4-Mar-2022
https://dl.acm.org/doi/10.1145/3506703
Yang CWang HZhang JZuo L(2022)Semi-partitioned scheduling of mixed-criticality system on multiprocessor platformsThe Journal of Supercomputing10.1007/s11227-021-04101-y78:5(6386-6410)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11227-021-04101-y
Behera L(2022)MCDPS: An Improved Global Scheduling Algorithm for Multiprocessor Mixed-Criticality SystemsDistributed Computing and Intelligent Technology10.1007/978-3-030-94876-4_10(157-162)Online publication date: 19-Jan-2022
https://dl.acm.org/doi/10.1007/978-3-030-94876-4_10
Wang WMao CZhao SCao YYi YChen SLiu Q(2021)A Smart Semipartitioned Real-Time Scheduling Strategy for Mixed-Criticality Systems in 6G-Based Edge ComputingWireless Communications & Mobile Computing10.1155/2021/66631992021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/6663199
She TVaidhun SGu QDas SGuo ZYang K(2021)Precise Scheduling of Mixed-Criticality Tasks on Varying-Speed MultiprocessorsProceedings of the 29th International Conference on Real-Time Networks and Systems10.1145/3453417.3453428(134-143)Online publication date: 7-Apr-2021
https://dl.acm.org/doi/10.1145/3453417.3453428
Medina RBorde EPautet L(2021)Generalized Mixed-Criticality Static Scheduling for Periodic Directed Acyclic Graphs on Multi-Core ProcessorsIEEE Transactions on Computers10.1109/TC.2020.299022970:3(457-470)Online publication date: 9-Feb-2021
https://dl.acm.org/doi/10.1109/TC.2020.2990229
Gavriluţ VPop P(2020)Traffic-type Assignment for TSN-based Mixed-criticality Cyber-physical SystemsACM Transactions on Cyber-Physical Systems10.1145/33717084:2(1-27)Online publication date: 21-Jan-2020
https://dl.acm.org/doi/10.1145/3371708
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents