{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:17:03Z","timestamp":1762521423635},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2011,7,13]],"date-time":"2011-07-13T00:00:00Z","timestamp":1310515200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s11241-011-9130-0","type":"journal-article","created":{"date-parts":[[2011,7,12]],"date-time":"2011-07-12T11:35:26Z","timestamp":1310470526000},"page":"389-429","source":"Crossref","is-referenced-by-count":53,"title":["DP-Fair: a unifying theory for optimal hard real-time multiprocessor scheduling"],"prefix":"10.1007","volume":"47","author":[{"given":"Shelby","family":"Funk","sequence":"first","affiliation":[]},{"given":"Greg","family":"Levin","sequence":"additional","affiliation":[]},{"given":"Caitlin","family":"Sadowski","sequence":"additional","affiliation":[]},{"given":"Ian","family":"Pye","sequence":"additional","affiliation":[]},{"given":"Scott","family":"Brandt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,7,13]]},"reference":[{"key":"9130_CR1","volume-title":"IEEE real-time and embedded technology and applications symposium (RTAS)","author":"T Abdelzaher","year":"2002","unstructured":"Abdelzaher T, Andersson B, Jonsson J, Sharma V, Nguyen M (2002) The aperiodic multiprocessor utilization bound for liquid tasks. In: IEEE real-time and embedded technology and applications symposium (RTAS), IEEE Computer Society Press, San Jose, California"},{"key":"9130_CR2","volume-title":"Euromicro conference on real-time systems (ECRTS)","author":"B Andersson","year":"2008","unstructured":"Andersson B, Bletsas K (2008) Sporadic multiprocessor scheduling with few preemptions. In: Euromicro conference on real-time systems (ECRTS)"},{"key":"9130_CR3","volume-title":"IEEE embedded and real-time computing systems and applications (RTCSA)","author":"B Andersson","year":"2006","unstructured":"Andersson B, Tovar E (2006) Multiprocessor scheduling with few preemptions. In: IEEE embedded and real-time computing systems and applications (RTCSA)"},{"key":"9130_CR4","volume-title":"IEEE real-time systems symposium (RTSS)","author":"B Andersson","year":"2008","unstructured":"Andersson B, Bletsas K, Baruah SK (2008) Scheduling arbitrary deadline sporadic task systems on multiprocessors. In: IEEE real-time systems symposium (RTSS)"},{"key":"9130_CR5","volume-title":"IEEE real-time systems symposium (RTSS)","author":"T Baker","year":"2003","unstructured":"Baker T (2003) Multiprocessor EDF and deadline monotonic schedulability analysis. In: IEEE real-time systems symposium (RTSS)"},{"key":"9130_CR6","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1109\/TPDS.2005.88","volume":"16","author":"T Baker","year":"2005","unstructured":"Baker T (2005) An analysis of EDF schedulability on a multiprocessor. IEEE Trans Parallel Distrib Syst 16:460\u2013768","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"2","key":"9130_CR7","first-page":"195","volume":"1","author":"SK Baruah","year":"2004","unstructured":"Baruah SK, Carpenter J (2004) Multiprocessor fixed-priority scheduling with restricted interprocessor migrations. J Embedd Comput 1(2):195\u2013202","journal-title":"J Embedd Comput"},{"issue":"6","key":"9130_CR8","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1007\/BF01940883","volume":"15","author":"SK Baruah","year":"1996","unstructured":"Baruah SK, Cohen NK, Plaxton CG, Varvel D (1996) Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15(6):600\u2013625","journal-title":"Algorithmica"},{"key":"9130_CR9","volume-title":"6th international workshop on operating systems platforms for embedded real-time applications (OSPERT)","author":"A Bastoni","year":"2010","unstructured":"Bastoni A, Brandenburg B, Anderson JH (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: 6th international workshop on operating systems platforms for embedded real-time applications (OSPERT)"},{"issue":"10","key":"9130_CR10","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1109\/12.805154","volume":"48","author":"G Buttazzo","year":"1999","unstructured":"Buttazzo G, Sensini F (1999) Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time environments. IEEE Trans Comput 48(10):1035\u20131052","journal-title":"IEEE Trans Comput"},{"key":"9130_CR11","volume-title":"Handbook on scheduling algorithms, methods, and models","author":"J Carpenter","year":"2004","unstructured":"Carpenter J, Funk S, Holman P, Srinivasan A, Anderson JH, Baruah SK (2004) A\u00a0categorization of real-time multiprocessor scheduling problems and algorithms. In: Leung JYT (ed) Handbook on scheduling algorithms, methods, and models. Chapman Hall\/CRC, London"},{"key":"9130_CR12","volume-title":"IEEE real-time systems symposium (RTSS)","author":"SY Chen","year":"2008","unstructured":"Chen SY, Hsueh CW (2008) Optimal dynamic-priority real-time scheduling algorithms for uniform multiprocessors. In: IEEE real-time systems symposium (RTSS)"},{"key":"9130_CR13","volume-title":"IEEE real-time systems symposium (RTSS)","author":"H Cho","year":"2006","unstructured":"Cho H, Ravindran B, Jensen E (2006) An optimal real-time scheduling algorithm for multiprocessors. In: IEEE real-time systems symposium (RTSS)"},{"issue":"12","key":"9130_CR14","first-page":"2859","volume":"E85-B","author":"SK Cho","year":"2002","unstructured":"Cho SK, Lee S, Han A, Lin KJ (2002) Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans Commun E85-B(12):2859\u20132867","journal-title":"IEICE Trans Commun"},{"key":"9130_CR15","doi-asserted-by":"crossref","unstructured":"Davis RI, Burns A (2011, accepted for publication) A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys","DOI":"10.1145\/1978802.1978814"},{"key":"9130_CR16","volume-title":"Proceedings of the IFIP congress","author":"M Dertouzos","year":"1974","unstructured":"Dertouzos M (1974) Control robotics: the procedural control of physical processors. In: Proceedings of the IFIP congress"},{"issue":"12","key":"9130_CR17","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/32.58762","volume":"15","author":"M Dertouzos","year":"1989","unstructured":"Dertouzos M, Mok AK (1989) Multiprocessor scheduling in a hard real-time environment. IEEE Trans Softw Eng 15(12):1497\u20131506","journal-title":"IEEE Trans Softw Eng"},{"issue":"1","key":"9130_CR18","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1287\/opre.26.1.127","volume":"26","author":"S Dhall","year":"1978","unstructured":"Dhall S, Liu C (1978) On a real-time scheduling problem. Oper Res 26(1):127\u2013140","journal-title":"Oper Res"},{"key":"9130_CR19","volume-title":"International workshop on analysis tools and methodologies for embedded and real-time systems (WATERS)","author":"P Emberson","year":"2010","unstructured":"Emberson P, Stafford R, Jonsson J, Davis RI (2010) Techniques for the synthesis of multiprocessor tasksets. In: International workshop on analysis tools and methodologies for embedded and real-time systems (WATERS), Brussels, Belgium"},{"issue":"1\u20132","key":"9130_CR20","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/s11241-010-9092-7","volume":"45","author":"N Fisher","year":"2010","unstructured":"Fisher N, Goossens J, Baruah S (2010) Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible. Real-Time Syst 45(1\u20132):26\u201371","journal-title":"Real-Time Syst"},{"key":"9130_CR21","volume-title":"ACM\/IEEE conference on supercomputing (SC06)","author":"F Franchetti","year":"2006","unstructured":"Franchetti F, Voronenko Y, Puschel M (2006) FFT program generation for shared memory: SMP and multicore. In: ACM\/IEEE conference on supercomputing (SC06)"},{"key":"9130_CR22","volume-title":"IEEE embedded and real-time computing systems and applications (RTCSA)","author":"K Funaoka","year":"2008","unstructured":"Funaoka K, Kato S, Yamasaki N (2008a) New abstraction for optimal real-time scheduling on multiprocessors. In: IEEE embedded and real-time computing systems and applications (RTCSA)"},{"key":"9130_CR23","volume-title":"Euromicro conference on real-time systems (ECRTS)","author":"K Funaoka","year":"2008","unstructured":"Funaoka K, Kato S, Yamasaki N (2008b) Work-conserving optimal real-time scheduling on multiprocessors. In: Euromicro conference on real-time systems (ECRTS)"},{"key":"9130_CR24","volume-title":"Conference on Real-Time and Network Systems (RTNS)","author":"S Funk","year":"2009","unstructured":"Funk S, Nadadur V (2009) LRE-TL: an optimal multiprocessor algorithm for sporadic task sets. In: Conference on Real-Time and Network Systems (RTNS)"},{"key":"9130_CR25","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1109\/12.166609","volume":"41","author":"KS Hong","year":"1992","unstructured":"Hong KS, Leung JYT (1992) On-line scheduling of real-time tasks. IEEE Trans Comput 41:1326\u20131331","journal-title":"IEEE Trans Comput"},{"key":"9130_CR26","volume-title":"IEEE embedded and real-time computing systems and applications (RTCSA)","author":"S Kato","year":"2007","unstructured":"Kato S, Yamasaki N (2007) Real-time scheduling with task splitting on multiprocessors. In: IEEE embedded and real-time computing systems and applications (RTCSA)"},{"key":"9130_CR27","volume-title":"ACM international conference on embedded software (EMSOFT)","author":"S Kato","year":"2008","unstructured":"Kato S, Yamasaki N (2008) Portioned EDF-based scheduling on multiprocessors. In: ACM international conference on embedded software (EMSOFT)"},{"issue":"1","key":"9130_CR28","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1006\/jpdc.1997.1327","volume":"43","author":"A Khemka","year":"1997","unstructured":"Khemka A, Shyamasundar RK (1997) An optimal multiprocessor real-time scheduling algorithm. J Parallel Distrib Comput 43(1):37\u201345","journal-title":"J Parallel Distrib Comput"},{"key":"9130_CR29","volume-title":"IEEE real-time systems symposium (RTSS)","author":"K Lakshmanan","year":"2009","unstructured":"Lakshmanan K, de Niz D, Rajkumar R (2009) Coordinated task scheduling, allocation and synchronization on multiprocessors. In: IEEE real-time systems symposium (RTSS). IEEE Computer Society, Los Alamitos"},{"issue":"1","key":"9130_CR30","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01553887","volume":"4","author":"J Leung","year":"1989","unstructured":"Leung J (1989) A new algorithm for scheduling periodic, real-time tasks. Algorithmica 4(1):209\u2013219","journal-title":"Algorithmica"},{"key":"9130_CR31","volume-title":"IEEE real-time systems symposium (RTSS)","author":"C Lin","year":"2005","unstructured":"Lin C, Brandt SA (2005) Improving soft real-time performance through better slack management. In: IEEE real-time systems symposium (RTSS)"},{"key":"9130_CR32","volume-title":"IEEE real-time systems symposium (RTSS)","author":"C Lin","year":"2006","unstructured":"Lin C, Kaldewey T, Povzner A, Brandt SA (2006) Diverse soft real-time processing in an integrated system. In: IEEE real-time systems symposium (RTSS)"},{"issue":"1","key":"9130_CR33","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"C Liu","year":"1973","unstructured":"Liu C, Layland J (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46\u201361","journal-title":"J ACM"},{"key":"9130_CR34","volume-title":"Euromicro conference on real-time systems (ECRTS)","author":"JM L\u00f3pez","year":"2000","unstructured":"L\u00f3pez JM, Garcia M, Diaz JL, Garcia DF (2000) Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems. In: Euromicro conference on real-time systems (ECRTS)"},{"issue":"1","key":"9130_CR35","first-page":"1","volume":"6","author":"R McNaughton","year":"1959","unstructured":"McNaughton R (1959) Scheduling with deadlines and loss functions. Mach Sci 6(1):1\u201312","journal-title":"Mach Sci"},{"key":"9130_CR36","unstructured":"Mok AK (1983) Fundamental design problems of distributed systems for the hard-real-time environment. PhD thesis, Massachusetts Institute of Technology"},{"key":"9130_CR37","volume-title":"IEEE embedded and real-time computing systems and applications (RTCSA)","author":"S Oh","year":"1998","unstructured":"Oh S, Yang S (1998) A\u00a0modified least-laxity-first scheduling algorithm for real-time tasks. In: IEEE embedded and real-time computing systems and applications (RTCSA)"},{"key":"9130_CR38","volume-title":"ACM symposium on the theory of computing (STOC)","author":"C Phillips","year":"1997","unstructured":"Phillips C, Stein C, Torng E, Wein J (1997) Optimal time-critical scheduling via resource augmentation. In: ACM symposium on the theory of computing (STOC)"},{"issue":"1","key":"9130_CR39","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF02341920","volume":"1","author":"B Sprunt","year":"1989","unstructured":"Sprunt B, Sha L, Lehoczky J (1989) Aperiodic task scheduling for hard-real-time systems. Real-Time Syst 1(1):27\u201360","journal-title":"Real-Time Syst"},{"key":"9130_CR40","volume-title":"International symposium on parallel and distributed processing (IPDPS)","author":"A Srinivasan","year":"2003","unstructured":"Srinivasan A, Holman P, Anderson JH, Baruah SK (2003) The case for fair multiprocessor scheduling. In: International symposium on parallel and distributed processing (IPDPS)"},{"key":"9130_CR41","unstructured":"Stafford R (2006) Random vectors with fixed sum. http:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/9700"},{"key":"9130_CR42","volume-title":"IEEE real-time systems symposium (RTSS)","author":"D Zhu","year":"2003","unstructured":"Zhu D, Moss\u00e9 D, Melhem R (2003) Multiple-resource periodic scheduling problem: how much fairness in necessary. In: IEEE real-time systems symposium (RTSS)"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-011-9130-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-011-9130-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-011-9130-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T18:45:54Z","timestamp":1560365154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-011-9130-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,13]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9130"],"URL":"https:\/\/doi.org\/10.1007\/s11241-011-9130-0","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,13]]}}}