ILP Approach for Periodic Dependent Tasks in Multicore Mixed-criticality systems

Document Type : Original Article

Authors

Department of Computer Engineering, Qom University of Technology, Qom, Iran

Abstract

Today, the desire to use mixed-critical systems in the industry is increasing. In order to provide the processing power required by mixed-critical systems, multi-core architectures are considered a suitable option. One of the main challenges in mixed-critical systems is task scheduling, which is even more challenging in multi-core architectures. Many studies of task scheduling in mixed-critical multi-core systems have dealt with the scheduling of independent tasks. But in many real systems, tasks are dependent on each other. In this research, we will deal with the scheduling of dependent periodic tasks in mixed-critical multi-core systems in such a way that the presented schedule satisfies the system constraints. The proposed algorithm provides the best possible schedule using linear programming. The results of the experiments showed that the presented method has been able to significantly reduce the number of preemptions while maintaining the scheduling capability.

Keywords

References

[1] S. Baruah, Mixed-Criticality Scheduling Theory: Scope, Promise, and Limitations, IEEE Des. Test, 35(2) 2018, 31-37.
[2] S. Baruah, Implementing mixed-criticality synchronous reactive programs upon uniprocessor platforms, Real-Time Systems, 50(3) 2014, 317-341.
[3] S. Baruah, Semantics-preserving implementation of multirate mixed-criticality synchronous programs, in Proceedings of the 20th International Conference on Real-Time and Network Systems, 2012, 11-19.
[4] S. Baruah, Implementing mixed criticality synchronous reactive systems upon multiprocessor platforms, The University of North Carolina at Chapel Hill, Tech. Rep, 2013.
[5] S. Baruah, The federated scheduling of systems of mixed-criticality sporadic DAG tasks, in 2016 IEEE Real-Time Systems Symposium (RTSS), 2016: IEEE, 227-236.
[6] S. Baruah et al., Scheduling real-time mixed-criticality jobs, IEEE Transactions on Computers, 61(8) 2011, 1140-1152.
[7] S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M.H. Su, K. Vahi, Characterization of scientific workflows, in 2008 third workshop on workflows in support of large-scale science, 2008: IEEE, pp. 1-10.
[8] E. Bini, G.C. Buttazzo, Measuring the performance of schedulability tests, Real-Time Systems, 30(1-2) 2005, 129-154.
[9] A. Burns and R. Davis, Mixed criticality systems-a review, Department of Computer Science, University of York, Tech. Rep, 2013, 1-69.
[10] G.C. Buttazzo, Hard real-time computing systems: predictable scheduling algorithms and applications. Springer Science & Business Media, 2011.
[11] F. Cadoret, T. Robert, E. Borde, L. Pautet, F. Singhoff, Deterministic implementation of periodic-delayed communications and experimentation in aadl, in 16th IEEE International Symposium on Object/component/service-oriented Real-time distributed Computing (ISORC 2013), 2013: IEEE, 1-8.
[12] D. Cordeiro, G. Mounié, S. Perarnau, D. Trystram, J.M. Vincent, F. Wagner, Random graph generation for scheduling simulations, in 3rd International ICST Conference on Simulation Tools and Techniques (SIMUTools 2010), 2010, ICST,10.
[13] R. I. Davis, A. Burns, Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems, in 2009 30th IEEE Real-Time Systems Symposium, 2009: IEEE, 398-409.
[14] J. Lee et al., MC-Fluid: Fluid model-based mixed-criticality scheduling on multiprocessors, in 2014 IEEE Real-Time Systems Symposium, 2014: IEEE, 41-52.
[15] H. Li, S. Baruah, Outstanding paper award: Global mixed-criticality scheduling on multiprocessors, 24th Euromicro Conference on Real-Time Systems, 2012: IEEE, 166-175.
[16] J. Li, D. Ferry, S. Ahuja, K. Agrawal, C. Gill, C. Lu, Mixed-criticality federated scheduling for parallel real-time tasks, Real-time systems, 53(5) 2017, 760-811.
[17] P. Marwedel, Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things. Springer, 2017.
[18] R. Medina, E. Borde, L. Pautet, Directed acyclic graph scheduling for mixed-criticality systems, in Ada-Europe International Conference on Reliable Software Technologies, 2017: Springer, 217-232.
[19] R. Medina, E. Borde, and L. Pautet, Scheduling multi-periodic mixed-criticality dags on multi-core architectures, in 2018 IEEE Real-Time Systems Symposium (RTSS), 2018: IEEE, 254-264.
[20] R. Medina, E. Borde, L. Pautet, Generalized Mixed-Criticality Static Scheduling for Periodic Directed Acyclic Graphs on Multi-Core Processors, IEEE Transactions on Computers, 2020.
[21] M. Mitchell, An introduction to genetic algorithms. MIT Press, 1998.
[22] R. M. Pathan, Schedulability analysis of mixed-criticality systems on multiprocessors, in 2012 24th Euromicro Conference on Real-Time Systems, 2012: IEEE, 309-320.
[23] R. M. Pathan, Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors, in 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), 2018: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[24] S. Siebert, J. Teizer, Mobile 3D mapping for surveying earthwork projects using an Unmanned Aerial Vehicle (UAV) system, Automation in construction, 41 2014, 1-14.
[25] S. Vestal, Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance, in 28th IEEE international real-time systems symposium (RTSS 2007), 2007: IEEE, 239-243.
[26] T. Yang, Y. Tang, X. Jiang, Q. Deng, and N. Guan, Semi-Federated Scheduling of Mixed-Criticality System for Sporadic DAG Tasks, in 2019 IEEE 22nd International Symposium on Real-Time Distributed Computing (ISORC), 2019: IEEE, 163-170.
[27] H.E. Zahaf, G. Lipari, S. Niar, Preemption-Aware Allocation, Deadline Assignment for Conditional DAGs on Partitioned EDF, in 2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 2020: IEEE, 1-10.
Mathematics and Computational Sciences
Volume 3, Issue 4
December 2022
Pages 33-45

Files

History

  • Receive Date: 30 November 1999
  • Accept Date: 30 November 1999
  • First Publish Date: 01 December 2022

Share

How to cite

Statistics