The DOI matches its Crossref record; 77 of the 77 references it cites were found in a registry or an index.
A survey of hard real-time scheduling for multiprocessor systems
Abstract
This survey covers hard real-time scheduling algorithms and schedulability analysis techniques for homogeneous multiprocessor systems. It reviews the key results in this field from its origins in the late 1960s to the latest research published in late 2009. The survey outlines fundamental results about multiprocessor real-time scheduling that hold independent of the scheduling algorithms employed. It provides a taxonomy of the different scheduling methods, and considers the various performance metrics that can be used for comparison purposes. A detailed review is provided covering partitioned, global, and hybrid scheduling algorithms, approaches to resource sharing, and the latest results from empirical investigations. The survey identifies open issues, key research challenges, and likely productive research directions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Scheduling algorithms for multiprogramming in a hard-real-time environment
Liu, C. L., & Layland, J. W. (1973) · Journal of the ACM · doi:10.1145/321738.321743 · Cited by 8,433
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
LIU, C. L., & LAYLAND, J. W. (2002) · Readings in Hardware/Software Co-Design · doi:10.1016/b978-155860702-6/50016-8 · Cited by 3,233
Priority inheritance protocols: an approach to real-time synchronization
Sha, L., Rajkumar, R., & Lehoczky, J. P. (1990) · IEEE Transactions on Computers · doi:10.1109/12.57058 · Cited by 2,244
The worst-case execution-time problem—overview of methods and survey of tools
Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann, R., Mitra, T., et al. (2008) · ACM Transactions on Embedded Computing Systems · doi:10.1145/1347375.1347389 · Cited by 1,871
Hard real-time computing systems: Predictable scheduling algorithms and applications
(1998) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(98)90205-x · Cited by 1,327
On the complexity of fixed-priority scheduling of periodic, real-time tasks
Leung, J. Y.-T., & Whitehead, J. (1982) · Performance Evaluation · doi:10.1016/0166-5316(82)90024-4 · Cited by 1,154
Measuring the Performance of Schedulability Tests
Bini, E., & Buttazzo, G. (2005) · Real-Time Systems · doi:10.1007/s11241-005-0507-9 · Cited by 917
Stack-based scheduling of realtime processes
Baker, T. P. (1991) · Real-Time Systems · doi:10.1007/bf00365393 · Cited by 817
Fixed priority scheduling of periodic task sets with arbitrary deadlines
Lehoczky, J. P. (1990) · [1990] Proceedings 11th Real-Time Systems Symposium · doi:10.1109/real.1990.128748 · Cited by 802
Proportionate Progress: A Notion of Fairness in Resource Allocation
Baruah, S., Cohen, N. K., Plaxton, C. G., & Varvel, D. (1996) · Algorithmica · doi:10.1007/bf01940883 · Cited by 737
Preemptively scheduling hard-real-time sporadic tasks on one processor
Baruah, S., Mok, A. K., & Rosier, L. E. (1990) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.1990.128746 · Cited by 734
Techniques for Multiprocessor Global Schedulability Analysis
Baruah, S. (2007) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/rtss.2007.35 · Cited by 708
Real Time Scheduling Theory: A Historical Perspective
Sha, L., Abdelzaher, T., årzén, K.-E., Cervin, A., Baker, T., Burns, A., Buttazzo, G., Caccamo, M., Lehoczky, J., & Mok, A. K. (2004) · Real-Time Systems · doi:10.1023/b:time.0000045315.61234.1e · Cited by 614
Self-citationBaruah, S., Rosier, L. E., & Howell, R. R. (1990) · Real-Time Systems · doi:10.1007/bf01995675 · Cited by 609
Speed is as powerful as clairvoyance
Kalyanasundaram, B., & Pruhs, K. (2000) · Journal of the ACM · doi:10.1145/347476.347479 · Cited by 561
Multiprocessor online scheduling of hard-real-time tasks
Dertouzos, M. L., & Mok, A. K. (1989) · IEEE Transactions on Software Engineering · doi:10.1109/32.58762 · Cited by 437
Real-time synchronization protocols for multiprocessors
Rajkumar, R., Sha, L., & Lehoczky, J. P. (2003) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.1988.51121 · Cited by 403
Fixed priority pre-emptive scheduling: An historical perspective
Audsley, N., Burns, A., Davis, R. I., Tindell, K., & Wellings, A. J. (1995) · Real-Time Systems · doi:10.1007/bf01094342 · Cited by 365
Self-citationStatic-priority scheduling on multiprocessors
Andersson, B. A., Baruah, S., & Jonsson, J. A. (2005) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.2001.990610 · Cited by 335
OPTIMAL PRIORITY ASSIGNMENT AND FEASIBILITY OF STATIC PRIORITY TASKS WITH ARBITRARY START TIMES
Audsley, N. (2007) · Cited by 318
Divisible Load Theory: A New Paradigm for Load Scheduling in Distributed Systems
Bharadwaj, V., Ghose, D., & Robertazzi, T. G. (2003) · Cluster Computing · doi:10.1023/a:1020958815308 · Cited by 296
Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors
Goossens, J., Funk, S., & Baruah, S. (2003) · Real-Time Systems · doi:10.1023/a:1025120124771 · Cited by 290
Multiprocessor EDF and deadline monotonic schedulability analysis
Baker, T. P. (2004) · International Symposium on System-on-Chip · doi:10.1109/real.2003.1253260 · Cited by 275
New strategies for assigning real-time tasks to multiprocessor systems
Burchard, A., Liebeherr, J., Oh, Y., & Son, S. H. (1995) · IEEE Transactions on Computers · doi:10.1109/12.477248 · Cited by 259
On priority assignment in fixed priority scheduling
Audsley, N. (2001) · Information Processing Letters · doi:10.1016/s0020-0190(00)00165-4 · Cited by 256
Davis, R. I., & Burns, A. (2009) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/rtss.2009.31 · Cited by 255
Self-citationMinimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip
Gai, P., Lipari, G., & Natale, M. D. (2005) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.2001.990598 · Cited by 233
Fast scheduling of periodic tasks on multiple resources
Baruah, S., Gehrke, J. E., & Plaxton, C. G. (2002) · International Parallel Processing Symposium · doi:10.1109/ipps.1995.395946 · Cited by 218
Optimal time-critical scheduling via resource augmentation (extended abstract)
Phillips, C. A., Stein, C., Torng, E. K., & Wein, J. M. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258570 · Cited by 195
Sustainable Scheduling Analysis
Baruah, S., & Burns, A. (2006) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/rtss.2006.47 · Cited by 189
Self-citationMultiprocessor Scheduling with Few Preemptions
Andersson, B. A., & Tovar, E. (2006) · IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) · doi:10.1109/rtcsa.2006.45 · Cited by 186
Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems
López, J. M., Díaz, J. L. G., & Garcia, D. F. (2004) · Real-Time Systems · doi:10.1023/b:time.0000033378.56741.14 · Cited by 179
Adapting Futures: Scalability for Real-World Computing
Helander, J., Serg, R., Veanes, M., & Roy, P. (2007) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/rtss.2007.41 · Cited by 178
Hierarchical Scheduling Framework for Virtual Clustering of Multiprocessors
Shin, I., Easwaran, A., & Lee, I. (2008) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/ecrts.2008.28 · Cited by 174
Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems
Lopez, J. M., García, M., Díaz, J. L. G., & Garcia, D. F. (2002) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/emrts.2000.853989 · Cited by 173
An analysis of EDF schedulability on a multiprocessor
Baker, T. P. (2005) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2005.88 · Cited by 172
New Response Time Bounds for Fixed Priority Multiprocessor Scheduling
Guan, N., Stigge, M., Yi, W., & Yu, G. (2009) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/rtss.2009.11 · Cited by 158
Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor Assignment
Oh, D., & Bakker, T. P. (1998) · Real-Time Systems · doi:10.1023/a:1008098013753 · Cited by 148
Partitioned Fixed-Priority Preemptive Scheduling for Multi-core Processors
Lakshmanan, K., Rajkumar, R., & Lehoczky, J. P. (2009) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/ecrts.2009.33 · Cited by 140
The Partitioned Multiprocessor Scheduling of Sporadic Task Systems
Baruah, S., & Fisher, N. (2006) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/rtss.2005.40 · Cited by 137
Heo, J., Henriksson, D., Liu, X., & Abdelzaher, T. (2007) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/rtss.2007.48 · Cited by 135
Deadline-based scheduling of periodic task systems on multiprocessors
Srinivasan, A., & Baruah, S. (2002) · Information Processing Letters · doi:10.1016/s0020-0190(02)00231-4 · Cited by 133
On-line scheduling on uniform multiprocessors
Funk, S., Goossens, J., & Baruah, S. (2005) · IEEE Real-Time Systems Symposium (RTSS) · doi:10.1109/real.2001.990609 · Cited by 123
Bounds on multiprocessing anomalies and related packing algorithms
Graham, R. L. (1971) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1478873.1478901 · Cited by 118
Semi-partitioned Scheduling of Sporadic Task Systems on Multiprocessors
Kato, S., Yamasaki, N., & Ishikawa, Y. (2009) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/ecrts.2009.22 · Cited by 117
Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition
Andersson, B. A., & Jonsson, J. A. (2002) · IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) · doi:10.1109/rtcsa.2000.896409 · Cited by 116
Allocating fixed-priority periodic tasks on multiprocessor systems
Oh, Y., & Son, S. H. (1995) · Real-Time Systems · doi:10.1007/bf01088806 · Cited by 115
Real-time computing with lock-free shared objects
Anderson, J. H., Ramamurthy, S., & Kevin Jeffay, B. (1997) · ACM Transactions on Computer Systems · doi:10.1145/253145.253159 · Cited by 113
The Partitioned Scheduling of Sporadic Tasks According to Static-Priorities
Fisher, N., Baruah, S., & Baker, T. P. (2006) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/ecrts.2006.30 · Cited by 113
Andersson, B. A., & Jonsson, J. A. (2004) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/emrts.2003.1212725 · Cited by 112
Gai, P., Natale, M. D., Lipari, G., Ferrari, A., Gabellini, C., & Marceca, P. (2004) · IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) · doi:10.1109/rttas.2003.1203051 · Cited by 112
Integrating job parallelism in real-time scheduling theory
Collette, S., Cucu, L., & Goossens, J. (2007) · Information Processing Letters · doi:10.1016/j.ipl.2007.11.014 · Cited by 111
On-line scheduling of real-time tasks
Hong, K. S., & Leung, J. Y. ‐. (1992) · IEEE Transactions on Computers · doi:10.1109/12.166609 · Cited by 111
Validating timing constraints in multiprocessor and distributed real-time systems
Ha, R., & Liu, J. W. S. (2002) · Proceedings of the ... International Conference on Distributed Computing Systems/Proceedings of the International Conference on Distributed Computing Systems · doi:10.1109/icdcs.1994.302407 · Cited by 105
Semi-partitioned Fixed-Priority Scheduling on Multiprocessors
Kato, S., & Yamasaki, N. (2009) · IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) · doi:10.1109/rtas.2009.9 · Cited by 95
Real-Time Scheduling with Task Splitting on Multiprocessors
Kato, S., & Yamasaki, N. (2007) · IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) · doi:10.1109/rtcsa.2007.61 · Cited by 93
Portioned EDF-based scheduling on multiprocessors
Kato, S., & Yamasaki, N. (2008) · ACM International Conference on Embedded Software (EMSOFT) · doi:10.1145/1450058.1450078 · Cited by 92
Rate-monotonic scheduling on uniform multiprocessors
Baruah, S., & Goossens, J. (2003) · IEEE Transactions on Computers · doi:10.1109/tc.2003.1214344 · Cited by 91
An Analysis of Fixed-Priority Schedulability on a Multiprocessor
Baker, T. P. (2006) · Real-Time Systems · doi:10.1007/s11241-005-4686-1 · Cited by 84
Speed is as powerful as clairvoyance [scheduling problems]
Kalyanasundaram, B., & Pruhs, K. R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492478 · Cited by 83
The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems
Baruah, S., & Fisher, N. (2006) · IEEE Transactions on Computers · doi:10.1109/tc.2006.113 · Cited by 82
Lauzac, S., Melhem, R., & Mossé, D. (2002) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/emwrts.1998.685084 · Cited by 81
Schedulability analysis of global edf
Baruah, S., & Baker, T. P. (2007) · Real-Time Systems · doi:10.1007/s11241-007-9047-9 · Cited by 79
Baker, T. P., Cirinei, M., & Bertogna, M. (2008) · Real-Time Systems · doi:10.1007/s11241-008-9061-6 · Cited by 72
On-line multiprocessor scheduling algorithms for real-time tasks
Lee, S. K. (2002) · IEEE Region 10 Conference (TENCON) · doi:10.1109/tencon.1994.369148 · Cited by 71
Global Static-Priority Preemptive Multiprocessor Scheduling with Utilization Bound 38%
Andersson, B. A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92221-6_7 · Cited by 70
Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling
Lopez, J. M., Díaz, J. L. G., & Garcia, D. F. (2004) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2004.25 · Cited by 70
Real-Time Divisible Load Scheduling for Cluster Computing
Lin, X., Lü, Y., Deogun, J. S., & Goddard, S. (2007) · IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) · doi:10.1109/rtas.2007.29 · Cited by 63
Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling
López, J. M., García, M., Díaz, J. L. G., & Garcia, D. F. (2003) · Real-Time Systems · doi:10.1023/a:1021749005009 · Cited by 58
Scalably scheduling processes with arbitrary speedup curves
Edmonds, J. A., & Pruhs, K. R. (2009) · doi:10.5555/1496770.1496845 · Cited by 54
Portioned static-priority scheduling on multiprocessors
Kato, S., & Yamasaki, N. (2008) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2008.4536299 · Cited by 52
Using Randomized Caches in Probabilistic Real-Time Systems
Quiñones, E., Berger, E. D., Bernat, G., & Cazorla, F. J. (2009) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/ecrts.2009.30 · Cited by 50
Multiprocessor fixed-priority scheduling with restricted interprocessor migrations
Baruah, S., & Carpenter, J. (2004) · Euromicro Conference on Real-Time Systems (ECRTS) · doi:10.1109/emrts.2003.1212744 · Cited by 48
Feasibility Intervals for Fixed-Priority Real-Time Scheduling on Uniform Multiprocessors
Cucu, L., & Goossens, J. (2006) · IEEE International Conference on Emerging Technologies and Factory Automation (ETFA) · doi:10.1109/etfa.2006.355388 · Cited by 47
Analyzing fixed-priority global multiprocessor scheduling
Lundberg, L. (2003) · IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) · doi:10.1109/rttas.2002.1137389 · Cited by 44
Cited by
Marwedel, P. (2021) · Embedded Systems · doi:10.1007/978-3-030-60910-8 · Cited by 605
A taxonomy for task allocation problems with temporal and ordering constraints
Nunes, E., Manner, M., Mitiche, H., & Gini, M. (2017) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2016.10.008 · Cited by 252
Chen, N., Kurniawan, C., Nakahira, Y., Chen, L., & Low, S. H. (2022) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2021.3138615 · Cited by 39
Metadata
- Authors
- Davis, R. I., & Burns, A.
- Venue
- ACM Computing Surveys
- Published
- 2011-10
- Volume
- 43
- Issue
- 4
- Pages
- 1-44
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W1968005108
- Cited by
- 907
- References
- 77
- FWCI
- 113.91
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.