Abstract
Optimal online scheduling algorithms are known for sporadic task systems scheduled upon a single processor. Additionally, optimal online scheduling algorithms are also known for restricted subclasses of sporadic task systems upon an identical multiprocessor platform. The research reported in this article addresses the question of existence of optimal online multiprocessor scheduling algorithms for general sporadic task systems. Our main result is a proof of the impossibility of optimal online scheduling for sporadic task systems upon a system comprised of two or more processors. The result is shown by finding a sporadic task system that is feasible on a multiprocessor platform that cannot be correctly scheduled by any possible online, deterministic scheduling algorithm. Since the sporadic task model is a subclass of many more general real-time task models, the nonexistence of optimal scheduling algorithms for the sporadic task systems implies nonexistence for any model which generalizes the sporadic task model.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Audsley NC, Burns A, Richardson MF, Wellings AJ (1991) Hard real-time scheduling: the deadline monotonic approach. In: Proceedings 8th IEEE workshop on real-time operating systems and software, Atlanta, May 1991, pp 127–132
Baker T, Cirinei M (2006) A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline tasks. In: Proceedings of the IEEE real-time systems symposium, Rio de Janeiro, December 2006. IEEE Computer Society, Los Alamitos, pp 178–187
Baker T, Cirinei M (2007) Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasks. In: Proceedings of the 10th international conference on principles of distributed systems, Guadeloupe, December 2007, pp 62–75
Baruah S (2003) Dynamic- and static-priority scheduling of recurring real-time tasks. Real-Time Syst 24(1):99–128
Baruah S, Fisher N (2007) Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems. In: Proceedings of the 11th international conference on principles of distributed systems, Guadeloupe, French West Indies, December 2007. Springer, Berlin
Baruah S, Howell R, Rosier L (1993) Feasibility problems for recurring tasks on one processor. Theor Comput Sci 118(1):3–20
Baruah S, Cohen N, Plaxton G, Varvel D (1996) Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15(6):600–625
Baruah S, Chen D, Gorinsky S, Mok A (1999) Generalized multiframe tasks. Real-Time Syst 17(1):5–22
Birman K, Joseph T (1987) Exploiting virtual synchrony in distributed systems. SIGOPS Oper Syst Rev 21(5):123–138
Dertouzos M (1974) Control robotics: the procedural control of physical processors. In: Proceedings of the IFIP congress, pp 807–813
Dertouzos M, Mok AK (1989) Multiprocessor scheduling in a hard real-time environment. IEEE Trans Softw Eng 15(12):1497–1506
Dhall SK, Liu CL (1978) On a real-time scheduling problem. Oper Res 26:127–140
Fischer MJ, Lynch NA, Paterson MS (1985) Impossibility of distributed consensus with one faulty process. J ACM 32(2):374–382
Fisher N, Baruah S (2009) The feasibility of general task systems with precedence constraints on multiprocessor platforms. Real-Time Syst 41(1):1–26
Hong K, Leung J (1988) On-line scheduling of real-time tasks. In: Proceedings of the real-time systems symposium, Huntsville, AL, December 1988. IEEE, New York, pp 244–250
Horn W (1974) Some simple scheduling algorithms. Nav Res Logist Q 21:177–185
Jeffay K, Stanat D, Martel C (1991) On non-preemptive scheduling of periodic and sporadic tasks. In: Proceedings of the 12th real-time systems symposium, San Antonio, TX, December 1991. IEEE Computer Society, Los Alamitos, pp 129–139
Kolmogorov AN, Fomin SV (1970) Introductory real analysis. Dover, New York
Leung J, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform Eval 2:237–250
Liu C, Layland J (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 20(1):46–61
Mok AK (1983) Fundamental design problems of distributed systems for the hard-real-time environment. PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology. Available as Technical Report No. MIT/LCS/TR-297
Phillips CA, Stein C, Torng E, Wein J (1997) Optimal time-critical scheduling via resource augmentation. In: Proceedings of the twenty-ninth annual ACM symposium on theory of computing, El Paso, TX, 4–6 May 1997, pp 140–149
Srinivasan A, Anderson J (2002) Optimal rate-based scheduling on multiprocessors. In: Proceedings of the 34th ACM symposium on the theory of computing, May 2002, pp 189–198
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fisher, N., Goossens, J. & Baruah, S. Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible. Real-Time Syst 45, 26–71 (2010). https://doi.org/10.1007/s11241-010-9092-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11241-010-9092-7