{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:50:35Z","timestamp":1764557435698,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,10,28]],"date-time":"2017-10-28T00:00:00Z","timestamp":1509148800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K011626\/1","EP\/P003664\/1"],"award-info":[{"award-number":["EP\/K011626\/1","EP\/P003664\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s11241-017-9294-3","type":"journal-article","created":{"date-parts":[[2017,10,28]],"date-time":"2017-10-28T11:35:57Z","timestamp":1509190557000},"page":"208-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Exact speedup factors and sub-optimality for non-preemptive scheduling"],"prefix":"10.1007","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5772-0928","authenticated-orcid":false,"given":"Robert I.","family":"Davis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhilash","family":"Thekkilakattil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Gettings","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Radu","family":"Dobrin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasikumar","family":"Punnekkat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8114-9760","authenticated-orcid":false,"given":"Jian-Jia","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,28]]},"reference":[{"issue":"3","key":"9294_CR1","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/LES.2015.2426657","volume":"7","author":"F Abugchem","year":"2015","unstructured":"Abugchem F, Short M, Xu D (2015) A note on the suboptimality of nonpreemptive real-time scheduling. IEEE Embed Syst Lett 7(3):69\u201372. https:\/\/doi.org\/10.1109\/LES.2015.2426657","journal-title":"IEEE Embed Syst Lett"},{"key":"9294_CR2","doi-asserted-by":"publisher","unstructured":"Altmeyer S, Davis RI, Maiza C (2011) Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In: Real-time systems symposium (RTSS), pp 261\u2013271. https:\/\/doi.org\/10.1109\/RTSS.2011.31","DOI":"10.1109\/RTSS.2011.31"},{"issue":"5","key":"9294_CR3","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s11241-012-9152-2","volume":"48","author":"S Altmeyer","year":"2012","unstructured":"Altmeyer S, Davis RI, Maiza C (2012) Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Syst 48(5):499\u2013526. https:\/\/doi.org\/10.1007\/s11241-012-9152-2","journal-title":"Real-Time Syst"},{"key":"9294_CR4","doi-asserted-by":"publisher","unstructured":"Altmeyer S, Douma R, Lunniss W, Davis RI (2014) Evaluation of cache partitioning for hard real-time systems. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 15\u201326. https:\/\/doi.org\/10.1109\/ECRTS.2014.11","DOI":"10.1109\/ECRTS.2014.11"},{"key":"9294_CR5","doi-asserted-by":"publisher","unstructured":"Altmeyer S, Douma R, Lunniss W, Davis RI (2016) On the effectiveness of cache partitioning in hard real-time systems. Real-Time Syst pp 1\u201346. https:\/\/doi.org\/10.1007\/s11241-015-9246-8","DOI":"10.1007\/s11241-015-9246-8"},{"key":"9294_CR6","unstructured":"Audsley N (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Dept Computer Science, University of York, Technical Report YCS, p 164"},{"issue":"1","key":"9294_CR7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(00)00165-4","volume":"79","author":"NC Audsley","year":"2001","unstructured":"Audsley NC (2001) On priority asignment in fixed priority scheduling. Inf Process Lett 79(1):39\u201344. https:\/\/doi.org\/10.1016\/S0020-0190(00)00165-4","journal-title":"Inf Process Lett"},{"issue":"5","key":"9294_CR8","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1049\/sej.1993.0034","volume":"8","author":"N Audsley","year":"1993","unstructured":"Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284\u2013292","journal-title":"Softw Eng J"},{"key":"9294_CR9","unstructured":"AUTOSAR (2007) Autosar specification of operating system, v4.10. Tech. rep. http:\/\/www.autosar.org\/"},{"issue":"1","key":"9294_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF00365393","volume":"3","author":"TP Baker","year":"1991","unstructured":"Baker TP (1991) Stack-based scheduling for realtime processes. Real-Time Syst 3(1):67\u201399. https:\/\/doi.org\/10.1007\/BF00365393","journal-title":"Real-Time Syst"},{"key":"9294_CR11","doi-asserted-by":"publisher","unstructured":"Baruah SK, Mok AK, Rosier LE (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings real-time systems symposium (RTSS), pp 182\u2013190. https:\/\/doi.org\/10.1109\/REAL.1990.128746","DOI":"10.1109\/REAL.1990.128746"},{"key":"9294_CR12","unstructured":"Bastoni A, Brandenburg BB, Anderson JH (2010) Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In: Proceedings operating systems platforms for embedded real-time applications (OSPERT)"},{"issue":"1\u20132","key":"9294_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s11241-005-0507-9","volume":"30","author":"E Bini","year":"2005","unstructured":"Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30(1\u20132):129\u2013154. https:\/\/doi.org\/10.1007\/s11241-005-0507-9","journal-title":"Real-Time Syst"},{"issue":"1\u20133","key":"9294_CR14","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s11241-009-9071-z","volume":"42","author":"RJ Bril","year":"2009","unstructured":"Bril RJ, Lukkien JJ, Verhaegh WF (2009) Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption. Real-Time Syst 42(1\u20133):63\u2013119. https:\/\/doi.org\/10.1007\/s11241-009-9071-z","journal-title":"Real-Time Syst"},{"key":"9294_CR15","doi-asserted-by":"publisher","unstructured":"Bui BD, Caccamo M, Sha L, Martinez J (2008) Impact of cache partitioning on multi-tasking real time embedded systems. In: proceedings Real-Time Computing Systems and Applications (RTCSA), pp 101\u2013110, https:\/\/doi.org\/10.1109\/RTCSA.2008.42","DOI":"10.1109\/RTCSA.2008.42"},{"issue":"5","key":"9294_CR16","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1109\/TC.2014.2322619","volume":"64","author":"A Burns","year":"2015","unstructured":"Burns A, Gutierrez M, Aldea Rivas M, Gonzalez Harbour M (2015) A deadline-floor inheritance protocol for edf scheduled embedded real-time systems with resource sharing. IEEE Trans Comput 64(5):1241\u20131253. https:\/\/doi.org\/10.1109\/TC.2014.2322619","journal-title":"IEEE Trans Comput"},{"issue":"1","key":"9294_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/TII.2012.2188805","volume":"9","author":"GC Buttazzo","year":"2013","unstructured":"Buttazzo GC, Bertogna M, Yao G (2013) Limited preemptive scheduling for real-time systems. A survey. IEEE Trans Ind Inform 9(1):3\u201315. https:\/\/doi.org\/10.1109\/TII.2012.2188805","journal-title":"A survey. IEEE Trans Ind Inform"},{"key":"9294_CR18","unstructured":"Chen JJ, von der Brggen G, Huang WH, Davis RI (2017) On the pitfalls of resource augmentation factors and utilization bounds in real-time scheduling. In: Proceedings Euromicro conference on real-time systems (ECRTS)"},{"key":"9294_CR19","unstructured":"Davis RI (2017) On the evaluation of schedulability tests for real-time scheduling algorithms. In: Proceedings international workshop on analysis tools and methodologies for embedded and real-time systems (WATERS)"},{"key":"9294_CR20","doi-asserted-by":"publisher","unstructured":"Davis RI, Bertogna M (2012) Optimal fixed priority scheduling with deferred pre-emption. In: Proceedings real-time systems symposium (RTSS), pp 39\u201350, https:\/\/doi.org\/10.1109\/RTSS.2012.57","DOI":"10.1109\/RTSS.2012.57"},{"issue":"3","key":"9294_CR21","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s11241-007-9012-7","volume":"35","author":"RI Davis","year":"2007","unstructured":"Davis RI, Burns A, Bril RJ, Lukkien JJ (2007) Controller area network (can) schedulability analysis: refuted, revisited and revised. Real-Time Syst 35(3):239\u2013272. https:\/\/doi.org\/10.1007\/s11241-007-9012-7","journal-title":"Real-Time Syst"},{"issue":"3","key":"9294_CR22","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s11241-009-9079-4","volume":"43","author":"RI Davis","year":"2009","unstructured":"Davis RI, Rothvoss T, Baruah SK, Burns A (2009a) Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real-Time Syst 43(3):211\u2013258. https:\/\/doi.org\/10.1007\/s11241-009-9079-4","journal-title":"Real-Time Syst"},{"key":"9294_CR23","doi-asserted-by":"crossref","unstructured":"Davis RI, Rothvoss T, Baruah SK, Burns A (2009b) Quantifying the sub-optimality of uniprocessor fixed priority pre-emptive scheduling for sporadic tasksets with arbitrary deadlines. In: Proceedings real-time and network systems (RTNS), pp 23\u201331","DOI":"10.1007\/s11241-009-9079-4"},{"key":"9294_CR24","unstructured":"Davis RI, George L, Courbin P (2010) Quantifying the sub-optimality of uniprocessor fixed priority non-pre-emptive scheduling. In: Proceedings real-time and network systems (RTNS), pp 1\u201310"},{"issue":"5","key":"9294_CR25","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s11241-015-9233-0","volume":"51","author":"RI Davis","year":"2015","unstructured":"Davis RI, Burns A, Baruah S, Rothvoss T, George L, Gettings O (2015a) Exact comparison of fixed priority and edf scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms. Real-Time Syst 51(5):566\u2013601. https:\/\/doi.org\/10.1007\/s11241-015-9233-0","journal-title":"Real-Time Syst"},{"key":"9294_CR26","unstructured":"Davis RI, Gettings O, Thekkilakattil A, Dobrin R, Punnekkat S (2015b) What is the exact speedup factor for fixed priority pre-emptive versus fixed priority non-pre-emptive scheduling? In: Proceedings real-time scheduling open problems seminar (RTSOPS), pp 23\u201324"},{"key":"9294_CR27","doi-asserted-by":"publisher","unstructured":"Davis RI, Thekkilakattil A, Gettings O, Dobrin R, Punnekkat S (2015c) Quantifying the exact sub-optimality of non-preemptive scheduling. In: Proceedings real-time systems symposium (RTSS), pp 96\u2013106. https:\/\/doi.org\/10.1109\/RTSS.2015.17","DOI":"10.1109\/RTSS.2015.17"},{"key":"9294_CR28","doi-asserted-by":"publisher","unstructured":"Davis RI, Cucu-Grosjean L, Bertogna M, Burns A (2016) A review of priority assignment in real-time systems. J Syst Archit 65:64\u201382. https:\/\/doi.org\/10.1016\/j.sysarc.2016.04.002 , http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1383762116300200","DOI":"10.1016\/j.sysarc.2016.04.002"},{"key":"9294_CR29","unstructured":"Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: Proceedings IFIP congress, pp 807\u2013813"},{"key":"9294_CR30","volume-title":"Preemptive and non-preemptive real-time uniprocessor scheduling","author":"L George","year":"1996","unstructured":"George L, Rivierre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Research report, INRIA"},{"key":"9294_CR31","doi-asserted-by":"publisher","unstructured":"Jeffay K, Stanat DF, Martel CU (1991) On non-preemptive scheduling of period and sporadic tasks. In: Proceedings real-time systems symposium (RTSS), pp 129\u2013139. https:\/\/doi.org\/10.1109\/REAL.1991.160366","DOI":"10.1109\/REAL.1991.160366"},{"key":"9294_CR32","doi-asserted-by":"publisher","unstructured":"Joseph M, Pandya P (1986) Finding response times in a real-time system. Comput J 29(5):390\u2013395. https:\/\/doi.org\/10.1093\/comjnl\/29.5.390 , http:\/\/comjnl.oxfordjournals.org\/content\/29\/5\/390.abstract , http:\/\/comjnl.oxfordjournals.org\/content\/29\/5\/390.full.pdf+html","DOI":"10.1093\/comjnl\/29.5.390"},{"issue":"4","key":"9294_CR33","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. J ACM 47(4):617\u2013643. https:\/\/doi.org\/10.1145\/347476.347479","journal-title":"J ACM"},{"key":"9294_CR34","doi-asserted-by":"publisher","unstructured":"Lehoczky JP (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings real-time systems symposium (RTSS), pp 201\u2013209. https:\/\/doi.org\/10.1109\/REAL.1990.128748","DOI":"10.1109\/REAL.1990.128748"},{"key":"9294_CR35","doi-asserted-by":"publisher","unstructured":"Lehoczky J, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: exact characterization and average case behavior. In: Proceedings real time systems symposium (RTSS), pp 166\u2013171. https:\/\/doi.org\/10.1109\/REAL.1989.63567","DOI":"10.1109\/REAL.1989.63567"},{"key":"9294_CR36","doi-asserted-by":"publisher","unstructured":"Leung JYT, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform Eval 2(4):237\u2013250. https:\/\/doi.org\/10.1016\/0166-5316(82)90024-4 , http:\/\/www.sciencedirect.com\/science\/article\/pii\/0166531682900244","DOI":"10.1016\/0166-5316(82)90024-4"},{"issue":"1","key":"9294_CR37","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"CL Liu","year":"1973","unstructured":"Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46\u201361. https:\/\/doi.org\/10.1145\/321738.321743","journal-title":"J ACM"},{"key":"9294_CR38","doi-asserted-by":"publisher","unstructured":"Lunniss W, Davis RI, Maiza C, Altmeyer S (2013) Integrating cache related pre-emption delay analysis into edf scheduling. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 75\u201384. https:\/\/doi.org\/10.1109\/RTAS.2013.6531081","DOI":"10.1109\/RTAS.2013.6531081"},{"key":"9294_CR39","unstructured":"OSEK\/VDX (2007) OSEK\/VDX operating system specification, version 2.2.3. Tech. rep. http:\/\/www.irisa.fr\/alf\/downloads\/puaut\/TPNXT\/images\/os223.pdf"},{"issue":"1","key":"9294_CR40","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF00365519","volume":"11","author":"I Ripoll","year":"1996","unstructured":"Ripoll I, Crespo A, Mok AK (1996) Improvement in feasibility testing for real-time tasks. Real-Time Syst 11(1):19\u201339. https:\/\/doi.org\/10.1007\/BF00365519","journal-title":"Real-Time Syst"},{"key":"9294_CR41","unstructured":"Short M (2010) The case for non-preemptive, deadline-driven scheduling in real-time embedded systems. In: Proceedings of the world congress on engineering (WCE), pp 399\u2013404"},{"key":"9294_CR42","unstructured":"Spuri M (1996) Analysis of deadline scheduled real-time systems. INRIA Research Report RR-2772 . https:\/\/hal.inria.fr\/inria-00073920\/document"},{"key":"9294_CR43","doi-asserted-by":"publisher","unstructured":"Thekkilakattil A, Dobrin R, Punnekkat S (2013) Quantifying the sub-optimality of non-preemptive real-time scheduling. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 113\u2013122. https:\/\/doi.org\/10.1109\/ECRTS.2013.22","DOI":"10.1109\/ECRTS.2013.22"},{"key":"9294_CR44","doi-asserted-by":"publisher","unstructured":"Thekkilakattil A, Baruah S, Dobrin R, Punnekkat S (2014) The global limited preemptive earliest deadline first feasibility of sporadic real-time tasks. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 301\u2013310. https:\/\/doi.org\/10.1109\/ECRTS.2014.21","DOI":"10.1109\/ECRTS.2014.21"},{"issue":"3","key":"9294_CR45","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s11241-015-9222-3","volume":"51","author":"A Thekkilakattil","year":"2015","unstructured":"Thekkilakattil A, Dobrin R, Punnekkat S (2015) The limited-preemptive feasibility of real-time tasks on uniprocessors. Real-Time Syst 51(3):247\u2013273. https:\/\/doi.org\/10.1007\/s11241-015-9222-3","journal-title":"Real-Time Syst"},{"issue":"2","key":"9294_CR46","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01088593","volume":"6","author":"K Tindell","year":"1994","unstructured":"Tindell K, Burns A, Wellings AJ (1994) An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Syst 6(2):133\u2013151. https:\/\/doi.org\/10.1007\/BF01088593","journal-title":"Real-Time Syst"},{"key":"9294_CR47","unstructured":"von der Bruggen G, Chen JJ, Huang WH (2015) Schedulability and optimization analysis for non-preemptive static priority scheduling based on task utilisation and blocking factors. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 90\u2013101"},{"key":"9294_CR48","doi-asserted-by":"publisher","unstructured":"von der Bruggen G, Chen JJ, Davis RI, Huang WH (2016) Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling. Inf Process Lett. https:\/\/doi.org\/10.1016\/j.ipl.2016.08.001 , http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019016301090","DOI":"10.1016\/j.ipl.2016.08.001"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-017-9294-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-017-9294-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-017-9294-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T04:53:46Z","timestamp":1570251226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-017-9294-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,28]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9294"],"URL":"https:\/\/doi.org\/10.1007\/s11241-017-9294-3","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"type":"print","value":"0922-6443"},{"type":"electronic","value":"1573-1383"}],"subject":[],"published":{"date-parts":[[2017,10,28]]}}}