{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:42:25Z","timestamp":1761324145120,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T00:00:00Z","timestamp":1521504000000},"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":["SIGBED Rev."],"published-print":{"date-parts":[[2018,3,20]]},"abstract":"<jats:p>Fixed-priority preemption-threshold scheduling (FPTS) is a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). Since FPPS and FPNS are incomparable in terms of potential schedulability, FPTS has the advantage that it can schedule any task set schedulable by FPPS or FPNS and some that are not schedulable by either. FPTS is based on the idea that each task is assigned a priority and a preemption threshold. While tasks are admitted into the system according to their priorities, they can only be preempted by tasks that have priority higher than the preemption threshold.<\/jats:p>\n          <jats:p>This paper presents a new optimal priority and preemption threshold assignment (OPTA) algorithm for FPTS which in general outperforms the existing algorithms in terms of the size of the explored state-space and the total number of worst case response time calculations performed. The algorithm is based on back-tracking, i.e. it traverses the space of potential priorities and preemption thresholds, while pruning infeasible paths, and returns the first assignment deemed schedulable.<\/jats:p>\n          <jats:p>We present the evaluation results where we compare the complexity of the new algorithm with the existing one. We show that the new algorithm significantly reduces the time needed to find a solution. Through a comparative evaluation, we show the improvements that can be achieved in terms of schedulability ratio by our OPTA compared to a deadline monotonic priority assignment.<\/jats:p>","DOI":"10.1145\/3199610.3199616","type":"journal-article","created":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T15:17:48Z","timestamp":1521731868000},"page":"43-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimal priority and threshold assignment for fixed-priority preemption threshold scheduling"],"prefix":"10.1145","volume":"15","author":[{"given":"Leo","family":"Hatvani","sequence":"first","affiliation":[{"name":"Technische Universiteit, The Netherlands"}]},{"given":"Sara","family":"Afshar","sequence":"additional","affiliation":[{"name":"M\u00e4lardalen University (MDH), V\u00e4ster\u00e5s, Sweden"}]},{"given":"Reinder J.","family":"Bril","sequence":"additional","affiliation":[{"name":"Technische Universiteit, The Netherlands and M\u00e4lardalen University (MDH), V\u00e4ster\u00e5s, Sweden"}]}],"member":"320","published-online":{"date-parts":[[2018,3,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2005.32"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-005-0507-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2007.38"},{"key":"e_1_2_1_4_1","first-page":"225","volume-title":"Advances in real-time systems","author":"Burns A.","year":"1995","unstructured":"A. Burns . Advances in real-time systems . chapter Preemptive Priority-based Scheduling: An Appropriate Engineering Approach, pages 225 -- 248 . Prentice-Hall, Inc. , Upper Saddle River, NJ, USA, 1995 . A. Burns. Advances in real-time systems. chapter Preemptive Priority-based Scheduling: An Appropriate Engineering Approach, pages 225--248. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1995."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/271658.271679"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2016.04.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ETFA.2015.7301449"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ETFA.2010.5640984"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"S.\n      Lee C.-G.\n      Lee M.\n      Lee S.\n      Min and \n      C.\n      Kim\n  . \n  Limited preemptible scheduling to embrace cache memory in real-time systems\n  . In F. Mueller and A. Bestavros editors Languages Compilers and Tools for Embedded Systems volume \n  1474\n   of \n  Lecture Notes in Computer Science pages \n  51\n  --\n  64\n  . \n  Springer Berlin Heidelberg 1998\n  .   S. Lee C.-G. Lee M. Lee S. Min and C. Kim. Limited preemptible scheduling to embrace cache memory in real-time systems. In F. Mueller and A. Bestavros editors Languages Compilers and Tools for Embedded Systems volume 1474 of Lecture Notes in Computer Science pages 51--64. Springer Berlin Heidelberg 1998.","DOI":"10.1007\/BFb0057780"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.469457"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/827272.829124"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1890629.1890633"},{"key":"e_1_2_1_13_1","first-page":"328","volume-title":"6th International Conference on Real-Time Computing Systems and Applications (RTCSA)","author":"Wang Y.","year":"1999","unstructured":"Y. Wang and M. Saksena . Scheduling fixed-priority tasks with preemption threshold . In 6th International Conference on Real-Time Computing Systems and Applications (RTCSA) , pages 328 -- 335 , Dec. 1999 . Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In 6th International Conference on Real-Time Computing Systems and Applications (RTCSA), pages 328--335, Dec. 1999."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2009.44"}],"container-title":["ACM SIGBED Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199610.3199616","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3199610.3199616","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:18Z","timestamp":1750273638000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3199610.3199616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,20]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,20]]}},"alternative-id":["10.1145\/3199610.3199616"],"URL":"https:\/\/doi.org\/10.1145\/3199610.3199616","relation":{},"ISSN":["1551-3688"],"issn-type":[{"type":"electronic","value":"1551-3688"}],"subject":[],"published":{"date-parts":[[2018,3,20]]},"assertion":[{"value":"2018-03-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}