Robert I. Davis
Skip Abstract Section
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.
- Anderson, J., Ramamurthy, S., and Jeffay, K. 1997. Real-time computing with lock-free shared objects. ACM Trans. Comp. Syst. 15, 2, 134--165. Google Scholar
Digital Library
- Anderson, J. and Srinivasan, A. 2000. Early-release fair scheduling. In Proceedings of the Euromicro Conference on Real-Time Systems. Google ScholarDigital Library
- Anderson, J. and Srinivasan, A. 2000b. Pfair scheduling: Beyond periodic task systems. In Proceedings of the 7th International Workshop on Real-Time Computing Systems and Applications. Google ScholarDigital Library
- Anderson, J. and Srinivasan, A. 2001a. Mixed Pfair/Erfair scheduling of asynchronous periodic tasks. In Proceedings of the 13th Euromicro Conference on Real-Time Systems. Google ScholarDigital Library
- Andersson, B. and Jonsson, J. 2000a. Fixed-priority preemptive multiprocessor scheduling: To partition or not to partition, In Proceedings of the International Workshop on Real-Time Computing Systems and Applications. Google ScholarDigital Library
- Andersson, B. and Jonsson, J. 2000b. Some insights on fixed-priority pre-emptive non-partitioned multiprocessor scheduling. In Proceedings of the Real-Time Systems Symposium—Work-in-Progress Session.Google Scholar
- Andersson, B., Baruah, S., and Jonsson, J. 2001. Static-priority scheduling on multiprocessors. In Proceedings of the 22nd IEEE Real-Time Systems Symposium. 193--202. Google ScholarDigital Library
- Andersson, B. 2003. Static-priority scheduling on multiprocessors. Ph.D. dissertation. Chalmers University of Technology, Gothenburg, Sweden. Google ScholarDigital Library
- Andersson, B. and Jonsson, J. 2003. The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50%. In Proceedings of the 15th Euromicro Conference on Real-Time Systems.Google Scholar
- Andersson, B. and Tovar, E. 2006. Multiprocessor scheduling with few preemptions. In Proceedings of the International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). Google ScholarDigital Library
- Andersson, B., Bletsas, K., and Baruah, S. K. 2008. Scheduling arbitrary deadline sporadic task systems on multiprocessors. In Proceedings of the Real-Time Systems Symposium. 384--393. Google ScholarDigital Library
- Andersson, B. and Bletsas, K. 2008. Sporadic multiprocessor scheduling with few preemptions. In Proceedings of the Euromicro Conference on Real-Time Systems. 243--252. Google ScholarDigital Library
- Andersson, B. 2008. Global static-priority preemptive multiprocessor scheduling with utilization bound 38%. In Proceedings of the 12th International Conference on Principles of Distributed Systems. Google ScholarDigital Library
- Audsley, N. C. 1991. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Tech. rep. YCS 164. Dept. Computer Science, University of York, York, U.K.Google Scholar
- Audsley, N. C., Burns, A., Davis, R. I., Tindell, K. W., and Wellings, A. J. 1996. Fixed priority scheduling: an historical perspective. Real-Time Syst. 8, 3, 173--198. Google ScholarDigital Library
- Audsley, N. C. 2001. On priority assignment in fixed priority scheduling. Inform. Process. Lett. 79, 1, 39--44. Google ScholarDigital Library
- Baker, T. P. 1991. Stack-based scheduling of real-time processes. Real-Time Syst. J. 3, 1, 67--100. Google ScholarDigital Library
- Baker, T. P. 2003. Multiprocessor EDF and deadline monotonic schedulability analysis. In Proceedings of the 24th IEEE Real-Time Systems Symposium. 120--129. Google ScholarDigital Library
- Baker, T. P. 2005. An analysis of EDF scheduling on a multiprocessor. IEEE Trans. Parall. Distrib. Syst. 15, 8, 760--768. Google ScholarDigital Library
- Baker, T. P. 2006a. An analysis of fixed-priority scheduling on a multiprocessor. Real Time Syst. 32, 1-2, 49--71. Google ScholarDigital Library
- Baker, T. P. 2006b. A comparison of global and partitioned EDF schedulability tests for multiprocessors. In Proceedings of the International Conference on Real-Time and Network Systems. 119--130.Google Scholar
- Baker, T. P. and Cirinei, M. 2006. A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline tasks. In Proceedings of the Work-In-Progress (WIP) Session of the 27th IEEE Real-Time Systems Symposium. Google ScholarDigital Library
- Baker, T. P. and Baruah, S. K. 2007a. Schedulability analysis of multiprocessor sporadic task systems. In Handbook of Real-Time and Embedded Systems, I. Lee, Joseph Y.-T. Leung, and S. H. Son, Eds., Chapman Hall/CRC Press.Google Scholar
- Baker, T. P. and Baruah, S. K. 2007b. Schedulability analysis of multiprocessor sporadic task systems. Tech. rep. TR-060601. Florida State University, Tallahassee, FL.Google Scholar
- Baker, T. P., Cirinei, M., and Bertogna, M. 2008. EDZL scheduling analysis. Real-Time Syst. 40, 3, 264--289. Google ScholarDigital Library
- Baker, T. P. and Baruah, S. K. 2008. Schedulability analysis of global EDF. Real-Time Syst. 38, 223--235. Google ScholarDigital Library
- Baker, T. P. and Baruah, S. K. 2009. Sustainable multiprocessor scheduling of sporadic task systems. In Proceedings of the EuroMicro Conference on Real-Time Systems. 141--150. Google ScholarDigital Library
- Baruah, S. K., Mok, A. K., and Rosier, L. E. 1990a. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of the Real-Time System Symposium. 182--190.Google Scholar
- Baruah, S. K., Rosier, L. E., and Howell, R. R. 1990b. Algorithms and complexity: Concerning the preemptive scheduling of periodic real-time tasks on one processor. Real-Time Syst. 2, 4, 301--324. Google ScholarDigital Library
- Baruah, S. K., Gehrke, J., and Plaxton, C. G. 1995. Fast scheduling of periodic tasks on multiple resources. In Proceedings of the International Parallel Processing Symposium. Google ScholarDigital Library
- Baruah, S. K., Cohen, N., Plaxton, G., and Varvel, D. 1996. Proportionate progress: A notion of fairness in resource allocation. Algorithmica 15, 6, 600--625.Google ScholarDigital Library
- Baruah, S. K. and Goossens, J. 2003. Rate-monotonic scheduling on uniform multiprocessors. IEEE Trans. Comp. 52, 7, 966--970. Google ScholarDigital Library
- Baruah, S. K. and Carpenter, J. 2003. Multiprocessor fixed-priority scheduling with restricted interprocessor migrations. In Proceedings of the EuroMicro Conference on Real-Time Systems. 195--202.Google Scholar
- Baruah, S. K. and Fisher, N. 2005. Partitioned multiprocessor scheduling of sporadic task systems. In Proceedings of the 26th Real-Time Systems Symposium. Google ScholarDigital Library
- Baruah, S. K. and Fisher, N. 2006. The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems. IEEE Trans. Comp. 55, 7, 918--923. Google ScholarDigital Library
- Baruah, S. K. and Burns, A. 2006. Sustainable scheduling analysis. In Proceedings of the IEEE Real-Time Systems Symposium. 159--168. Google ScholarDigital Library
- Baruah, S. K. 2007. Techniques for multiprocessor global schedulability analysis. In Proceedings of the Real-Time Systems Symposium. 119--128. Google ScholarDigital Library
- Baruah, S. K. and Fisher, N. 2007. The partitioned dynamic-priority scheduling of sporadic task systems. Real-Time Syst. 36, 3, 199--226. Google ScholarDigital Library
- Baruah, S. K. and Fisher, N. 2008a. Non-migratory feasibility and migratory schedulability analysis of multiprocessor real-time systems. Real-Time Syst. 39, 1-3, 97--122. Google ScholarDigital Library
- Baruah, S. K. and Fisher, N. 2008b. Global fixed-priority scheduling of arbitrary-deadline sporadic task systems. In Proceedings of the 9th International Conference on Distributed Computing and Networking. Google ScholarDigital Library
- Baruah, S. K. and Baker, T. P. 2008. Global EDF schedulability analysis of arbitrary sporadic task systems. In Proceedings of the EuroMicro Conference on Real-Time Systems. 3--12. Google ScholarDigital Library
- Baruah, S. K. and Baker, T. P. 2009. An analysis of global EDF schedulability for arbitrary sporadic task systems. Real-Time Syst. 43, 1, 3--24. Google ScholarDigital Library
- Baruah, S. K., Bonifaci, V., Marchetti-Spaccamela, A., and Stiller, S. 2009. Implementation of a speedup-optimal global EDF schedulability test. In Proceedings of the EuroMicro Conference on Real-Time Systems. 259--268. Google ScholarDigital Library
- Baruah, S. K. 2007. Schedulability analysis of global deadline monotonic scheduling. Tech. rep., University of North Carolina, Chapel Hill, NC. http://www.cs.unc.edu/~baruah/Pubs.shtml.Google Scholar
- Bertogna, M., Cirinei, M., and Lipari, G. 2005a. New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In Proceedings of the 9th International Conference on Principles of Distributed Systems. Google ScholarDigital Library
- Bertogna, M., Cirinei, M., and Lipari, G. 2005b. Improved schedulability analysis of EDF on multiprocessor platforms. In Proceedings of the 17th Euromicro Conference on Real-Time Systems. 209--218. Google ScholarDigital Library
- Bertogna, M. 2007. Real-time scheduling analysis for multiprocessor platforms. Ph.D. dissertation. Scuola Superiore Sant'Anna, Pisa, Italy.Google Scholar
- Bertogna, M. and Cirinei, M. 2007. Response time analysis for global scheduled symmetric multiprocessor platforms. In Proceedings of the Real-Time Systems Symposium. 149--158. Google ScholarDigital Library
- Bertogna, M., Cirinei, M., and Lipari, G. 2008. Schedulability analysis of global scheduling algorithms on multiprocessor platforms. IEEE Trans. Paral. Distrib. Syst. 20, 4, 553--566. Google ScholarDigital Library
- Bertogna, M. 2009. Evaluation of existing schedulability tests for global EDF. In Proceedings of the 1st International Workshop on Real-Time Systems on Multicore Platforms: Theory and Practice. Google ScholarDigital Library
- Bharadwaj, V., Ghose, D., Mani, V., and Robertazzi, T. G. 1996. Scheduling Divisible Loads in Parallel and Distributed Systems. IEEE Computer Society Press, Los Alamitos, CA. Google ScholarDigital Library
- Bini, E. and Buttazzo, G. C. 2005. Measuring the performance of schedulability tests. Real-Time Syst. 30, 1--2, 129--154. Google ScholarDigital Library
- Bini, E., Buttazzo, G. C. and Bertogna, M. 2009a. The multi supply function abstraction for multiprocessors. In Proceedings of the Conference on Real-Time Computing Systems and Applications. Google ScholarDigital Library
- Bini, E., Bertogna, M., and Baruah, S.K. 2009b. Virtual Multiprocessor Platforms: Specification and Use. In Proceedings of the Real-Time Systems Symposium. Google ScholarDigital Library
- Bletsas, K. and Andersson, B. 2009. Notional processors: An approach for multiprocessor scheduling. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. 3--12. Google ScholarDigital Library
- Block, A., Leontyev, H., Brandenburg, B., and Anderson, J. H. 2007. A flexible real-time locking protocol for multiprocessors. In Proceedings of the Conference on Real-Time Computing Systems and Applications. 47--56. Google ScholarDigital Library
- Brandenburg, B. B., Calandrino, J. M. and Anderson, J. H. 2008a. On the scalability of real-time scheduling algorithms on multicore platforms: A case study. In Proceedings of the Real-Time Systems Symposium. 157--169. Google ScholarDigital Library
- Brandenburg, B. B., Calandrino, J. M., Block, A., Leontyev, H., and Anderson, J. H. 2008b. Real-time synchronization on multiprocessors: to block or not to block, to suspend or spin. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. 342--353. Google ScholarDigital Library
- Burchard, A., Liebeherr, J., Oh, Y., and Son, S. H. 1995. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans. Comp. 44, 12, 1429--1442. Google ScholarDigital Library
- Burns, A. and Wellings, A. 2009. Real-Time Systems and Programming Languages, 4th ed. Addison Wesley Longmain, Reading, MA. Google ScholarDigital Library
- Bonifaci, V., Marchetti-Spaccamela, A., and Stiller, S. 2008. A constant-approximate feasibility test for multiprocessor real-time scheduling. In Proceedings of the European Symposium on Algorithms. 210--221. Google ScholarDigital Library
- Buttazzo, G. 2005. Hard Real-Time Computing Systems Predictable Scheduling Algorithms and Applications, 2nd ed., Springer, Berlin, Germany. Google ScholarDigital Library
- Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J. H., and Baruah, S. K. 2004. A categorization of real-time multiprocessor scheduling problems and algorithms. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall, CRC Computer.Google Scholar
- Chao, Y.-H., Lin, S.-S., and Lin, K.-J. 2008. Schedulability issues for EDZL scheduling on real-time multiprocessor systems. Inform. Process. Lett. 107, 5, 158--164. Google ScholarDigital Library
- Chen, C-M., Tripathi, S.K., and Blackmore, A. 1994. A resource synchronization protocol for multiprocessor real-time systems. In Proceedings of the International Conference on Parallel Processing. 159--162. Google ScholarDigital Library
- Cho S., Lee, S. K., Han, A., and Lin, K.-J. 2002. Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans. Comm. E85-B, 12, 2859--2867.Google Scholar
- Cho, H., Ravindran, B., and Jensen, E. D. 2006. An optimal real-time scheduling algorithm for multiprocessors. In Proceedings of the Real-Time Systems Symposium. 1001--110. Google ScholarDigital Library
- Cirinei, M. and Baker, T. P. 2007. EDZL scheduling analysis. In Proceedings of the EuroMicro Conference on Real-Time Systems. 9--18. Google ScholarDigital Library
- Collette, S., Cucu, L., and Goossens, J. 2007. Algorithm and complexity for the global scheduling of sporadic tasks on multiprocessors with work-limited parallelism. In Proceedings of the International Conference on Real-Time and Network Systems. 123--128.Google Scholar
- Collette, S., Cucu, L. and Goossens, J. 2008. Integrating job parallelism in real-time scheduling theory. Inform. Process. Lett. 106, 5, 180--187. Google ScholarDigital Library
- Cucu, L., and Goossens, J. 2006. Feasibility intervals for fixed-priority real-time scheduling on uniform multiprocessors. In Proceedings of the International Conference on Emerging Technologies and Factory Automation.Google Scholar
- Cucu, L., and Goossens, J. 2007. Feasibility intervals for multiprocessor fixed-priority scheduling of arbitrary deadline periodic systems, In Proceedings of the 10th Conference on Design, Automation and Test in Europe. Google ScholarDigital Library
- Cucu, L. 2008. Optimal priority assignment for periodic tasks on unrelated processors, In Proceedings of the Euromicro Conference on Real-Time Systems, WIP Session.Google Scholar
- Davari, S. and Dhall, S. K. 1986. On a periodic real time task allocation problem. Annual International Conference on System Sciences.Google Scholar
- Davis, R. I. and Burns, A. 2009. Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In Proceedings of the Real-Time Systems Symposium. Google ScholarDigital Library
- Dhall, S. K. and Liu, C. L. 1978. On a real-time scheduling problem. Oper. Res. 26, 1, 127--140.Google ScholarDigital Library
- Dertouzos, M. L. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the International Federation for Information Processing Working Conference on Data Semantics. 807--813.Google Scholar
- Dertouzos, M. L. and Mok, A. K. 1989. Multiprocessor scheduling in a hard real-time environment. IEEE Trans. Softw. Eng. 15, 12, 1497--1506. Google ScholarDigital Library
- Devi, U. C. Leontyev, H. and Anderson, J. 2006. Efficient synchronization under global EDF scheduling on multiprocessors. In Proceedings of the Euromicro conference on Real-Time Systems. 75--84. Google ScholarDigital Library
- Downing, C. 2009. Avionics, October, 40.Google Scholar
- Edmonds, J. and Pruh, K. 2009. Scalably scheduling processes with arbitrary speedup curves. In Proceedings of the Symposium on Discrete Algorithms. 685--692. Google ScholarDigital Library
- Fisher, N., Baruah, S. K., and Baker, T. P. 2006. The partitioned scheduling of sporadic tasks according to static priorities. In Proceedings of the EuroMicro Conference on Real-Time Systems. 118--127. Google ScholarDigital Library
- Fisher, N. and Baruah, S. K. 2006. Global static-priority scheduling of sporadic task systems on multiprocessor platforms. In Proceedings of the International Conference on Parallel and Distributed Computing and Systems.Google Scholar
- Fisher, N. and Baruah, S. K. 2007. The global feasibility and schedulability of general task models on multiprocessor platforms. In Proceedings of the Euromicro Conference on Real-Time Systems. 51--60. Google ScholarDigital Library
- Fisher, N. 2007. The multiprocessor real-time scheduling of general task systems. Ph.D. dissertation. Department of Computer Science, The University of North Carolina at Chapel Hill, Chapel Hill, NC.Google Scholar
- Funaoka, K., Kato, S., and Yamasaki, N. 2008. Work-conserving optimal real-time scheduling on multiprocessors. In Proceedings of the Euromicro Conference on Real-Time Systems. 13--22. Google ScholarDigital Library
- Funk, S., Goossens, J., and Baruah, S. K. 2001. On-line scheduling on uniform multiprocessors. In Proceedings of the IEEE Real-Time Systems Symposium. 183--192. Google ScholarDigital Library
- Funk, S. and Nadadur, V. 2009. LRE-TL: An optimal multiprocessor algorithm for sporadic task sets. In Proceedings of the Real-Time Networks and Systems Conference. 159--168.Google Scholar
- Gai, P., Lipari, G., and Di Natale, M. 2001. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In Proceedings of the Real-Time Systems Symposium. 73--83. Google ScholarDigital Library
- Gai, P., Di Natale, M., Lipari, G., Ferrari, A., Gabellini, C., and Marceca, P. 2003. A comparison of MPCP and MSRP when sharing resources in the Janus multiple-processor on a chip platform. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. Google ScholarDigital Library
- Garey, M. and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY. Google ScholarDigital Library
- Graham, R. L. 1972. Bounds on multiprocessor scheduling anomalies and related packing problem. In Proceedings of the AFIPS Spring Joint Computer Conference. 205--217. Google ScholarDigital Library
- Goossens, J., Funk, S., and Baruah, S. K. 2003. Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Syst. 25, 2--3, 187--205. Google ScholarDigital Library
- Guan, N., Stigge, M., Yi, W., and Yu, G. 2009. New response time bounds for fixed priority multiprocessor scheduling. In Proceedings of the Real-Time Systems Symposium. Google ScholarDigital Library
- Holman, P. and Anderson, J. H. 2005. Adapting Pfair scheduling for symmetric multiprocessors. J. Embed. Comput. 1, 4, 543--564. Google ScholarDigital Library
- Hong, K. S. and Leung, J. 1988. On-line scheduling of real-time tasks. In Proceedings of the Real-Time Systems Symposium. 244--250.Google Scholar
- Hong, K. S. and Leung, J.Y.-T. 1992. On-line scheduling of real-time tasks. IEEE Trans. Comp. 41, 1326--1331. Google ScholarDigital Library
- Horn, W. A. 1974. Some simple scheduling algorithms. Naval Res. Logist. Quart. 21, 177--185.Google ScholarCross Ref
- Ha, R. and Liu, J. W.-S. 1994. Validating timing constraints in multiprocessor and distributed real-time systems. In Proceedings of the International Conference on Distributed Computing Systems. 162--171.Google Scholar
- Kalyanasundaram, B. and Pruhs, K. 1995. Speed is as powerful as clairvoyance. In Proceedings of the Symposium on Foundations of Computer Science. 214--221. Google ScholarDigital Library
- Kato, S. and Yamasaki, N. 2007. Real-time scheduling with task splitting on multiprocessors. In Proceedings of the International Conference on Embedded and Real-Time Computing Systems and Applications. 441--450. Google ScholarDigital Library
- Kato, S. and Yamasaki, N. 2008a. Portioned EDF-based scheduling on multiprocessors. In Proceedings of the International Conference on Embedded Software. 139--148. Google ScholarDigital Library
- Kato, S. and Yamasaki, N. 2008b. Portioned static-priority scheduling on multiprocessors. In Proceedings of the International Parallel and Distributed Processing Symposium.Google Scholar
- Kato, S. and Yamasaki, N. 2008c. Global EDF-based scheduling with efficient priority promotion. In Proceedings of the International Conference on Embedded and Real-Time Computing Systems and Applications. 197--206. Google ScholarDigital Library
- Kato, S. and Yamasaki, N. 2009. Semi-partitioned fixed-priority scheduling on multiprocessors. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. 23--32. Google ScholarDigital Library
- Kato, S., Yamasaki, N., and Ishikawa. Y. 2009. Semi-partitioned scheduling of sporadic task systems on multiprocessors. In Proceedings of the Euromicro Conference on Real-Time Systems. 249--258. Google ScholarDigital Library
- Khemka, A. and Shyamasundar, R. K. 1997. An optimal multiprocessor real-time scheduling algorithm. J. Paral. Distrib. Comp. 43, 1, 37--45. Google ScholarDigital Library
- Lakshmanan, K., Rajkumar, R., and Lehoczky, J. 2009. Partitioned fixed-priority preemptive scheduling for multi-core processors. In Proceedings of the Euromicro Conference on Real-Time Systems. 239--248. Google ScholarDigital Library
- Lammers, D. 2004. Intel cancels Tejas, moves to dual-core designs. EETimes, May 7.Google Scholar
- Lauzac, S., Melhem, R., and Mosse, D. 1998. Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor. In Proceedings of the EuroMicro Workshop on Real-Time Systems. 188--195.Google Scholar
- Lee, S. K. 1994. On-line multiprocessor scheduling algorithms for real-time tasks. In Proceedings of the IEEE Region 10's 9th Annual International Conference. 607--611.Google Scholar
- Lee, W. Y., Hong, S. J., and Kim, J. 2003. On-line scheduling of scalable real-time tasks on multiprocessor systems. J. Parall. Distrib. Comp. 63, 12, 1315--1324. Google ScholarDigital Library
- Lehoczky, J. 1990. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of the Real-Time Systems Symposium. 201--209.Google ScholarCross Ref
- Leteinturier P. 2007. Multi-core processors: driving the evolution of automotive electronics architectures. Embedded.com, September 16.Google Scholar
- Leontyev, H. and Anderson, J. H. 2008. Hierarchical multiprocessor bandwidth reservation scheme with timing guarantees. In Proceedings of the Euromicro Conference on Real-Time Systems. 191--200. Google ScholarDigital Library
- Lin, X., Lu, Y., Deogun, J., and Goddard, S. 2007. Real-time divisible load scheduling for cluster computing. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. 303--314. Google ScholarDigital Library
- Liu, C. L. 1969. Scheduling algorithms for multiprocessors in a hard real-time environment. In JPL Space Programs Summary, vol. 37-60. JPL, Pasadena, CA, 28--31.Google Scholar
- Liu, C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61. Google ScholarDigital Library
- Liu, J. W. S. 2000. Real Time Systems. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
- Leung, J. Y.-T. and Whitehead, J. 1982. On the complexity of fixed-priority scheduling of periodic real-time tasks. Perform. Eval. 2, 237--250.Google ScholarCross Ref
- Lopez, J. M., Garcia, M., Diaz, J., and Garcia, D. F. 2000. Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems. In Proceedings of the Euromicro Conference on Real-time Systems. 25--33. Google ScholarDigital Library
- Lopez, J. M., Diaz, J. L., Garcia, M., and Garcia, D. F. 2003. Utilization bounds for multiprocessor RM scheduling. Real-Time Syst. 24, 1, 5--28. Google ScholarDigital Library
- Lopez, J. M., Diaz, J. L., and Garcia, D. F. 2004a. Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling. IEEE Trans. Parall. Distrib. Syst. 15, 7, 642--653. Google ScholarDigital Library
- Lopez, J. M., Garcia, M., Diaz, J. L., and Garcia, D. F. 2004b. Utilization bounds for EDF scheduling on real-time multiprocessor systems. Real-Time Syst. 28, 1, 39--68. Google ScholarDigital Library
- Lundberg, L., 2002. Analyzing fixed-priority global multiprocessor scheduling. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. Google ScholarDigital Library
- Lundberg, L. and Lennerstad, H. 2007. Guaranteeing response times for aperiodic tasks in global multiprocessor scheduling. Real-Time Syst. 35, 135--151. Google ScholarDigital Library
- Lundberg, L. and Lennerstad, H. 2008. Slack-based global multiprocessor scheduling of aperiodic tasks in parallel embedded real-time systems. In Proceedings of the International Conference on Computer Systems and Applications. 465--472. Google ScholarDigital Library
- Mellor-Crummey, J. and Scott, M. 1991. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comp. Syst. 9, 1, 21--65. Google ScholarDigital Library
- Oh, Y. and Son, S. H. 1993. Tight performance bounds of heuristics for a real-time scheduling problem. Tech. rep. CS-93-24. Department of Computer Science, University of Virginia, Charlottesville, VA. Google ScholarDigital Library
- Oh, Y. and Son, S. H. 1995. Allocating fixed priority periodic tasks on multiprocessor systems. Real-Time Syst. 9, 3, 207--239. Google ScholarDigital Library
- Oh, D. I. and Baker, T. P. 1998. Utilization bounds for N-processor rate monotone scheduling with stable processor assignment. Real-Time Syst. 15, 2, 183--193. Google ScholarDigital Library
- Park, M., Han, S., Kim, H., Cho, S., and Cho, Y. 2005. Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor. IEICE Trans. Inform. Syst. E88-D, 3, 658--661. Google ScholarDigital Library
- Phillips, C. A., Stein, C., Torng, E., and Wein, J. 1997. Optimal time-critical scheduling via resource augmentation. In Proceedings of the ACM Symposium on theory of Computing. Google ScholarDigital Library
- Piao, X., Han, S., Kim, H., Park, M., Cho, Y., and Cho, S. 2006. Predictability of earliest deadline zero laxity algorithm for multiprocessor real time systems. In Proceedings of the 9th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing. Google ScholarDigital Library
- PROARTIS. 2009. Probabilistic analysable real-time systems. EU FP-7-ICT-2009-4 Project proposal.Google Scholar
- Quiñones, E., Berger, E., Bernat, G., and Cazorla, F. 2009. Using randomised caches in real-time systems. In Proceedings of the Euromicro Conference on Real-Time Systems. 129--138. Google ScholarDigital Library
- Rajkumar, R., Sha, L., and Lehoczky, J. P. 1988. Real-time synchronization protocols for multiprocessors. In Proceedings of the Real Time Systems Symposium. 259--269.Google Scholar
- Robertazzi, T. G. 2003. Ten reasons to use divisible load theory. Computer 36, 5, 63--68. Google ScholarDigital Library
- Rothvoss, T. 2009. On the computational complexity of periodic scheduling. Ph.D. dissertation. Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland.Google Scholar
- Saez, S., Vila, J., and Crespo. A. 1998. Using exact feasibility tests for allocating real-time tasks in multiprocessor systems. In Proceedings of the Euromicro Workshop on Real-Time Systems. 53--60.Google ScholarCross Ref
- Sha, L., Rajkumar, R., and Lehoczky, J. P. 1990. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Comp. 39, 9, 1175--1185. Google ScholarDigital Library
- Sha, L., Abdelzaher, T., Arzen, K.-E., Cervin, A., Baker, T. P., Burns, A., Buttazzo, G., Caccamo, M., Lehoczky, J. P., and Mok, A. K. 2004. Real time scheduling theory: A historical perspective. Real-Time Syst. 28, 2/3, 101--155. Google ScholarDigital Library
- Shin, I., Easwaran, A., and Lee, I. 2008. Hierarchical scheduling framework for virtual clustering of multiprocessors. In Proceedings of the Euromicro Conference on Real-Time Systems. 181--190. Google ScholarDigital Library
- Simpson, H. R. 1990. Four-slot fully asynchronous communication mechanism. IEE Proc. 137 Part E, 1, 17--30.Google ScholarCross Ref
- Srinivasan, A. and Baruah, S. K. 2002. Deadline-based scheduling of periodic task systems on multiprocessors. Inform. Process. Lett. 84, 93--98. Google ScholarDigital Library
- Veeravalli, B., Ghose, D., and Robertazzi, T. G. 2003. Divisible load theory: A new paradigm for load scheduling in distributed systems. Cluster Comp. 6, 1, 7--17. Google ScholarDigital Library
- Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann, R., Mitra, T., Mueller, F., Puaut, I., Puschner, P., Staschulat, J., and Stenstrom, P. 2008. The worst-case execution-time problem overview of methods and survey of tools. ACM Trans. Embed. Comp. Syst. 7, 3, 1--53. Google ScholarDigital Library
- Zapata, O. U. P and Alvarez, P. M. 2004. EDF and RM multiprocessor scheduling algorithms: Survey and performance evaluation. Report No. CINVESTAV-CS-RTG-02. CINVESTAV-IPN, Sección de Computación, Zacatenco, Mexico.Google Scholar
- Zhu, D., Mossé, D., and Melhem, R. G. 2003. Multiple-resource periodic scheduling problem: How much fairness is necessary? In Proceedings of the Real Time Systems Symposium. 142--151. Google ScholarDigital Library
Index Terms
- A survey of hard real-time scheduling for multiprocessor systems
Recommendations
Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred Preemption
Special Issue on Embedded Platforms for Crypto and Regular PapersThis 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 ...
Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems
This paper is an extended version of a paper that appeared in the proceedings of the IEEE Real-Time Systems Symposium 2009. This paper has been updated with respect to advances made in schedulability analysis, and contains a number of significant ...
A semi-partitioned real-time scheduling approach for periodic task systems on multicore platforms
SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied ComputingSemi-partitioned scheduling is regarded as a viable alternative to partitioned or global scheduling approaches. Advantage of semi-partitioned scheduling is two-folds: it has reduced runtime overhead compared to global scheduling, and improved ...
Comments