An optimal semi-partitioned algorithm for scheduling real-time applications on uniform multicore processors

Roy, 2020, Contention-aware optimal scheduling of real-time precedence-constrained task graphs on heterogeneous distributed systems, J. Syst. Archit., 105, 10.1016/j.sysarc.2019.101706 Chang, 2020, Real-time scheduling and analysis of parallel tasks on heterogeneous multi-cores, J. Syst. Archit., 105, 10.1016/j.sysarc.2019.101704 Jiang, 2020, Real-time scheduling of parallel tasks with tight deadlines, J. Syst. Archit., 108, 10.1016/j.sysarc.2020.101742 Sun, 2019, Pessimism in multicore global schedulability analysis, J. Syst. Archit., 97, 142, 10.1016/j.sysarc.2018.12.006 Rupanetti, 2019, Task allocation, migration and scheduling for energy-efficient real-time multiprocessor architectures, J. Syst. Archit., 98, 17, 10.1016/j.sysarc.2019.06.003 Chronaki, 2019, On the maturity of parallel applications for asymmetric multi-core proces-sors, J. Parallel Distrib. Comput., 127, 105, 10.1016/j.jpdc.2019.01.007 Xu, 2019, A semi-partitioned model for mixed criticality systems, J. Syst. Softw., Volume 150, 51, 10.1016/j.jss.2019.01.015 Derafshi, 2020, HRHS: a high-performance real-time hardware scheduler, IEEE Trans. Parallel Distrib. Syst., vol. 31, 897, 10.1109/TPDS.2019.2952136 Maiza, 2019, A Survey of Timing Verification Techniques for Multi-Core Real-Time Systems, ACM Comput. Surv. Moulik, 2020, HEARS: a heterogeneous energy-aware real-time scheduler, Microprocess. Microsyst., Volume 72, 10.1016/j.micpro.2019.102939 Davis, 2011, A survey of hard real-time scheduling for multiprocessor, ACM Comput. Surv., vol. 43, 1, 10.1145/1978802.1978814 Liu, 1973, Scheduling algorithms for multiprogramming in a hard real-time environment, J. ACM, 20, 40, 10.1145/321738.321743 Leung, 1982, On the complexity of fixed-priority scheduling of periodic real-time tasks, Perform. Eval., 2, 237, 10.1016/0166-5316(82)90024-4 N. Guan, M. Stigge, W. Yi, G. Yu, Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling, 2012 IEEE 26th International Parallel and Distributed Processing Symposium, 2012, pp. 261–272, doi: 10.1109/IPDPS.2012.33. Li, 2021, Comprehensive study of schedulability tests and optimal design for rate-monotonic scheduling, Comput. Commun., Volume 173, 107, 10.1016/j.comcom.2021.03.013 Kuo, T.-W., Mok, A., 1991. Load adjustment in adaptive real-time systems. In: Proc. Real-Time Systems Symposium, 1991, Twelfth, pp. 160–170, http://dx.doi.org/10.1109/REAL.1991.160369. Han, C.-C., Tyan, H.-Y., 1997. A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms. In: Proc. IEEE Real-Time Systems Symposium (RTSS), http://dx.doi.org/10.1109/REAL.1997.641267. Enrico Bini, 2003, Rate monotonic analysis: the hyperbolic bound, IEEE Trans. Comput 52, 7, 933, 10.1109/TC.2003.1214341 Audsley, 1993, Applying new scheduling theory to static priority preemptive scheduling, Softw. Eng. J., 8, 80 Anderson, 2005, An EDF-based scheduling algorithm for multiprocessor soft real-time systems, 17th ECRTS K. Lakshmanan, S. Kato, R. Raj-kumar, Scheduling Parallel Real-time Tasks on Multi-core Processors, Proc. IEEE Symp. Real-time Systems (RTSS), pp. 259–268, Nov. 2010. N. Guan, M. Stigge, W. Yi, G. Yu. 2010. Fixed-priority multiprocessor scheduling with liu and layland’s utilization bound. In Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium on Systems, Ser. RTAS’10 (April 2010), 165–174. Xu, 2010 Mahmoud Naghibzadeh, Peyman Neamatollahi, Reza Ramezani, Amin Rezaeian, Toktam Dehghani. 2013. Efficient semi-partitioning and rate-monotonic scheduling hard real-time tasks on multi-coresystems. In Proceedings of the 8th IEEE International Symposium on Industrial Embedded Systems.(SIES) ser. RTSS’08 (June 2013). IEEE Computer Society, Washington, DC, 85–88. Hadeer A. Hassan, Sameh A. Salem, Ahmed M. Mostafa, E.M. Saad. 2016. Harmonic segment-based semi-partitioning scheduling for multi-core real-time systems. ACM Trans. Embed. Comput. Syst. 15, 4, Article 73 (August 2016), 29 pages. DOI: http://dx.doi.org/10.1145/2933388. Funk,S., Goossens, J., Baruah, S., On-line Scheduling on Uniform Multiprocessors, In Proceedings of the Real-Time Systems Symposium (RTSS), pp. 183–192, 2001. Baruah, 2003, Rate-monotonic scheduling on uniform multiprocessors, IEEE Trans. Comput., Vol. 52, 966, 10.1109/TC.2003.1214344 Andersson, B., Tovar, E., Competitive Analysis of Partitioned Scheduling on Uniform Multiprocessors, Parallel and Distributed Processing Symposium, International, pp. 147, 2007. Andersson, B., Tovar, E., Competitive Analysis of Static-Priority Partitioned Scheduling on Uniform Multiprocessors, 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), pp. 111–119, 2007. Cucu, L., Goossens, J., Feasibility Intervals for Fixed-Priority Real-Time Scheduling on Uniform Multiprocessors, IEEE Conference on Emerging Technologies and Factory Automation, Prague, pp. 397–404, 2006. Baruah, S., Goossens, J., The EDF Scheduling of Sporadic Task Systems on Uniform Multiprocessors, Real-Time Systems Symposium, pp.367–374, 2008. Calandrino, J.M., Baumberger, D., Li, T., Hahn, S., Anderson, J.H., Soft Real-Time Scheduling on Performance Asymmetric Multicore Platforms, 13th IEEE Real Time and Embedded Technology and Applications Symposium (RTAS'07), Bellevue, WA, pp. 101–112, 2007. Chen, S.Y., Hsueh, C.W., Optimal Dynamic-Priority Real-Time Scheduling Algorithms for Uniform Multiprocessors, Real-Time Systems Symposium, Barcelona, pp. 147–156, 2008. Xiaojian, L., Xiang, L., A-S Algorithm: an Optimal on-line Real-Time Scheduling Algorithm for Uniform Multiprocessors, 3rd IEEE International Conference on "Computational Intelligence and Communication Technology" (IEEE-CICT 2017), 2017. Pathan R.M. Jonsson, J., Parameterized Schedulability Analysis on Uniform Multiprocessors, 39th International Conference on Parallel Processing, San Diego, CA, pp. 323–332, 2010. Jung, M.J., Seong, Y.P., Lee, C.H., Optimal RM Scheduling for Simply Periodic Tasks on Uniform Multiprocessors, In Proceedings of the 2009 International Conference on Hybrid Information Technology (ICHIT '09). ACM, New York, NY, USA, pp.383–389, 2009. S. Bertozzi, A. Acquaviva, D. Bertozzi, A. Poggiali, "Supporting Task Migration in Multi-Processor Systems-on-Chip: A Feasibility Study," Proceedings of the Design Automation & Test in Europe Conference, Munich, 2006, pp. 1–6, doi: 10.1109/DATE.2006.243952. S. Kato, N. Yamasaki, Semi-partitioned Fixed-Priority Scheduling on Multiprocessors, 2009 15th IEEE Real-Time and Embedded Technology and Applications Symposium, San Francisco, CA, 2009, pp. 23–32, doi: 10.1109/RTAS.2009.9. Francis M.David, Jeffrey C.Carlyle, Roy H.Campbell 2007. Context switch overheads for Linux on ARM platforms. In Proceedings of the 2007 workshop on Experimental computer science (ExpCS ’07). Association for Computing Machinery, New York, NY, USA, 3–es. DOI:https://doi.org/10.1145/1281700.1281703.