EvoSMS: An Event-Oriented Simulation Method for Multi-Core Real-Time Scheduling
Source abstract
Abstract
In this paper, an event-oriented simulation analysis approach was established for the schedulability analysis of multi-core embedded systems. To the best of our knowledge, this work is the first to introduce an event-oriented simulation strategy into multi-core processor schedulability analysis. The proposed method transforms the conventional step-by-step simulation into a jump-based simulation process, thereby reducing redundant system state updates and improving computational efficiency. Task execution is abstracted as a time-axis folding operation, and two algorithms, RBTF and PBTF, are developed to optimize event generation and management, effectively lowering the algorithmic complexity of the simulation. Furthermore, to resolve core-mapping conflicts arising in global scheduling during jump-based simulation, a time-axis-unfolding-based dynamic core-mapping algorithm is proposed. By incorporating a time interval recycling mechanism and a priority inheritance algorithm, this method ensures correct job-to-core assignment and enables precise response time analysis under global scheduling policies. This approach reduced the simulation time by 96.24% on average while guaranteeing the accuracy and soundness of the analysis. It is primarily applicable to periodic tasks with implied deadlines, and future work will explore extending this method to support sporadic tasks and tasks with arbitrary deadlines.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Real-Time Systems Scheduling · Embedded Systems Design Techniques · Petri Nets in System Modeling
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Beijing Institute of Computer Science and Applications, Beijing 100039, China
Beijing Institute of Tracking and Telecommunications Technology, Beijing 100094, China
Funding
Beijing Institute of Computer Science and Applications
References (27)
Show source-provided references
1. A survey of hard real-time scheduling for multiprocessor systems10.1145/1978802.1978814 ↗
2. Tian, Y.C., and Levy, D.C. (2022). Handbook of Real-Time Computing, Springer Nature.10.1007/978-981-287-251-7 ↗
3. Scheduling algorithms for multiprogramming in a hard-real-time environment10.1145/321738.321743 ↗
4. Cheng, A.M. (2023, January 9–12). Work in Progress: Response Time Analysis of Real-Time Quantum Computing Systems. Proceedings of the 2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS), San Antonio, TX, USA.10.1109/RTAS58335.2023.00033 ↗
5. Finding response times in a real-time system10.1093/comjnl/29.5.390 ↗
6. Lehoczky, J.P. (1990, January 5–7). Fixed priority scheduling of periodic task sets with arbitrary deadlines. Proceedings of the [1990] Proceedings 11th Real-Time Systems Symposium, Lake Buena Vista, FL, USA.10.1109/REAL.1990.128748 ↗
7. Applying new scheduling theory to static priority pre-emptive scheduling10.1049/sej.1993.0034 ↗
8. Günzel, M., Ueter, N., and Chen, J.J. (2021, January 7–10). Suspension-aware fixed-priority schedulability test with arbitrary deadlines and arrival curves. Proceedings of the 2021 IEEE Real-Time Systems Symposium (RTSS), Dortmund, Germany.10.1109/RTSS52674.2021.00045 ↗
9. Baker, T.P. (2003, January 5). Multiprocessor EDF and deadline monotonic schedulability analysis. Proceedings of the RTSS 2003. 24th IEEE Real-Time Systems Symposium, 2003, Cancun, Mexico.
10. Bertogna, M., Cirinei, M., and Lipari, G. (2005, January 6–8). Improved schedulability analysis of EDF on multiprocessor platforms. Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS’05), Balearic Islands, Spain.
11. Bertogna, M., and Cirinei, M. (2007, January 3–6). Response time analysis for globally scheduled symmetric multiprocessor platforms. Proceedings of the 28th IEEE International Real-Time Systems Symposium (RTSS 2007), Tucson, AZ, USA.10.1109/RTSS.2007.31 ↗
12. Baruah, S. (2007, January 3–6). Techniques for multiprocessor global schedulability analysis. Proceedings of the 28th IEEE International Real-Time Systems Symposium (RTSS 2007), Tucson, AZ, USA.10.1109/RTSS.2007.35 ↗
13. Guan, N., Stigge, M., Yi, W., and Yu, G. (2009, January 1–4). New response time bounds for fixed priority multiprocessor scheduling. Proceedings of the 2009 30th IEEE Real-Time Systems Symposium, Washington, DC, USA.10.1109/RTSS.2009.11 ↗
14. Pessimism in multicore global schedulability analysis10.1016/j.sysarc.2018.12.006 ↗
15. Bounding carry-in interference for synchronous parallel tasks under global fixed-priority scheduling10.1016/j.sysarc.2018.08.004 ↗
16. Global Fixed Priority Scheduling with Constructing Execution Dependency in Multiprocessor Real-Time Systems10.1142/S0218126618501657 ↗
17. Nasri, M., and Brandenburg, B.B. (2017, January 5–8). An exact and sustainable analysis of non-preemptive scheduling. Proceedings of the 2017 IEEE Real-Time Systems Symposium (RTSS), Paris, France.10.1109/RTSS.2017.00009 ↗
18. Ranjha, S., Nelissen, G., and Nasri, M. (2022, January 4–6). Partial-Order Reduction for Schedule-Abstraction-based Response-Time Analyses of Non-Preemptive Tasks. Proceedings of the 2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS), Milano, Italy.10.1109/RTAS54340.2022.00018 ↗
19. Partial-order reduction in reachability-based response-time analyses of limited-preemptive DAG tasks10.1007/s11241-023-09398-x ↗
20. Feasibility interval and sustainable scheduling simulation with CRPD on uniprocessor platform10.1016/j.sysarc.2021.102007 ↗
21. Harbour, M.G., García, J.G., Gutiérrez, J.P., and Moyano, J.D. (2001, January 13–15). Mast: Modeling and analysis suite for real time applications. Proceedings of the Proceedings 13th Euromicro Conference on Real-Time Systems, Delft, The Netherlands.
22. Urunuela, R., Déplanche, A.M., and Trinquet, Y. (2010, January 13–16). Storm a simulation tool for real-time multiprocessor scheduling evaluation. Proceedings of the 2010 IEEE 15th Conference on Emerging Technologies & Factory Automation (ETFA 2010), Bilbao, Spain.10.1109/ETFA.2010.5641179 ↗
23. Chandarli, Y., Fauberteau, F., Masson, D., Midonnet, S., and Qamhieh, M. (2012). Yartiss: A Tool to Visualize, Test, Compare and Evaluate Real-Time Scheduling Algorithms. [Ph.D. Thesis, Université Paris-Est].
24. Chéramy, M., Hladik, P.E., and Déplanche, A.M. (2014, January 8). Simso: A simulation tool to evaluate real-time multiprocessor scheduling algorithms. Proceedings of the 5th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), Madrid, Spain.10.1007/978-3-319-11457-6_3 ↗
25. Singhoff, F., Legrand, J., Nana, L., and Marcé, L. (2004, January 14–18). Cheddar: A flexible real time scheduling framework. Proceedings of the 2004 annual ACM SIGAda International Conference on Ada: The Engineering of Correct and Reliable Software for Real-Time & Distributed Systems Using Ada and Related Technologies, Atlanta, GA, USA.10.1145/1032297.1032298 ↗
26. Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms10.1007/s11241-016-9256-1 ↗
27. Rubinstein, R.Y., and Kroese, D.P. (2016). Simulation and the Monte Carlo Method, John Wiley & Sons.10.1002/9781118631980 ↗