Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with Contention
Source abstract
Abstract
In the scheduling of hard real-time systems on multicore platforms, significant unpredictability arises from interference caused by shared hardware resources. The objective of this paper is to offer a schedulability analysis for such systems by assuming a general model that introduces interference as a time parameter for each task. The analysis assumes constrained deadlines and is provided for fixed priorities. It is based on worst-case response time analysis, which exists in the literature for monocore systems. We demonstrate that the worst-case response time is an upper bound, and we evaluate our proposal with synthetic loads and execution on a real platform.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Real-Time Systems Scheduling · Scheduling and Optimization Algorithms · Petri Nets in System Modeling
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Instituto de Automática e Informática Industrial (ai2), Universitat Politècnica de València, 46022 Valencia, Spain
Funding
MCIN/AEI/10.13039/501100011033/ · Universitat Politècnica de València
References (34)
Show source-provided references
1. Dasari, D., Akesson, B., Nélis, V., Awan, M.A., and Petters, S.M. (2013, January 19–21). Identifying the sources of unpredictability in COTS-based multicore systems. Proceedings of the 2013 8th IEEE International Symposium on Industrial Embedded Systems (SIES), Porto, Portugal.10.1109/SIES.2013.6601469 ↗
2. The Impact of Interference due to Resource Contention in Multicore Platform for Safety-critical Avionics Systems
3. Kim, H., de Niz, D., Andersson, B., Klein, M., Mutlu, O., and Rajkumar, R. (2014, January 22–24). Bounding memory interference delay in COTS-based multi-core systems. Proceedings of the 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), St. Louis, MI, USA.10.1109/RTAS.2014.6925998 ↗
4. Hardware resources contention-aware scheduling of hard real-time multiprocessor systems10.1016/j.sysarc.2021.102223 ↗
5. Johnson, D.S. (1973). Near-Optimal Bin Packing Algorithms. [Ph.D. Thesis, Massachusetts Institute of Technology].
6. Optimized Scheduling of Periodic Hard Real-Time Multicore Systems10.1109/ACCESS.2023.3261130 ↗
7. Allocating Fixed-Priority Periodic Tasks on Multiprocessor Systems10.1007/BF01088806 ↗
8. Coffman, E.G., Garey, M.R., and Johnson, D.S. (1996). Approximation Algorithms for NP-Hard Problems, PWS Publishing Co.
9. Schedulability Analysis of Dynamic Priority Real-Time Systems with Contention10.1007/s11227-022-04446-y ↗
10. Worst-Case Response Time Analysis of Real-Time Tasks under Fixed-Priority Scheduling with Deferred Preemption Revisited
11. A Survey of Hard Real-Time Scheduling for Multiprocessor Systems10.1145/1978802.1978814 ↗
12. A Survey of Techniques for Reducing Interference in Real-Time Applications on Multicore Platforms10.1109/ACCESS.2022.3151891 ↗
13. NUMA-aware memory coloring for multicore real-time systems10.1016/j.sysarc.2021.102188 ↗
14. Reduced latency DRAM for multi-core safety-critical real-time systems10.1007/s11241-019-09338-8 ↗
15. Mancuso, R., Dudko, R., Betti, E., Cesati, M., Caccamo, M., and Pellizzoni, R. (2013, January 9–11). Real-time cache management framework for multi-core architectures. Proceedings of the 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), Philadelphia, PA, USA.10.1109/RTAS.2013.6531078 ↗
16. Sun, G., Shen, J., and Veidenbaum, A.V. (2019, January 20–24). Combining prefetch control and cache partitioning to improve multicore performance. Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rio de Janeiro, Brazil.10.1109/IPDPS.2019.00103 ↗
17. Memory Bandwidth Management for Efficient Performance Isolation in Multi-Core Platforms10.1109/TC.2015.2425889 ↗
18. Xu, M., Gifford, R., and Phan, L.T.X. (2019, January 2–6). Holistic multi-resource allocation for multicore real-time virtualization. Proceedings of the 56th Annual Design Automation Conference, Las Vegas, NV, USA.10.1145/3316781.3317840 ↗
19. Altmeyer, S., Davis, R.I., Indrusiak, L., Maiza, C., Nelis, V., and Reineke, J. (2015, January 7–8). A generic and compositional framework for multicore response time analysis. Proceedings of the 23rd International Conference on Real Time and Networks Systems, Dortmund, Germany.10.1145/2834848.2834862 ↗
20. Negrean, M., Schliecker, S., and Ernst, R. (2009, January 20–24). Response-time analysis of arbitrarily activated tasks in multiprocessor systems with shared resources. Proceedings of the 2009 Design, Automation & Test in Europe Conference & Exhibition, Nice, France.10.1109/DATE.2009.5090720 ↗
21. Schranzhofer, A., Pellizzoni, R., Chen, J.J., Thiele, L., and Caccamo, M. (2010, January 13–18). Worst-case response time analysis of resource access models in multi-core systems. Proceedings of the Design Automation Conference, Anaheim, CA, USA.10.1145/1837274.1837359 ↗
22. Choi, J., Kang, D., and Ha, S. (2016, January 14–18). Conservative modeling of shared resource contention for dependent tasks in partitioned multi-core systems. Proceedings of the 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany.10.3850/9783981537079_0101 ↗
23. Chen, J.J. (2016, January 5–8). Partitioned multiprocessor fixed-priority scheduling of sporadic real-time tasks. Proceedings of the 2016 28th Euromicro Conference on Real-Time Systems (ECRTS), Toulouse, France.10.1109/ECRTS.2016.26 ↗
24. Schedulability Analysis of Non-Preemptive Strictly Periodic Tasks in Multi-Core Real-Time Systems10.1007/s11241-015-9226-z ↗
25. Huang, W.H., Chen, J.J., and Reineke, J. (2016, January 5–9). MIRROR: Symmetric timing analysis for real-time tasks on multicore platforms with shared resources. Proceedings of the 2016 53nd ACM/EDAC/IEEE Design Automation Conference (DAC), Austin, TX, USA.10.1145/2897937.2898046 ↗
26. Worst-Case Response Time Analysis of a Synchronous Dataflow Graph in a Multiprocessor System with Real-Time Tasks10.1145/2997644 ↗
27. Compositional verification of embedded real-time systems10.1016/j.sysarc.2023.102928 ↗
28. Schedulability Analysis of Tasks with Corunner-Dependent Execution Times10.1145/3203407 ↗
29. Partitioning and Selection of Data Consistency Mechanisms for Multicore Real-Time Systems10.1145/3358233 ↗
30. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment10.1145/321738.321743 ↗
31. Finding Response Times in a Real-Time System10.1093/comjnl/29.5.390 ↗
32. Davis, R.I., and Burns, A. (2009, January 1–4). Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Proceedings of the 2009 30th IEEE Real-Time Systems Symposium, Washington, DC, USA.10.1109/RTSS.2009.31 ↗
33. Rate Monotonic vs. EDF: Judgment Day10.1023/B:TIME.0000048932.30002.d9 ↗
34. Guide for the Use of the Ada Ravenscar Profile in High Integrity Systems10.1145/997119.997120 ↗