Generic placeholder image

International Journal of Sensors, Wireless Communications and Control

Author(s): Ajitesh Kumar* and Sanjai Kumar Gupta

DOI: 10.2174/2210327912666220105141851

DownloadDownload PDF Flyer Cite As
A Systematic Survey of Multiprocessor Real-Time Scheduling and Synchronization Protocol

Page: [212 - 229] Pages: 18

  • * (Excluding Mailing and Handling)

Explore Articles
About Journal
For Authors
For Editors
For Reviewers

Abstract

Background: Nowadays, there is an immense increase in the demand for high power computation of real-time workloads and the trend towards multi-core and multiprocessor CPUs. The realtime system needs to be implemented upon multiprocessor platforms.

Introduction: The nature of processors in an embedded real-time system is changing day by day. The two most significant challenges in a multiprocessor environment are scheduling and synchronization. The popularity of real-time multi-core systems has exploded in recent years, driving the rapid development of a variety of methods for multiprocessor scheduling of essential tasks; on the other hand; these systems have constraints when it comes to maintaining synchronization in order to access shared resources.

Methods: This research work presents a systematic review of different existing scheduling algorithms and synchronization protocols for shared resources in a real-time multiprocessor environment. The manuscript also presents a study based on various metrics of resource scheduling and comparison among different resource scheduling techniques.

Conclusion: The survey classifies open issues, key challenges, and likely useful research directions. Finally, we accept that there is still a lot of capacity in developing better resource management and further maintaining the overall quality. The paper considers such a future path of research in this field.

Keywords: MPRTS, WCET, migration, blocking time, synchronization, RTOS.

Graphical Abstract

[1]
Alfranseder M, Deubzer M, Justus B, Mottok J, Siemers C. An efficient spin-lock based multi-core resource sharing protocol. IEEE 33rd International Performance Computing and Communications Conference (IPCCC). 1-7.
[2]
Al-Bayati Z, Sun Y, Zeng H, Natale MD, Zhu Q, Meyer BH. Partitioning and selection of data consistency mechanisms for multi-core real-time systems. ACM Trans Embed Comput Syst 2019; 18(4): 1-28.
[http://dx.doi.org/10.1145/3320271]
[3]
Baruah SK. The non-preemptive scheduling of periodic tasks upon multiprocessors. Real-Time Syst 2006; 32(1-2): 9-20.
[http://dx.doi.org/10.1007/s11241-006-4961-9]
[4]
Brandenburg BB. Multiprocessor real-time locking protocols: A systematic review. arXiv preprint arXiv:190909600 2019.
[http://dx.doi.org/10.1007/s11241-006-4961-9]
[5]
Brandenburg BB, Anderson JH. The OMLP family of optimal multiprocessor real-time locking protocols. Des Autom Embed Syst 2013; 17(2): 277-342.
[http://dx.doi.org/10.1007/s10617-012-9090-1]
[6]
Biondi A, Buttazzo GC, Bertogna M. Supporting component-based development in partitioned multiprocessor real-time systems. 27th Euromicro Conference on Real-Time Systems 2015; 269-80.
[http://dx.doi.org/10.1109/ECRTS.2015.31]
[7]
Baek H, Shin KG, Lee J. Response-time analysis for multi-mode tasks in real-time multiprocessor systems IEEE Access 2020
[http://dx.doi.org/10.1109/ACCESS.2020.2992868]
[8]
Buttazzo GC, Bertogna M, Yao G. Limited preemptive scheduling for real-time systems. a survey. IEEE Trans Industr Inform 2012; 9(1): 3-15.
[http://dx.doi.org/10.1109/TII.2012.2188805]
[9]
Brandenburg BB. A fully preemptive multiprocessor semaphore protocol for latency-sensitive real-time applications. 2013 25th Euromicro Conference on Real-Time Systems 2013; 292-302.
[http://dx.doi.org/10.1109/ECRTS.2013.38]
[10]
Brandenburg BB, Anderson JH. An implementation of the pcp, srp, d-pcp, m-pcp, and FMLP real-time synchronization protocols in litmus^ rt. 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications 2008; 185-94.
[11]
Baker TP. An analysis of EDF schedulability on a multiprocessor. IEEE Trans Parallel Distrib Syst 2005; 16(8): 760-8.
[http://dx.doi.org/10.1109/TPDS.2005.88]
[12]
Block A, Leontyev H, Brandenburg BB, Anderson JH. A flexible real-time locking protocol for multiprocessors. 13th IEEE international conference on embedded and real-time computing systems and applications (RTCSA 2007). 2007; 47-56.
[http://dx.doi.org/10.1109/RTCSA.2007.8]
[13]
Chen JJ. von der BrA1/4ggen G, Shi J, Ueter N Dependency graph approach for multiprocessor real-time synchronization 2018 IEEE Real-Time Systems Symposium (RTSS) 434-46.
[http://dx.doi.org/10.1109/RTSS.2018.00057]
[14]
Chen JJ, Nelissen G, Huang WH, et al. Many suspensions, many problems: a review of self-suspending tasks in real-time systems. Real-Time Syst 2019; 55(1): 144-207.
[http://dx.doi.org/10.1007/s11241-018-9316-9]
[15]
Carminati A, De Oliveira RS, Friedrich LF. Exploring the design space of multiprocessor synchronization protocols for real-time systems. J Systems Archit 2014; 60(3): 258-70.
[http://dx.doi.org/10.1016/j.sysarc.2013.11.010]
[16]
Capota EA, Stangaciu CS, Micea MV, Cretu VI. P_FENP: A multiprocessor real-time scheduling algorithm. 2018 IEEE 12th International Symposium on Applied Computational Intelligence and Informatics (SACI). 2018; 000509-14.
[17]
Cho H, Ravindran B, Jensen ED. Utility accrual real-time scheduling for multiprocessor embedded systems. J Parallel Distrib Comput 2010; 70(2): 101-10.
[http://dx.doi.org/10.1016/j.jpdc.2009.10.003]
[18]
Chai H, Zhang G, Sun J, Vajdi A, Hua J, Zhou J. A review of recent techniques in mixed-criticality systems. J Circuits Syst Comput 2019; 28(07): 1930007.
[http://dx.doi.org/10.1142/S0218126619300071]
[19]
Dahal K, Hossain A, Varghese B, Abraham A, Xhafa F, Daradoumis A. Scheduling in a multiprocessor system using genetic algorithms. In: 2008 7th Computer Information Systems and Industrial Management Applications. IEEE 2008; pp. 281-6.
[20]
Davis RI, Burns A. A survey of hard real-time scheduling for multiprocessor systems. ACM computing surveys (CSUR) 2011; 43(4): 1-44..
[http://dx.doi.org/10.1145/1978802.1978814]
[21]
Dos Santos LM, Gracioli G, Kloda T, Caccamo M. On the design and implementation of real-time resource access protocols. 2020 X Brazilian Symposium on Computing Systems Engineering (SBESC). 1-8.
[22]
Devaraj R. A solution to drawbacks in capturing execution requirements on heterogeneous platforms. J Supercomput 2020; 1-16.
[http://dx.doi.org/10.1007/s11227-020-03145-w]
[23]
Da Silva EC, Gabriel PH. A comprehensive review of evolutionary algorithms for multiprocessor DAG scheduling. Computation (Basel) 2020; 8(2): 26.
[http://dx.doi.org/10.3390/computation8020026]
[24]
Elliott GA, Anderson JH. An optimal k-exclusion real-time locking protocol motivated by multi-GPU systems. Real-Time Syst 2013; 49(2): 140-70.
[http://dx.doi.org/10.1007/s11241-012-9170-0]
[25]
Faggioli D, Lipari G, Cucinotta T. The multiprocessor bandwidth inheritance protocol. 22nd Euromicro Conference on Real-Time Systems 2010; 90-9.
[http://dx.doi.org/10.1109/ECRTS.2010.19]
[26]
Gomes RM. Analysis of MrsP protocol in RTEMS operating system. Doctoral dissertation 2019.
[27]
Ganjaliyev F. Spin-then-sleep: A machine learning alternative to queue-based spin-then-block strategy. In: Spin. 2019; 10(3).
[http://dx.doi.org/10.14569/IJACSA.2019.0100377]
[28]
Habibah I, Dayang NJ, Ismail A, Adham IM. Evaluation of the proposed hybrid multiprocessor real-time scheduling approach with partitioned and global approaches. In: MATEC web of conferences. EDP Sciences 2019; 255: p. 05004.
[http://dx.doi.org/10.1051/matecconf/201925505004]
[29]
Hangan A, Sebestyen G, Vacariu L. Multiprocessor real-time scheduling using an optimization-based technique. In: IJCCI (ECTA). 2014; pp. 236-43.
[http://dx.doi.org/10.5220/0005076202360243]
[30]
Han JJ, Wang Z, Gong S, Miao T, Yang LT. Resource-aware scheduling for dependable multicore real-time systems: Utilization bound and partitioning algorithm. IEEE Trans Parallel Distrib Syst 2019; 30(12): 2806-19.
[http://dx.doi.org/10.1109/TPDS.2019.2926455]
[31]
Huang WH, Yang M, Chen JJ. Resource-oriented partitioned scheduling in multiprocessor systems: How to partition and how to share? 2016 IEEE Real-Time Systems Symposium (RTSS). 2016; 111-22.
[http://dx.doi.org/10.1109/RTSS.2016.020]
[32]
Hsiu PC, Lee DN, Kuo TW. Task synchronization and allocation for many-core real-time systems. Proceedings of the ninth ACM interna-tional conference on Embedded software 79-88.
[http://dx.doi.org/10.1145/2038642.2038656]
[33]
Jarrett CE, Ward BC, Anderson JH. A contention-sensitive fine-grained locking protocol for multiprocessor real-time systems. Proceedings of the 23rd International Conference on Real Time and Networks Systems. 3-12.
[http://dx.doi.org/10.1145/2834848.2834874]
[34]
Jiang X, Guan N, Tang Y, Liu W, Duan H. Suspension-based locking protocols for parallel real-time tasks. 2019 IEEE Real-Time Systems Symposium (RTSS). 274-86.
[http://dx.doi.org/10.1109/RTSS46320.2019.00033]
[35]
Jiang X, Guan N, Du H, Liu W, Yi W. On the analysis of parallel real-time tasks with spin locks. arXiv preprint arXiv:200308233
[36]
LA3pez JM, DA-az JL, GarcA-a DF. Utilization bounds for EDF scheduling on real-time multiprocessor systems. Real-Time Syst 2004; 28(1): 39-68.
[http://dx.doi.org/10.1023/B:TIME.0000033378.56741.14]
[37]
Lee H, Lee J. Limited non-preemptive EDF scheduling for a real-time system with symmetry multiprocessors. Symmetry (Basel) 2020; 12(1): 172.
[http://dx.doi.org/10.3390/sym12010172]
[38]
Lee J, Kim M. Ceiling priority for synchronous communication in real-time systems. Electronic and Automation Control Conference (IT-NEC). 1: 617-22.
[http://dx.doi.org/10.1109/ITNEC48623.2020.9084783]
[39]
Lee J, Easwaran A, Shin I, Lee I. Multiprocessor real-time scheduling considering concurrency and urgency. ACM SIGBED Review 2010; 7(1): 1-5.
[http://dx.doi.org/10.1145/1851166.1851173]
[40]
Mahmood A, Khan SA, Albalooshi F, Awwad N. Energy-aware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm. Electronics (Basel) 2017; 6(2): 40.
[http://dx.doi.org/10.3390/electronics6020040]
[41]
Massa E, Lima G, Regnier P, Levin G, Brandt S. Quasi-partitioned scheduling: optimality and adaptation in multiprocessor real-time sys-tems. Real-Time Syst 2016; 52(5): 566-97.
[http://dx.doi.org/10.1007/s11241-016-9251-6]
[42]
Nemati F, Behnam M, Nolte T. Independently-developed real-time systems on multi-cores with shared resources. 2011 23rd Euromicro Conference on Real-Time Systems. 2011; 251-61.
[http://dx.doi.org/10.1109/ECRTS.2011.31]
[43]
Nemitz CE, Amert T, Anderson JH. Real-time multiprocessor locks with nesting: Optimizing the common case. Real-Time Syst 2019; 55(2): 296-348.
[http://dx.doi.org/10.1007/s11241-019-09328-w]
[44]
Nemitz CE, Amert T, Goyal M, Anderson JH. Concurrency groups: a new way to look at real-time multiprocessor lock nesting. Proceedings of the 27th International Conference on Real-Time Networks and Systems. 187-97.
[http://dx.doi.org/10.1145/3356401.3356404]
[45]
Nemitz CE. A preliminary examination of schedulability under lock servers. th Junior Researcher Workshop on Real-Time Computing.
[46]
Nemitz CE, Yang K, Yang M, Ekberg P, Anderson JH. Multiprocessor real-time locking protocols for replicated resources. 2016 28th Euromicro Conference on Real-Time Systems (ECRTS) 50-60.
[http://dx.doi.org/10.1109/ECRTS.2016.29]
[47]
Patel P, Baek I, Kim H, Rajkumar R. Analytical enhancements and practical insights for mpcp with self-suspensions. 2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) 2018; 177-89.
[http://dx.doi.org/10.1109/RTAS.2018.00027]
[48]
Regnier P, Lima G, Massa E, Levin G, Brandt S. Run: Optimal multiprocessor real-time scheduling via reduction to uniprocessor. 2011 IEEE 32nd Real-Time Systems Symposium 2011; 104-15.
[49]
Str A. m TB, SparsA, J, Schoeberl M. Hardlock: Real-time multi-core locking. J Systems Archit 2019; 97: 467-76.
[http://dx.doi.org/10.1016/j.sysarc.2019.02.003]
[50]
Shi J, Chen KH, Zhao S, Huang WH, Chen JJ, Wellings A. Implementation and evaluation of multiprocessor resource synchronization protocol (MrsP) on LITMUSRT. 13th Workshop on Operating Systems Platforms for Embedded Real-Time Applications.
[51]
Safaei AA, Alemi M, Haghjoo MS, Mohammadi S. Hybrid multiprocessor real-time scheduling approach. International Journal of Com-puter Science Issues (IJCSI) 2011; 8(2): 171.
[52]
Teixeira R, Lima G. Improved task packing for shared resources in multiprocessor real-time systems scheduled by RUN under SBLP. 2019 IX Brazilian Symposium on Computing Systems Engineering (SBESC) 2019; 1-8.
[http://dx.doi.org/10.1109/SBESC49506.2019.9046074]
[53]
Ward BC, Elliott GA, Anderson JH. Replica-request priority donation: A real-time progress mechanism for global locking protocols. 2012 IEEE International Conference on Embedded and Real-Time Computing Systems and Applications 2012; 280-9.
[http://dx.doi.org/10.1109/RTCSA.2012.26]
[54]
Ward BC, Anderson JH. Supporting nested locking in multiprocessor real-time systems. 2012 24th Euromicro Conference on RealTime Systems. 2012; 223-32.
[http://dx.doi.org/10.1109/ECRTS.2012.17]
[55]
Yang M, Huang WH, Chen JJ. Resource-oriented partitioning for multiprocessor systems with shared resources. IEEE Trans Comput 2018; 68(6): 882-98.
[http://dx.doi.org/10.1109/TC.2018.2889985]
[56]
Yang K. Multiprocessor real-time locking protocols: from homogeneous to heterogeneous. University of North Carolina
[57]
Zhu D, Qi X. MossA(c) D, Melhem R. An optimal boundary fair scheduling algorithm for multiprocessor real-time systems. J Parallel Distrib Comput 2011; 71(10): 1411-25.
[http://dx.doi.org/10.1016/j.jpdc.2011.06.003]
[58]
Zeng G, Matsubara Y, Tomiyama H, Takada H. Energy-aware task migration for multiprocessor real-time systems. Future Gener Comput Syst 2016; 56: 220-8.
[http://dx.doi.org/10.1016/j.future.2015.07.008]
[59]
Zhao S, Garrido J, Wei R, Burns A, Wellings A, Juan A. A complete run-time overhead-aware schedulability analysis for MrsP under nest-ed resources. J Syst Softw 2020; 159: 110449.
[http://dx.doi.org/10.1016/j.jss.2019.110449]
[60]
Zhang X, Urban C, Wu C. Priority inheritance protocol proved correct. J Autom Reason 2020; 64(1): 73-95.
[http://dx.doi.org/10.1007/s10817-019-09511-5]