{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:19Z","timestamp":1750220779681,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T00:00:00Z","timestamp":1560124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>Multicore platforms are becoming increasingly popular in real-time systems. One of the major challenges in designing multicore real-time systems is ensuring consistent and timely access to shared resources. Lock-based protection mechanisms such as MPCP and MSRP have been proposed to guarantee mutually exclusive access in multicore systems at the expense of blocking. In this article, we consider partitioning and scheduling in multicore real-time systems with resource sharing. We first propose a resource-aware task partitioning algorithm for systems with lock-based protection. Wait-free methods, which ensure consistent access to shared memory resources with negligible blocking at the expense of additional memory space, are a suitable alternative when the shared resource is a communication buffer. We propose several approaches to solve the joint problem of task partitioning and the selection of a data consistency mechanism (lock-based or wait-free). The problem is first formulated as an Integer Linear Programming (ILP). For large systems where an ILP solution is not scalable, we propose two heuristic algorithms. Experimental results compare the effectiveness of the proposed approaches in finding schedulable systems with low memory cost and show how the use of wait-free methods can significantly improve schedulability.<\/jats:p>","DOI":"10.1145\/3320271","type":"journal-article","created":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T13:28:16Z","timestamp":1560259696000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Partitioning and Selection of Data Consistency Mechanisms for Multicore Real-Time Systems"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3224-9938","authenticated-orcid":false,"given":"Zaid","family":"Al-bayati","sequence":"first","affiliation":[{"name":"McGill University, Montreal, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youcheng","family":"Sun","sequence":"additional","affiliation":[{"name":"Scuola Superiore Sant\u2019Anna, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haibo","family":"Zeng","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco Di","family":"Natale","sequence":"additional","affiliation":[{"name":"Scuola Superiore Sant\u2019Anna, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qi","family":"Zhu","sequence":"additional","affiliation":[{"name":"University of California at Riverside, Riverside, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brett H.","family":"Meyer","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,10]]},"reference":[{"volume-title":"USENIX Annual Technical Conference.","author":"Huang H.","key":"e_1_2_1_1_1","unstructured":"H. Huang , P. Pillai , and K. G. Shin . 2002. Improving wait-free algorithms for interprocess communication in embedded real-time systems . In USENIX Annual Technical Conference. H. Huang, P. Pillai, and K. G. Shin. 2002. Improving wait-free algorithms for interprocess communication in embedded real-time systems. In USENIX Annual Technical Conference."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.1990.89257"},{"volume-title":"IEEE Real-Time Systems Symposium.","author":"Gai P.","key":"e_1_2_1_3_1","unstructured":"P. Gai , G. Lipari , and M. D. Natale . 2001. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip . In IEEE Real-Time Systems Symposium. P. Gai, G. Lipari, and M. D. Natale. 2001. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In IEEE Real-Time Systems Symposium."},{"volume-title":"International Conference on Real-Time Computing Systems and Applications.","author":"Chen J.","key":"e_1_2_1_4_1","unstructured":"J. Chen and A. Burns . 1999. Loop-free asynchronous data sharing in multiprocessor real-time systems based on timing properties . In International Conference on Real-Time Computing Systems and Applications. J. Chen and A. Burns. 1999. Loop-free asynchronous data sharing in multiprocessor real-time systems based on timing properties. In International Conference on Real-Time Computing Systems and Applications."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.51"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.127"},{"key":"e_1_2_1_7_1","unstructured":"The AUTOSAR consortium. The AUTOSAR Standard specification version 4.1. {Online} http:\/\/www.autosar.org.  The AUTOSAR consortium. The AUTOSAR Standard specification version 4.1. {Online} http:\/\/www.autosar.org."},{"volume-title":"IEEE Real-Time and Embedded Technology and Applicatons Symposium.","author":"Al-Bayati Z.","key":"e_1_2_1_8_1","unstructured":"Z. Al-Bayati , Y. Sun , H. Zeng , M. Di Natale , Q. Zhu , and B. Meyer . 2015. Task placement and selection of data consistency mechanisms for real-time multicore applications . In IEEE Real-Time and Embedded Technology and Applicatons Symposium. Z. Al-Bayati, Y. Sun, H. Zeng, M. Di Natale, Q. Zhu, and B. Meyer. 2015. Task placement and selection of data consistency mechanisms for real-time multicore applications. In IEEE Real-Time and Embedded Technology and Applicatons Symposium."},{"volume-title":"IEEE International Symposium on Industrial Embedded Systems.","author":"Wieder A.","key":"e_1_2_1_9_1","unstructured":"A. Wieder and B. Brandenburg . 2013. Efficient partitioning of sporadic real-time tasks with shared resources and spin locks . In IEEE International Symposium on Industrial Embedded Systems. A. Wieder and B. Brandenburg. 2013. Efficient partitioning of sporadic real-time tasks with shared resources and spin locks. In IEEE International Symposium on Industrial Embedded Systems."},{"volume-title":"IEEE Conference on Emerging Technologies 8 Factory Automation.","author":"Nemati F.","key":"e_1_2_1_10_1","unstructured":"F. Nemati , M. Behnam , and T. Nolte . 2009. Efficiently migrating real-time systems to multi-cores . In IEEE Conference on Emerging Technologies 8 Factory Automation. F. Nemati, M. Behnam, and T. Nolte. 2009. Efficiently migrating real-time systems to multi-cores. In IEEE Conference on Emerging Technologies 8 Factory Automation."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2013.106"},{"volume-title":"IEEE Conference on Emerging Technologies 8 Factory Automation.","author":"Gracioli G.","key":"e_1_2_1_12_1","unstructured":"G. Gracioli and A. Fr\u00f6hlich . 2014. CAP: Color-aware task partitioning for multicore real-time applications . In IEEE Conference on Emerging Technologies 8 Factory Automation. G. Gracioli and A. Fr\u00f6hlich. 2014. CAP: Color-aware task partitioning for multicore real-time applications. In IEEE Conference on Emerging Technologies 8 Factory Automation."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978802.1978814"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2005.40"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2006.30"},{"volume-title":"Conference on Design and Architectures for Signal and Image Processing.","author":"Baruah S.","key":"e_1_2_1_16_1","unstructured":"S. Baruah and E. Bini . 2008. Partitioned scheduling of sporadic task systems: An ILP based approach . In Conference on Design and Architectures for Signal and Image Processing. S. Baruah and E. Bini. 2008. Partitioned scheduling of sporadic task systems: An ILP based approach. In Conference on Design and Architectures for Signal and Image Processing."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.32"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2011.18"},{"volume-title":"Conference on Design, Automation and Test in Europe.","author":"Dong C.","key":"e_1_2_1_19_1","unstructured":"C. Dong and H. Zeng . 2014. Minimizing stack memory for hard real-time applications on multicore platforms . In Conference on Design, Automation and Test in Europe. C. Dong and H. Zeng. 2014. Minimizing stack memory for hard real-time applications on multicore platforms. In Conference on Design, Automation and Test in Europe."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2846096"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.38"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2007.8"},{"volume-title":"IEEE Symposium on Industrial Embedded Systems.","author":"Zeng H.","key":"e_1_2_1_23_1","unstructured":"H. Zeng and M. Di Natale . 2011. Mechanisms for guaranteeing data consistency and time determinism in AUTOSAR software on multi-core platforms . In IEEE Symposium on Industrial Embedded Systems. H. Zeng and M. Di Natale. 2011. Mechanisms for guaranteeing data consistency and time determinism in AUTOSAR software on multi-core platforms. In IEEE Symposium on Industrial Embedded Systems."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176887.1176892"},{"key":"e_1_2_1_25_1","first-page":"3","article-title":"Improving the size of communication buffers in synchronous models with time constraints","volume":"5","author":"Wang G.","year":"2009","unstructured":"G. Wang , M. Di Natale , and A. Sangiovanni-Vincentelli . 2009 . Improving the size of communication buffers in synchronous models with time constraints . IEEE Transactions on Industrial Informatics 5 , 3 (Aug. 2009), 229--240. G. Wang, M. Di Natale, and A. Sangiovanni-Vincentelli. 2009. Improving the size of communication buffers in synchronous models with time constraints. IEEE Transactions on Industrial Informatics 5, 3 (Aug. 2009), 229--240.","journal-title":"IEEE Transactions on Industrial Informatics"},{"key":"e_1_2_1_26_1","first-page":"2","article-title":"Experimental evaluation and selection of data communication mechanisms in multicore platforms","volume":"10","author":"Han G.","year":"2014","unstructured":"G. Han , H. Zeng , M. Di Natale , X. Liu , and W. Dou . 2014 . Experimental evaluation and selection of data communication mechanisms in multicore platforms . IEEE Transactions on Industrial Informatics 10 , 2 (May 2014), 903--918. G. Han, H. Zeng, M. Di Natale, X. Liu, and W. Dou. 2014. Experimental evaluation and selection of data communication mechanisms in multicore platforms. IEEE Transactions on Industrial Informatics 10, 2 (May 2014), 903--918.","journal-title":"IEEE Transactions on Industrial Informatics"},{"volume-title":"Conference on Principles of Distributed Systems.","author":"Nemati F.","key":"e_1_2_1_27_1","unstructured":"F. Nemati , T. Nolte , and M. Behnam . 2010. Partitioning real-time systems on multiprocessors with shared resources . In Conference on Principles of Distributed Systems. F. Nemati, T. Nolte, and M. Behnam. 2010. Partitioning real-time systems on multiprocessors with shared resources. In Conference on Principles of Distributed Systems."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.57058"},{"key":"e_1_2_1_29_1","volume-title":"Technical Report 854. TU Dortmund.","author":"Chen J.","year":"2016","unstructured":"J. Chen 2016 . Many Suspensions, Many Problems : A Review of Self-Suspending Tasks in Real-Time Systems. Department of Computer Science , Technical Report 854. TU Dortmund. J. Chen et al. 2016. Many Suspensions, Many Problems: A Review of Self-Suspending Tasks in Real-Time Systems. Department of Computer Science, Technical Report 854. TU Dortmund."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1990.128747"},{"volume-title":"IEEE Real-Time Systems Symposium.","author":"Wieder A.","key":"e_1_2_1_31_1","unstructured":"A. Wieder and B. Brandenburg . 2013. On spin locks in AUTOSAR: Blocking analysis of FIFO, unordered, and priority-ordered spin locks . In IEEE Real-Time Systems Symposium. A. Wieder and B. Brandenburg. 2013. On spin locks in AUTOSAR: Blocking analysis of FIFO, unordered, and priority-ordered spin locks. In IEEE Real-Time Systems Symposium."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2013.6531087"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/99163.99185"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00165-4"},{"key":"e_1_2_1_35_1","unstructured":"IBM ILOG CPLEX Optimization Studio. {Online}. Available: https:\/\/www-01.ibm.com\/software\/commerce\/optimization\/cplex-optimizer\/  IBM ILOG CPLEX Optimization Studio. {Online}. Available: https:\/\/www-01.ibm.com\/software\/commerce\/optimization\/cplex-optimizer\/"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3320271","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3320271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:28Z","timestamp":1750200088000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3320271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,10]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3320271"],"URL":"https:\/\/doi.org\/10.1145\/3320271","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2019,6,10]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}