{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:16:43Z","timestamp":1750306603416,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,4,21]],"date-time":"2015-04-21T00:00:00Z","timestamp":1429574400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Portuguese National Funds through FCT (Portuguese Foundation for Science and Technology"},{"name":"UK EPSRC Tempo project"},{"name":"UK EPSRC MCC project"},{"name":"ERDF (European Regional Development Fund) through COMPETE (Operational Programme \"Thematic Factors of Competitiveness\"), within the RePoMuC project"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2015,5,21]]},"abstract":"<jats:p>This article introduces schedulability analysis for Global Fixed Priority Scheduling with Deferred Preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of Global Fixed Priority Preemptive Scheduling (gFPPS) and Global Fixed Priority Nonpreemptive Scheduling (gFPNS). We show how schedulability can be improved using gFPDS via appropriate choice of priority assignment and final nonpreemptive region lengths, and provide algorithms that optimize schedulability in this way. Via an experimental evaluation we compare the performance of multiprocessor scheduling using global approaches: gFPDS, gFPPS, and gFPNS, and also partitioned approaches employing FPDS, FPPS, and FPNS on each processor.<\/jats:p>","DOI":"10.1145\/2739954","type":"journal-article","created":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T13:57:35Z","timestamp":1429711055000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred Preemption"],"prefix":"10.1145","volume":"14","author":[{"given":"Robert I.","family":"Davis","sequence":"first","affiliation":[{"name":"University of York, Deramore Lane, York, UK"}]},{"given":"Alan","family":"Burns","sequence":"additional","affiliation":[{"name":"University of York, Deramore Lane, York, UK"}]},{"given":"Jose","family":"Marinho","sequence":"additional","affiliation":[{"name":"CISTER\/INESC-TEC, ISEP, PORTO, Portugal"}]},{"given":"Vincent","family":"Nelis","sequence":"additional","affiliation":[{"name":"CISTER\/INESC-TEC, ISEP, PORTO, Portugal"}]},{"given":"Stefan M.","family":"Petters","sequence":"additional","affiliation":[{"name":"CISTER\/INESC-TEC, ISEP, PORTO, Portugal"}]},{"given":"Marko","family":"Bertogna","sequence":"additional","affiliation":[{"name":"University of Modena, Modena, Italy"}]}],"member":"320","published-online":{"date-parts":[[2015,4,21]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2011.31"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9152-2"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00165-4"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/956418.956614"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2006.47"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2005.32"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.48"},{"volume-title":"Proceedings of the 9th International Conference on Distributed Computing and Networking. 215--226","author":"Baruah S. K.","key":"e_1_2_2_9_1","unstructured":"S. K. Baruah and N. Fisher . 2008. Global fixed-priority scheduling of arbitrary-deadline sporadic task systems . In Proceedings of the 9th International Conference on Distributed Computing and Networking. 215--226 . S. K. Baruah and N. Fisher. 2008. Global fixed-priority scheduling of arbitrary-deadline sporadic task systems. In Proceedings of the 9th International Conference on Distributed Computing and Networking. 215--226."},{"volume-title":"Proceedings of the 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT\u201910)","author":"Brandenburg B.","key":"e_1_2_2_10_1","unstructured":"Bastoni, B. Brandenburg , and J. Anderson . 2010. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability . In Proceedings of the 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT\u201910) . 33--44. Bastoni, B. Brandenburg, and J. Anderson. 2010. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In Proceedings of the 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT\u201910). 33--44."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_24"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.41"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.129"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2010.9"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2011.28"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2011.30"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2007.8"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_2_19_1","volume-title":"Technical Report MPI-SWS-2014-007. Max Plank Institute for Software Systems. Available from http:&sol;&sol;www.mpi-sws.org&sol;cont&sol;tr&sol;2014-007.pdf.","author":"Brandenburg B. B.","year":"2014","unstructured":"B. B. Brandenburg and J. Anderson . 2014 . A Clarification of Link-Based Global Scheduling . Technical Report MPI-SWS-2014-007. Max Plank Institute for Software Systems. Available from http:&sol;&sol;www.mpi-sws.org&sol;cont&sol;tr&sol;2014-007.pdf. B. B. Brandenburg and J. Anderson. 2014. A Clarification of Link-Based Global Scheduling. Technical Report MPI-SWS-2014-007. Max Plank Institute for Software Systems. Available from http:&sol;&sol;www.mpi-sws.org&sol;cont&sol;tr&sol;2014-007.pdf."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-009-9071-z"},{"volume-title":"Preemptive Priority Based Scheduling: An Appropriate Engineering Approach","author":"Burns A.","key":"e_1_2_2_22_1","unstructured":"A. Burns . 1994. Preemptive Priority Based Scheduling: An Appropriate Engineering Approach . S. Son (Ed.), Advances in Real-Time Systems. Prentice-Hall , Upper Saddle River, NJ, 225--248. A. Burns. 1994. Preemptive Priority Based Scheduling: An Appropriate Engineering Approach. S. Son (Ed.), Advances in Real-Time Systems. Prentice-Hall, Upper Saddle River, NJ, 225--248."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5626\/JCSE.2008.2.1.074"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2012.2188805"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.31"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-009-9079-4"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-010-9106-5"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.31"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9149-x"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978802.1978814"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.57"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-007-9012-7"},{"volume-title":"Proceedings of the 19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA\u201913)","author":"Davis R. I.","key":"e_1_2_2_33_1","unstructured":"R. I. Davis , A. Burns , J. Marinho , V. Nelis , S. M. Petters , and M. Bertogna . 2013. Global fixed priority scheduling with deferred pre-emption . In Proceedings of the 19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA\u201913) . 1--11. R. I. Davis, A. Burns, J. Marinho, V. Nelis, S. M. Petters, and M. Bertogna. 2013. Global fixed priority scheduling with deferred pre-emption. In Proceedings of the 19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA\u201913). 1--11."},{"volume-title":"Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-Time Systems (WATERS\u201910)","author":"Emberson P.","key":"e_1_2_2_34_1","unstructured":"P. Emberson , R. Stafford , and R. I. Davis . 2010. Techniques for the synthesis of multiprocessor tasksets . In Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-Time Systems (WATERS\u201910) . 6--11. P. Emberson, R. Stafford, and R. I. Davis. 2010. Techniques for the synthesis of multiprocessor tasksets. In Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-Time Systems (WATERS\u201910). 6--11."},{"volume-title":"Procedings of the IASTED International Conference on Parallel and Distributed Computing and Systems.","author":"Fisher N.","key":"e_1_2_2_35_1","unstructured":"N. Fisher and S. K. Baruah . 2006. Global static-priority scheduling of sporadic task systems on multiprocessor platforms . In Procedings of the IASTED International Conference on Parallel and Distributed Computing and Systems. N. Fisher and S. K. Baruah. 2006. Global static-priority scheduling of sporadic task systems on multiprocessor platforms. In Procedings of the IASTED International Conference on Parallel and Distributed Computing and Systems."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2006.30"},{"key":"e_1_2_2_37_1","unstructured":"M. Garey and D. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York.   M. Garey and D. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2010.08.003"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.11"},{"volume-title":"Proceedings of the 36th Symposium on Foundations of Computer Science. 214--221","author":"Kalyanasundaram B.","key":"e_1_2_2_40_1","unstructured":"B. Kalyanasundaram and K. Pruhs . 1995. Speed is as powerful as clairvoyance . In Proceedings of the 36th Symposium on Foundations of Computer Science. 214--221 . B. Kalyanasundaram and K. Pruhs. 1995. Speed is as powerful as clairvoyance. In Proceedings of the 36th Symposium on Foundations of Computer Science. 214--221."},{"key":"e_1_2_2_41_1","article-title":"A comparison between fixed priority and EDF scheduling accounting for cache related pre-emption delays","volume":"1","author":"Lunniss W.","year":"2014","unstructured":"W. Lunniss , S. Altmeyer , and R. I. Davis . 2014 . A comparison between fixed priority and EDF scheduling accounting for cache related pre-emption delays . Leibniz Trans. Embedded Syst. 1 , 1 (2014). DOI: http:&sol;&sol;dx.doi.org&sol;10.4230&sol;LITES-v001-i001-a001. W. Lunniss, S. Altmeyer, and R. I. Davis. 2014. A comparison between fixed priority and EDF scheduling accounting for cache related pre-emption delays. Leibniz Trans. Embedded Syst. 1, 1 (2014). DOI: http:&sol;&sol;dx.doi.org&sol;10.4230&sol;LITES-v001-i001-a001.","journal-title":"Leibniz Trans. Embedded Syst."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2013.26"},{"volume-title":"Proceedings of DATE. 497--502","author":"Marinho J.","key":"e_1_2_2_43_1","unstructured":"J. Marinho , V. N\u00e9lis , S. M. Petters , and I. Puaut . 2012. Preemption delay analysis for floating non-preemptive region scheduling . In Proceedings of DATE. 497--502 . J. Marinho, V. N\u00e9lis, S. M. Petters, and I. Puaut. 2012. Preemption delay analysis for floating non-preemptive region scheduling. In Proceedings of DATE. 497--502."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008098013753"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2009.44"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2739954","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2739954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:52Z","timestamp":1750227412000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2739954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,21]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,5,21]]}},"alternative-id":["10.1145\/2739954"],"URL":"https:\/\/doi.org\/10.1145\/2739954","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2015,4,21]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}