Abstract
In this chapter we consider the problem of scheduling real-time applications upon multiprocessors, or equivalently upon multicores, which represents the current trend for embedded and cyber-physical systems. We present first popular models of computation for critical real-time applications. We then present a classification of the scheduler we may find in the middleware of real-time and cyber-physical systems. Those algorithms are compared and their important properties are then analyzed. Two very different kinds of solutions are then presented and compared: the partitioned scheduling and the global scheduling. Important metrics are considered in our comparison like utilization bounds and speedup factors. Lastly, we deal with parallel applications where each program can execute on several processors. Such an intratask parallelism allows to use efficiently multicore platforms.
Similar content being viewed by others
References
B. Andersson, D. de Niz, in Analyzing global-EDF for multiprocessor scheduling of parallel tasks. In International conference on principles of distributed systems (Springer, 2012), pp. 16–30
B. Andersson, J. Jonsson, in The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50%. In Real-time systems, 2003. Proceedings. 15th euromicro conference on (2003), pp. 33–40
T. Baker, An analysis of edf scheduling on a multiprocessor. IEEE Trans. Prallel Distrib Syst 15(18), 760–768 (2005)
T. Baker, S. Baruah, in Sustainable multiprocessor scheduling for sporadic task systems. In Euromicro Conference on Real-Time Systems, ECRTS 2009 (2009), pp. 141–150
S. Baruah, in Techniques for multiprocessor global schedulability analysis. In Proceedings of the 28th IEEE International Real-Time Systems Symposium, RTSS ‘07 (IEEE Computer Society, Washington, DC, 2007), pp. 119–128
S. Baruah, Partitioned EDF scheduling: A closer look. Real-Time Syst. 49(6), 715–729 (2013)
S.K. Baruah, N.K. Cohen, C.G. Plaxton, D.A. Varvel, in Proportionate progress: a notion of fairness in resource allocation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, (STOC’93) (1993), pp. 345–354
S.K. Baruah, N.K. Cohen, C.G. Plaxton, D.A. Varvel, Proportionate progress: A notion of fairness in resource allocation. Algorithmica 15, 600–625 (1996)
S. Baruah, V. Bonifaci, A. Marchetti-Spaccamela, L. Stougie, A. Wiese, in A generalized parallel task model for recurrent real-time processes. In Real-Time Systems Symposium (2012), pp. 63–72
V. Berten, P. Courbin, J. Goossens, in Gang fixed priority scheduling of periodic moldable real-time tasks. In 5th Junior Researcher Workshop on Real-Time Computing (2011), pp. 9–12
J. Blazewicz, M. Drabowski, J. Weglarz, Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Comput. 100(5), 389–393 (1986)
V. Bonifaci, A. Marchetti-Spaccamela, S. Stiller, A. Wiese, in Feasibility analysis in the sporadic DAG task model. In Euromicro Conference on Real-Time Systems (IEEE Computer Society, 2013), pp. 225–233
R. Buyya, Scheduling Parallel Jobs on Clusters, in High Performance Cluster Computing: Architectures and Systems, (Prentice Hall PTR, Upper Saddle River, 1999), pp. 519–533
J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, S. Baruah, A categorization of real-time multiprocessor scheduling problems and algorithms, in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ed. by J.Y.-T. Leung (Ed), (Chapman Hall/CRC Press, London, 2004)
R. Chandra, L. Dagum, D. Kohr, D. Maydan, J. McDonald, R. Menon, Parallel Programming in OpenMP (Morgan Kaufmann Publishers Inc., San Francisco, 2001a)
R. Chandra, D. Leonaldo, K. Dave, M. Dror, M. Jeff, M. Ramesh, Parallel Programming in OpenMP (Morgan Kaufmann, San Francisco, 2001b)
M. Chéramy, P.-E. Hladik, A.-M. Déplanche, in Simso: a simulation tool to evaluate real-time multiprocessor scheduling algoritehms. In Proceedings of the 5th International Workshop on Analysis Tools and Methodologies for Embedded and Real-Time Systems (Waters, 2014)
E.G. Coffman, Jr., D.S. Johnson, M.R. Garey, Approximation algorithms for bin packing: a survey, in Approximation Algorithms for NP-Hard Problems, ed. by D. Hochbaum (Ed), (PWS Publishing, Boston, 1996)
S. Collette, L. Cucu, J. Goossens, Integrating job parallelism in real-time scheduling theory. Inf. Process. Lett. 106(5), 180–187 (2008)
P. Courbin, I. Lupu, J. Goossens, Scheduling of hard real-time multi-phase multi-thread periodic tasks. Real-Time Syst. 49(2), 239–266 (2013)
M. Dertouzos, A. Mok, Multiprocessor online scheduling of hard-real-time tasks. IEEE Trans. Softw. Eng. 15, 1497–1506 (1989)
S.K. Dhall, C.L. Liu, On a real-time scheduling problem. Oper. Res. 26(1), 127–140 (1978)
M. Drozdowski, Scheduling parallel tasks—algorithms and complexity, in Handbook of Scheduling Algorithms, Models and Performance Analysis, (Chapman & Hall/CRC Press, London, 2004)
P.-F. Dutot, G. Mounie, D. Trystram, Scheduling parallel tasks—approximation algorithms, in Handbook of Scheduling Algorithms, Models and Performance Analysis, (Chapman & Hall/CRC Press, London, 2004)
P. Emberson, R. Stafford, R. Davis, in Techniques for the synthesis of multiprocessor task sets. In Proceedings 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-Time Systems (WATERS 2010) (2010), pp. 6–11
N. Fisher, J. Goossens, S. Baruah, Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible. Real-Time Syst. 45(11), 26–71 (2010)
S. Funk, G. Levin, C. Sadowski, I. Pye, S.A. Brandt, Dp-fair: A unifying theory for optimal hard real-time multiprocessor scheduling. Real-Time Syst. 47(5), 389–429 (2011)
M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, New York, 1979)
A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam, PVM: Parallel Virtual Machine A Users’ Guide and Tutorial for Networked Parallel Computing (MIT Press, Cambridge, MA, 1994)
J. Goossens, V. Berten, in Gang FTP scheduling of periodic and parallel rigid real-time tasks. In 18th International Conference on Real-Time and Network Systems (2010), pp. 189–196
J. Goossens, P. Richard, Optimal scheduling of periodic gang tasks. Leibniz Trans. Embed. Syst. 3, 1 (2016)
J. Goossens, S. Funk, S. Baruah, Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Syst. 25(12), 187–205 (2003)
S. Gorlatch, H. Bischof, A generic MPI implementation for a data-parallel skeleton: formal derivation and application to FFT. Parallel Process. Lett. 8(4), 447–458 (1998)
R.L. Graham, Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416–429 (1969)
W. Gropp, E. Lusk, A. Skjellum, Using MPI: Portable Parallel Programming with the Message-Passing Interface, 2nd edn. (MIT Press, Cambridge, 1999)
R. Ha, J. Liu, in Validating timing constraints in multiprocessor and distributed real-time systems. In Distributed Computing Systems, 1994., Proceedings of the 14th International Conference on (jun 1994), pp. 162–171.
K. Hong, J.-T. Leung, On-line scheduling of real-time tasks. Comput. IEEE Trans. 41(10), 1326–1331 (1992)
W. Horn, Some simple scheduling algorithms. Naval Res. Logist. Q. 21, 177–185 (1974)
B. Kalyanasundaram, K. Pruhs, Speed is as powerful as clairvoyance. J. ACM 47, 617–643 (2000)
A. Karrenbauer, T. Rothvo�, A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks, in Approximation and Online Algorithms, Lecture Notes in Computer Science, ed. by K. Jansen, R. Solis-Oba (Eds), vol. 6534, (Springer, Berlin/Heidelberg, 2011), pp. 166–177
K. Lakshmanan, S. Kato, R. Rajkumar, in Scheduling parallel real-time tasks on multi-core processors. In Real-Time Systems Symposium (2010), pp. 259–268.
J.Y.T. Leung, J. Whitehead, On the comlpexity of fixed-priority scheduling of periodic, real-time tasks. Perform. Eval. 2, 237–250 (1982)
J. Li, K. Agrawal, C. Lu, C. Gill, in Analysis of global EDF for parallel tasks. In Euromicro Conference on Real-Time Systems (IEEE Computer Society, 2013), pp. 3–13.
J.C. Liu, J.W. Layland, Scheduling algorithms for multiprogramming in hard real-time environment. J. ACM 20(1), 46–61 (1973)
J.M. López, J.L. Diaz, D.F. García, Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling. IEEE Trans. Parallel Distrib. Syst. 15, 642–653 (2004)
J.M. López, M. Garcia, J.L. Diaz, D.F. Garcia, Utilization bounds for multiprocessor rate-monotonic scheduling. Real-Time Syst. 24, 5–28 (2003)
C. Maia, M. Bertogna, L.M. Nogueira, L.M. Pinho, in Response-time analysis of synchronous parallel tasks in multiprocessor systems. In Proceedings of the 22nd International Conference on Real-Time Networks and Systems (ACM, 2014), p. 3.
R. McNaughton, Scheduling with deadlines and loss functions. Manag. Sci. 6(1) (1959)
G. Nelissen, V. Berten, J. Goossens, D. Milojevic, in Techniques optimizing the number of processors to schedule multi-threaded tasks. In Euromicro Conference on Real-Time Systems (IEEE Computer Society Press, 2012a), pp. 321–330.
G. Nelissen, V. Berten, V. Nelis, J. Goossens, D. Milojevic, in U-EDF: an unfair but optimal multiprocessor scheduling algorithm for sporadic tasks. In 22th Euromicro Conference on Real-Time Systems (ECRTS’12) (2012b), pp. 13–23.
D.-I. Oh, T. Baker, Utilization bounds for n-processor rate monotonic scheduling with static processor assignment. Real-Time Syst. 15, 183–192 (1998)
Y. Oh, S.H. Son, Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Syst. 9, 207–239 (1995)
C.A. Phillips, C. Stein, E. Torng, J. Wein, in Optimal time-critical scheduling via resource augmentation (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC ’97) (ACM, 1997), pp. 140–149.
C.A. Phillips, C. Stein, E. Torng, J. Wein, Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2), 163–200 (2002)
M.L. Pinedo, M.L. Pinedo, Parallel machine models (deterministic), in Scheduling, (Springer, New York, 2008), pp. 111–149
P. Reigner, G. Lima, E. Massa, G. Levin, S. Brandt, in Run: optimal multiprocessor real-time scheduling via reduction to uniprocessor. In 32th IEEE Real-Time Systems Sympposium (RTSS’11) (2011), pp. 104–115.
P. Richard, J. Goossens, S. Kato, in Comments on “Gang EDF Schedulability Analysis”. Thech. rep., Univeristé de Poitiers (2016).
A. Saifullah, K. Agrawal, C. Lu, C. Gill, in Multi-core real-time scheduling for generalized parallel task models. In Real-Time Systems Symposium (2011), pp. 217–226.
A. Srivinasan, J. Anderson, Fair scheduling of dynamic tasks systems on multiprocessors. J. Syst. Softw. 77(11), 67–80 (2005)
A. Srivinasan, S. Baruah, Deadline-based scheduling of periodic task systems on multiprocessors. Inf. Process. Lett. 84(2), 93–98 (2002)
V. Sunderam, PVM: A framework for parallel distributed computing. Concurrency Pract Exp 2(4), 315–339 (1990)
D.W. Walker, J.J. Dongarra, MPI: a standard message passing interface. Supercomputer 12, 56–68 (1996)
D. Zhu, D. Mossé, R.G. Melhem, in Multiple-resource periodic scheduling problem: how much fairness is necessary? In Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS 2003), 3–5 December 2003, Cancun, Mexico (2003), pp. 142–151.
D. Zhu, X. Qi, D. Mossé, R.G. Melhem, An optimal boundary fair scheduling algorithm for multiprocessor real-time systems. J. Parallel Distrib. Comput. 71(10), 1411–1425 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2017 Springer-Verlag GmbH Germany
About this entry
Cite this entry
Goossens, J., Richard, P. (2017). Multiprocessor Real-Time Scheduling. In: Wang, X. (eds) Cyber-Physical Systems: A Reference. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54477-4_2-1
Download citation
DOI: https://doi.org/10.1007/978-3-642-54477-4_2-1
Received:
Accepted:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54477-4
Online ISBN: 978-3-642-54477-4
eBook Packages: Springer Reference EngineeringReference Module Computer Science and Engineering