Cluster-based multicore real-time mixed-criticality scheduling
Pages 45 - 58
Abstract
A cluster-based scheduling approach is proposed, to schedule the mixed-criticality task sets on multicore processors.This approach uses smaller cluster sizes (sub-cluster) in low criticality mode, and relatively larger cluster sizes in high criticality mode, for better processor utilization.A new task allocation scheme is proposed that allocates all mixed criticality tasks to subclusters in low criticality mode, and also allocates high criticality tasks to the clusters for high criticality mode scheduling.For schedulability analysis, a fixed-priority response time analysis based on Audsleys approach is used for each sub-cluster and cluster of mixed-criticality tasks.Experiments with randomly generated task sets showed that the proposed cluster-based scheduling approach performed better than partitioned and global mixed-criticality scheduling approaches. Cluster-based scheduling is recently gaining importance to be applied to mixed-criticality real-time systems on multicore processors platform. In this approach, the cores are grouped into clusters, and tasks that are partitioned among different clusters are scheduled by global scheduler in each cluster. This research work introduces a new cluster-based task allocation scheme for the mixed-criticality real-time task sets on multicore processors. For task allocation, smaller clusters sizes (sub-clusters) are used for mixed-criticality tasks in low criticality mode, while relatively larger cluster sizes are used for high criticality tasks in high criticality mode. In this research paper, the mixed-criticality task set is allocated to clusters using worst-fit heuristic. The tasks from each cluster are also allocated to its sub-clusters, using the same worst-fit heuristic. A fixed-priority response time analysis approach based on Audsleys approach is used for the schedulability analysis of tasks in each cluster and sub-cluster. If the high criticality job is not completed after its worst case execution time in low mode, then the system is switched to high criticality mode. After mode switch, all the low criticalities tasks are discarded and only high criticality tasks are further executed in high criticality mode. Simulation results indicate that the percentage of schedulable task sets significantly increases under cluster scheduling as compared to partitioned and global mixed-criticality scheduling schemes.
References
[1]
ARINC653 - An Avionics Standard for Safe, Partitioned Systems, Wind river systems/IEEE seminar, 2008.
[2]
R. Davis, A. Burns, A survey of hard real-time scheduling for multiprocessor systems, ACM Comput. Surv., 43, 2011.
[3]
J.M. Lopez, M. Garcia, J.L. Diaz, D.F. Garcia, Utilization bounds for multiprocessor rate-monotonic systems, Real-Time Syst. 24 (January) (2003) 5-28.
[4]
S.K. Dhall, C.L. Liu, On a real-time scheduling problem, Oper. Res. 26 (January/February) (1978) 127-140.
[5]
G. Nelissen, V. Berten, J. Goossens, D. Milojevic, Reducing preemptions and migrations in real-time multiprocessor scheduling algorithms by releasing the fairness, in: RTCSA11, 2011, pp. 15-24.
[6]
G. Nelissen, V. Berten, V. Nelis, J. Goossens, D. Milojevic, U-EDF: an unfair but optimal multiprocessor scheduling algorithm for sporadic tasks, ECRTS12, 2012.
[7]
P. Regnier, G. Lima, E. Massa, G. Levin, S. Brandt, RUN: Optimal multiprocessor real-time scheduling via reduction to uniprocessor, in: RTSS 11, 2011, pp. 104-115.
[8]
E. Massa, G. Lima, P. Regnier, G. Levin, S. Brandt, Optimal and adaptive multiprocessor real-time scheduling: the quasi-partitioning approach, in: ECRTS14, 2014, pp. 291-300.
[9]
N. Audsley, Optimal priority assignment and feasibility of static priority tasks with arbitrary start times, Tech. Rep., University of York, England, 1991.
[10]
J.W.S. Liu, Real-time systems, Upper Saddle River, NJ: Prentice Hall, 2000.
[11]
Vestal, Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance, in: Proc. of RTSS, 2007, pp. 239-243.
[12]
F. Dorin, P. Richard, M. Richard, J. Goossens, Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities, Real-Time Syst. 46 (December) (2010) 305-331.
[13]
S. Baruah, A. Burns, R. Davis, Response-time analysis for mixed criticality systems, in: Proc. of RTSS, 2011, pp. 34-43.
[14]
S. Baruah, H. Li, L. Stougie, Towards the design of certifiable mixed-criticality systems, in: Proc. of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2010.
[15]
D. Socci, P. Poplavko, S. Bensalem, M. Bozga, Mixed critical earliest deadline first, ECRTS, 2013.
[16]
Z. Guo, S. Baruah, Implementing mixed-criticality systems upon a preemptive varying-speed processor, Leibniz Trans. Embedded Syst. (LITES) 1 (2) (2014). 3:1-3:19.
[17]
Z. Guo, S. Baruah, The concurrent consideration of uncertainty in WCET and processor speeds in mixed-criticality systems, RTNS, 2015.
[18]
S. Baruah, V. Bonifaci, G.D. Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, L. Stougie, Scheduling real-time mixed- criticality jobs, in: IEEE Transactions on Computation, 61, 2012, pp. 1140-1152.
[19]
H. Li, S. Baruah, An algorithm for scheduling certifiable mixed criticality sporadic task systems, in: Proc. of the 31st IEEE Real-Time Systems Symposium (RTSS), 2010.
[20]
N. Guan, P. Ekberg, M. Stigge, W. Yi, Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems, in: Proc. of RTSS, 2011, pp. 13-23.
[21]
O.R. Kelly, H. Aydin, B. Zhao, On partitioned scheduling of fixed-priority mixed-criticality task sets, in: Proc. of the 10th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (IEEE TrustCom-11), 2011.
[22]
C. Gu, N. Guan, Q. Deng, W. yi, Partitioned mixed-criticality scheduling on multiprocessor platforms, in: Proc. of DATE14, 2014.
[23]
P. Ekberg, W. Yi, Bounding and shaping the demand of generalized mixed-criticality sporadic tasks systems, Springer Science + Business Media, New York, 2013.
[24]
P. Ekberg, W. Yi, Bounding and shaping the demand of mixed-criticality sporadic tasks, in: Proc. of ECRTS, 2012.
[25]
Pathan, Schedulability analysis of mixed-criticality systems on multiprocessors, in: Proc. of ECRTS, 2012.
[26]
H. Li, S. Baruah, Global mixed-criticality scheduling on multiprocessors, in: Proc. of ECRTS, 2012.
[27]
S.K. Baruah, V. Bonifaci, G. DAngelo, A. Marchetti-Spaccamela, S. van der Ster, L. Stougie, Mixed-criticality scheduling of sporadic task systems, in, in: Proceedings of the 19th Annual European Symposium on Algorithms, Saarbrucken, Germany, September, Springer-Verlag, 2011, pp. 555-566.
[28]
S. Baruah, Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors, IEEE Trans. Comput. 53 (6) (2004).
[29]
A. Bastoni, B.B. Brandenburg, J.H. Anderson, An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers, in: Proc. of RTSS, 2010.
[30]
J. Calandrino, J. Anderson, D. Baumberger, A hybrid real-time scheduling approach for large-scale multicore platforms, in: Proc. of the 19th Euromicro Conf. on Real-Time Sys, 2007, pp. 247-256.
[31]
I. Shin, A. Easwaran, I. Lee, Hierarchical scheduling framework for virtual clustering of multiprocessors, in: Proceedings of the 20th Euromicro Conference on Real-Time Systems, Jul., 2008.
[32]
I. Shin, A. Easwaran, I. Lee, Optimal virtual cluster-based multiprocessor scheduling, in: Springer Real-Time Systems, 43, 2009, pp. 25-59.
[33]
X. Qi, D. Zhu, H. Aydin, A study of utilization bound and run-time overhead for cluster scheduling in multiprocessor real-time systems, in Proc. of RTCSA (2010).
[34]
X. Qi, D. Zhu, H. Aydin, Cluster scheduling for real-time systems: utilization bounds and run-time overhead, Real-Time Syst. (2011) 253-284.
[35]
D. Zhu, D. Mosse, R. Melhem, Periodic multiple resource scheduling problem: how much fairness is necessary, in: Proc. of the 24th IEEE Real-Time Systems Symposium (RTSS), Dec, 2003, pp. 142-151.
[36]
D. Zhu, X. Qi, D. Mosse, R. Melhem, An optimal boundary-fair scheduling algorithm for multiprocessor real-time systems., Technical report, 2009.
[37]
S. Baruah, B. Chattopadhyay, H. Li, I. Shin, Mixed-criticality scheduling on multiprocessors, Real-Time Syst. (2014) 142-177.
[38]
N. Audsley, A. Burns, M. Richardson, K. Tindell, A. Wellings, Applying new scheduling theory to static priority preemptive scheduling, Software Eng. J. 8 (5) (1993) 284-292.
[39]
N. Guan, M. Stigge, W. Yi, G. Yu, New response time bounds for fixed priority multiprocessor scheduling, Proc. of RTSS (2009) 387-397.
[40]
B. Andersson, S. Baruah, J. Jonsson, Static-priority scheduling on multiprocessors, in: RTSS, London, UK, 2001, pp. 193-202.
[41]
M. Bertogna, Real-time scheduling for multiprocessor platforms, phd thesis, scuola superiore santanna, pisa, 2007.
[42]
A. Bastoni, B. Brandenburg, J. Anderson, Cache-related preemption and migration delays: empirical approximation and impact on schedulability, in: Proc. of OSPERT, 2010, pp. 33-44.
- Cluster-based multicore real-time mixed-criticality scheduling
Recommendations
Compositional Real-Time Scheduling of Mixed-Criticality Real-Time Systems
DASC '14: Proceedings of the 2014 IEEE 12th International Conference on Dependable, Autonomic and Secure ComputingCompositional real-time scheduling frameworks provide ways for building large and complex real-time embedded systems from independent sub-systems. This paper introduces a novel scheme for scheduling a component of Mixed-Criticality (MC) sporadic tasks ...
Mixed-criticality federated scheduling for parallel real-time tasks
A mixed-criticality system comprises safety-critical and non-safety-critical tasks sharing a computational platform. Thus, different levels of assurance are required by different tasks in terms of real-time performance. As the computational demands of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier North-Holland, Inc.
United States
Publication History
Published: 01 September 2017
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024