{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:15:54Z","timestamp":1760238954532,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T00:00:00Z","timestamp":1600041600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002628","name":"Incheon National University","doi-asserted-by":"publisher","award":["2019"],"award-info":[{"award-number":["2019"]}],"id":[{"id":"10.13039\/501100002628","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Zero-laxity (ZL) and contention-free (CF) policies have received considerable attention owing to their simplicity and applicability to real-time systems equipped with symmetry multiprocessors. Recently, the ZL policy for mixed-criticality (MC) systems has been proposed and studied, but the applicability to and performance of the CF policy for MC systems have not been investigated yet. In this paper, we propose the CF policy (as a scheduling policy) for MC symmetry multiprocessor systems, referred to as the MC systems tailored CF policy (MC-CF), and a schedulability analysis in support thereof. We define the notion of contention-free slots for two different criticalities (of MC systems) of tasks, propose a technique to limit the amount to be utilized for each task by defining an upper bound, and subsequently explain the way in which the contention-free slots are systematically utilized to improve the schedulability of MC symmetry multiprocessor systems. Following this, we develop a deadline analysis (DA) for MC-CF. Using our experimental results under various environmental settings, we demonstrate that MC-CF can significantly improve the schedulability of fixed-priority scheduling.<\/jats:p>","DOI":"10.3390\/sym12091515","type":"journal-article","created":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T10:24:09Z","timestamp":1600165449000},"page":"1515","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Contention-Free Scheduling for Mixed-Criticality Multiprocessor Real-Time System"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9518-3556","authenticated-orcid":false,"given":"Hyeongboo","family":"Baek","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Incheon National University (INU), Incheon 22012, Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3651-0427","authenticated-orcid":false,"given":"Kilho","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Smart Systems Software, Soongsil University (SSU), Seoul 06978, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Baruah, S., Mok, A., and Rosier, L. (1990, January 5\u20137). Preemptively scheduling hard-real-time sporadic tasks on one processor. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Lake Buena Vista, FL, USA.","DOI":"10.1109\/REAL.1990.128746"},{"key":"ref_2","unstructured":"Anderson, J.H., and Srinivasan, A. (2000, January 19\u201321). Early-release fair scheduling. Proceedings of the 12th Euromicro Conference on Real-Time Systems, Euromicro, RTSECRTS, Stockholm, Sweden."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Cho, H., Ravindran, B., and Jensen, E.D. (2006, January 5\u20138). An Optimal Real-Time Scheduling Algorithm for Multiprocessors. Proceedings of the 27th IEEE International Real-Time Systems Symposium (RTSS\u201906), Rio de Janeiro, Brazil.","DOI":"10.1109\/RTSS.2006.10"},{"key":"ref_4","unstructured":"Regnier, P., Lima, G., Massa, E., Levin, G., and Brandt, S. (December, January 29). RUN: Optimal Multiprocessor Real-Time Scheduling via Reduction to Uniprocessor. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Vienna, Austria."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Andersson, B., and Tovar, E. (2006, January 16\u201318). Multiprocessor Scheduling with Few Preemptions. Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA\u201906), Sydney, Australia.","DOI":"10.1109\/RTCSA.2006.45"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Levin, G., Funk, S., Sadowski, C., Pye, I., and Brandt, S. (2010, January 6\u20139). DP-FAIR: A Simple Model for Understanding Optimal Multiprocessor Scheduling. Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), Brussels, Belgium.","DOI":"10.1109\/ECRTS.2010.34"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1109\/MDAT.2016.2594790","article-title":"Mixed Criticality Systems\u2014A History of Misconceptions?","volume":"33","author":"Ernst","year":"2016","journal-title":"IEEE Des. Test"},{"key":"ref_8","unstructured":"Anderson, J.H., Baruah, S., and Brandenburg, B.B. (2009, January 16). Multicore operating-system support for mixed criticality. Proceedings of the Workshop on Mixed-Criticality: Roadmap to Evolving UAV Certification, San Francisco, CA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Pathan, R. (2012, January 11\u201313). Schedulability Analysis of Mixed-Criticality Systems on Multiprocessors. Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), Pisa, Italy.","DOI":"10.1109\/ECRTS.2012.29"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1766","DOI":"10.1109\/TPDS.2018.2806443","article-title":"Non-Preemptive Scheduling for Mixed-Criticality Real-Time Multiprocessor Systems","volume":"29","author":"Baek","year":"2018","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/s11241-008-9061-6","article-title":"EDZL Scheduling Analysis","volume":"40","author":"Baker","year":"2008","journal-title":"Real Time Syst."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lee, J., Easwaran, A., and Shin, I. (2011, January 11\u201314). Maximizing Contention-Free Executions in Multiprocessor Scheduling. Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS), Chicago, IL, USA.","DOI":"10.1109\/RTAS.2011.30"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2494530","article-title":"Contention-Free Executions for Real-Time Multiprocessor Scheduling","volume":"13","author":"Lee","year":"2014","journal-title":"ACM Trans. Embed. Comput. Syst."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1888","DOI":"10.1587\/transfun.E101.A.1888","article-title":"Incorporating Zero-Laxity Policy into Mixed-Criticality Multiprocessor Real-Time Systems","volume":"101","author":"Jung","year":"2018","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_15","unstructured":"Burns, A., and Davis, R.I. (2015). Mixed Criticality Systems\u2014A Review, University of York."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Bertogna, M., and Cirinei, M. (2008, January 3\u20136). Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms. Proceedings of the 28th IEEE International Real-Time Systems Symposium (RTSS 2007), Tucson, AZ, USA.","DOI":"10.1109\/RTSS.2007.31"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.jss.2017.11.027","article-title":"Multi-Level Contention-Free Policy for Real-Time Multiprocessor Scheduling","volume":"137","author":"Baek","year":"2018","journal-title":"J. Syst. Softw."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.jss.2019.04.067","article-title":"Improved Schedulability Analysis of the Contention-Free Policy for Real-Time Systems","volume":"154","author":"Baek","year":"2019","journal-title":"J. Syst. Softw."},{"key":"ref_19","unstructured":"Vestal, S. (2005, January 7\u201310). Real-Time Sampled Signal Flows through Asynchronous Distributed Systems. Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS), San Francisco, CA, USA."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Baruah, S., Bonifaci, V., D\u2019Angelo, G., MarchettiSpaccamela, A., van der Ster, S., and Stougie, L. (2011, January 5\u20139). Mixed-criticality scheduling of sporadic task systems. Proceedings of the 19th Annual European Symposium on Algorithms, Saarbr\u00fccken, Germany.","DOI":"10.1007\/978-3-642-23719-5_47"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Baruah, S., Bonifaci, V., D\u2019Angelo, G., Marchetti-Spaccamela, H.L.A., van der Ster, S., and Stougie, L. (2012, January 11\u201313). The Preemptive Uniprocessor Scheduling of Mixed-Criticality Implicit-Deadline Sporadic Task Systems. Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), Pisa, Italy.","DOI":"10.1109\/ECRTS.2012.42"},{"key":"ref_22","unstructured":"Baruah, S., Burns, A., and Davis, R.I. (December, January 29). Response-Time Analysis for Mixed Criticality Systems. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Vienna, Austria."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Baruah, S., Li, H., and Stougie, L. (2010, January 12\u201315). Toward the design of certifiable mixed-criticality systems. Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS), Stockholm, Sweden.","DOI":"10.1109\/RTAS.2010.10"},{"key":"ref_24","unstructured":"Li, H., and Baruah, S. (December, January 30). An algorithm for scheduling certifiable mixed-criticality sporadic task systems. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), San Diego, CA, USA."},{"key":"ref_25","unstructured":"Baruah, S. (December, January 29). Schedulability Analysis for a General Model of Mixed-Criticality Recurrent Real-Time Tasks. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Porto, Portugal."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Li, H., and Baruah, S. (2012, January 10\u201313). Global mixed-criticality scheduling on multiprocessors. Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), Pisa, Italy.","DOI":"10.1109\/ECRTS.2012.41"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Lee, J., Phan, K., Gu, X., Lee, J., Easwaran, A., Shin, I., and Lee, I. (2014, January 2\u20135). MC-Fluid: Fluid Model-Based Mixed-Criticality Scheduling on Multiprocessorss. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Rome, Italy.","DOI":"10.1109\/RTSS.2014.32"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Davis, R., and Burns, A. (2009, January 1\u20134). Priority Assignment for Global Fixed Priority Pre-emptive Scheduling in Multiprocessor Real-Time Systems. Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Washington, DC, USA.","DOI":"10.1109\/RTSS.2009.31"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s11241-005-0507-9","article-title":"Measuring the performance of schedulability tests","volume":"30","author":"Bini","year":"2005","journal-title":"Real Time Syst."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/9\/1515\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:10:00Z","timestamp":1760177400000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/9\/1515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,14]]},"references-count":29,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["sym12091515"],"URL":"https:\/\/doi.org\/10.3390\/sym12091515","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,9,14]]}}}